درخت اسپیکیوآر: تفاوت میان نسخهها
ایجاد یک مقاله نو از طریق ایجادگر |
(بدون تفاوت)
|
نسخهٔ ۳۰ نوامبر ۲۰۱۱، ساعت ۲۲:۳۵
در نظریهی گراف، یک زیرشاخه از ریاضیات، مولفههای سههمبند یک گراف دوهمبند یک دستگاه از گرافهای کوچکتر هستند که همهی برشهای دوراسی گراف را توصیف می کند.درخت SPQR یک داده ساختار درختی است که در علوم رایانه، به ویژه در الگوریتم های گراف،برای نشان دادن مولفههای سه همبند یک درخت استفاده می شود.درخت SPQR یک گراف را می توان در یک زمان خطی بنا کرد.این گراف کاربردهای متعددی در الگوریتم های پویای رنگآمیزی گراف دارد. ساختارهای بنیادین درخت SPQR، مولفههای سه همبند گراف، و اتصال بین این اجزا و تعبیهی مسطح یک گراف مسطح، را اولین بار ساندرز مکلین(1973) بررسی کرد.پژوهشگران دیگری همچون دیباتیستا وتاماسیا این ساختارها را، پیش از رسمی شدن به عنوان درخت SPQR در الگوریتمهای کارآمد استفاده کرده بودند.
ساختار
یک درخت SPQR فرم یک درخت بدون ریشه را دارد که در آن هر گره x با یک گراف بدون جهت یا یک گراف چندگانه Gx متناظر شده است. گره و گراف متناظر با آن یکی از 4 فرم زیر را داراست:
- در یک گرهی S، گراف متناظر یک گراف دوری با بیشتر از 2 راس یا یال است.این مورد مشابه ترکیب سری در گرافهای سری- موازی است؛ S نشان دهندهی سری(series) است.
- در یک گرهی P، گراف متناظر یک گراف دوقطبی، یک گراف چندگانه دارای دو راس با تعداد یال بیشتر از 2 است. planar dual برای یک گراف دوری. این مورد مشابه ترکیب موازی در گرافهای سری- موازی است؛P نشان دهندهی موازی(parallel)) است.
- در یک گرهی Q، گراف متناظر یک یال تنها دارد. این مورد جزئی تنها برای گرافهایی که یک راس دارند به کار برده می شود و در گرافهای پیچیدهتر ظاهر نمی شود.
- در یک گرهی R، گراف متناظر یک گراف سههمبند است که دوری با دوقطبی نباشد.R نشان دهندهی صلب (rigid ) است: در کاربرد درخت SPQR در تعبیهی گراف مسطح، گراف متناظر با یک گرهی R یک تعبیهی مسطح منحصر به فرد دارد.
هر یال xy بین دو گرهی درخت SPQR متناظر با دو یال جهتدار مجازی است که یکی از آنها یک یال در Gx و دیگری یالی در Gy است. هر یال در یک گراف Gx می تواند حداکثر در یک درخت SPQR یال مجازی باشد.
یک درخت SPQR، T، یک گراف دوهمبند GT را نمایش می دهد که اینگونه ساخته می شود: هرگاه یال xy در درخت SPQR، یال مجازی ab، در گراف Gx را با یال مجازی cd، در Gy متناظر کند، یک گراف بزرگتر با ادغام کردن a و c و ساختن یک راس فوقانی و ادغام کردن b و d و ساختن راس فوقانی دیگر و حذف دو یال مجازی ساخته می شود.با این کار گراف بزرگتر جمع دو گروهکی برای دو گراف Gx و Gy است. با انجام این گام برای هر یال درخت SPQR گراف GT ساخته می شود، ترتیب این گام ها تاثیری در نتیجه ی نهایی ندارد. هر راس در گراف Gx با یک راس منحصر به فرد در GT متناظر می شود؛ راس فوقانی که از ادغام این راس به وجود آمده است.
معمولا" در یک درخت SPQR دو گرهی S یا دو گرهی P نمی توانند مجاور باشند، زیرا اگر چنین اتفاقی بیفتد دو گرهی مجاور می توانند ادغام شوند و یک گرهی بزرگتر را تولید کنند. با این فرض درخت SPQR به طور منحصر به فرد از گرافش مشخص می شود. وقتی که یک گراف G با یک درخت SPQR که هیچ دو گرهی P یا S مجاور ندارد نشان داده شود آنگاه گرافهای Gx متناظر با گرههای درخت SPQR به عنوان مولفههای سههمبند G شناخته می شوند.
یافتن برشهای دوراسی
با استفاده از درخت SPQR یک گراف G (بدون گرههای Q) یافتن هر جفت راسهایی مانند x و u، که حذف کردن آنها باعث غیرهمبند شدن گراف می شود، و مولفههای همبند گراف باقی مانده، سرراست می شود.
- دو راس u و v ممکن است دو سر یک یال مجازی در گراف متناظر با یک گرهی R باشند، که در این صورت دو مولفه با دو زیردرخت از درخت SPQR نشان داده می شوند که از حذف کردن یال متناظر در درخت SPQR به دست می آیند.
- دو راس u و v ممکن است دو راس در گراف متناظر با یک گرهی P باشند که تعداد 2 یا بیشتر یال مجازی دارد. در این صورت مولفههایی که با حذف u و v به وجود می آیند، با زیردرختهایی از درخت SPQR نشان داده می شوند به طوری که هر یک در ازای یکی از یالهای مجازی گره است.
- دو راس u و v ممکن است دو راس در گراف متناظر با یک گرهی S باشند به طوری که یا u و v مجاور نیستند یا یال uv مجازی است. اگر یال مجازی باشد، دوتایی (u,v ) به یک گرهی نوع P و R هم تعلق دارند و مولفههای آنها در بالا توصیف شدهاند. اگر دو راس مجاور نباشند پس دو مولفه با دو مسیر در گراف دوری متناظر با گرهی S، و با گرههای وابسته به آن دو مسیر در درخت SPQR نشان داده می شود.
تعبیهی گرافهای مسطح
گراف مسطح سههمبند، با توجه به جهتگیری و انتخاب اینکه کدام وجه آن وجه خارجی باشد، یک تعبیهی مسطح منحصر به فرد دارد. وجههای تعبیه دقیقا" همان دورهای غیرمجزای گراف هستند. عرچند برای یک گراف مسطح( با یالها و راسهای برچسبدار) که دوهمبند باشد، آزادی بیشتری برای پیدا کردن تعبیهی همبند وجود دارد. مخصوصا" وقتی دو گره در درخت SPQR گراف، که با یک جفت یال مجازی به هم متصلند، تغییر جهتگیری یکی از گرهها امکان پذیر است. همچنین در یک گرهی P درخت SPQR قسمتهای مختلف درخت که با یالهای مجازی با گرهی P ارتباط دارند، می توانند به صورت دلخواه جابهجا شوند. همهی نمایشهای مسطح می توانند به این صورت توصیف شوند.
منابع
- Bienstock, Daniel; Monma, Clyde L. (1988), "On the complexity of covering vertices by faces in a planar graph", SIAM Journal on Computing, 17 (1): 53–76, doi:10.1137/0217004.
- Di Battista, Giuseppe; Tamassia, Roberto (1989), "Incremental planarity testing", Proc. 30th Annual Symposium on Foundations of Computer Science, pp. 436–441, doi:10.1109/SFCS.1989.63515.
- Di Battista, Giuseppe; Tamassia, Roberto (1990), "On-line graph algorithms with SPQR-trees", Proc. 17th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 443, Springer-Verlag, pp. 598–611, doi:10.1007/BFb0032061.
- Di Battista, Giuseppe; Tamassia, Roberto (1996), "On-line planarity testing" (PDF), SIAM Journal on Computing, 25 (5): 956–997, doi:10.1137/S0097539794280736.
- Gutwenger, Carsten; Mutzel, Petra (2001), "A linear time implementation of SPQR-trees", Proc. 8th International Symposium on Graph Drawing (GD 2000), Lecture Notes in Computer Science, vol. 1984, Springer-Verlag, pp. 77–90, doi:10.1007/3-540-44541-2_8.
- Hopcroft, John; Tarjan, Robert (1973), "Dividing a graph into triconnected components", SIAM Journal on Computing, 2 (3): 135–158, doi:10.1137/0202012.
- Mac Lane, Saunders (1937), "A structural characterization of planar combinatorial graphs", Duke Mathematical Journal, 3 (3): 460–472, doi:10.1215/S0012-7094-37-00336-3.
پیوند به بیرون
- SQPR tree implementation in the Open Graph Drawing Framework.