درخت اس‌پی‌کیوآر

یک گراف و درخت SPQR آن

در نظریهٔ گراف، یکی از زیرشاخه‌های ریاضیات، مولفه‌های سه‌همبند یک گراف دوهمبند یک دستگاه از گراف‌های کوچک‌تر است که همهٔ برش‌های دوراسی گراف را توصیف می‌کند.درخت SPQR یک داده ساختار درختی است که در علوم رایانه، به ویژه در الگوریتم‌های گراف، برای نشان دادن مولفه‌های سه همبند یک درخت استفاده می‌شود.درخت SPQR یک گراف را می‌توان در یک زمان خطی بنا کرد.این گراف کاربردهای متعددی در الگوریتم های پویای رنگ‌آمیزی گراف دارد. ساختارهای بنیادین درخت SPQR، مؤلفه‌های سه همبند گراف، و اتصال بین این اجزا و تعبیهٔ مسطح یک گراف مسطح، را اولین بار ساندرز مک‌لین(1973) بررسی کرد.پژوهشگران دیگری همچون دی‌باتیستا وتاماسیا این ساختارها را، پیش از رسمی شدن به عنوان درخت SPQR در الگوریتم‌های کارآمد استفاده کرده بودند.

ساختار

یک درخت SPQR فرم یک درخت بدون ریشه را دارد که در آن هر گره x با یک گراف بدون جهت یا یک گراف چندگانه G_x متناظر شده‌است. گره و گراف متناظر با آن یکی از 4 فرم زیر را داراست:

• در یک گرهٔ S، گراف متناظر یک گراف دوری با بیشتر از 2 راس یا یال است.این مورد مشابه ترکیب سری در گراف‌های سری- موازی است؛ S نشان دهندهٔ سری(series) است.
• در یک گرهٔ P، گراف متناظر یک گراف دوقطبی(یک گراف چندگانه دارای دو راس با تعداد یال بیشتر از 2) است.یک همزاد مسطح(Planar Dual) برای یک گراف دوری. این مورد مشابه ترکیب موازی در گراف‌های سری- موازی است؛P نشان دهندهٔ موازی(parallel)) است.
• در یک گرهٔ Q، گراف متناظر یک یال تنها دارد. این مورد جزئی تنها برای گراف‌هایی که یک راس دارند به کار برده می‌شود و در گراف‌های پیچیده‌تر ظاهر نمی‌شود.
• در یک گرهٔ R، گراف متناظر یک گراف سه‌همبند است که دوری با دوقطبی نباشد.R نشان دهندهٔ صلب (rigid ) است: در کاربرد درخت SPQR در تعبیهٔ گراف مسطح، گراف متناظر با یک گرهٔ R یک تعبیهٔ مسطح منحصربه‌فرد دارد.

هر یال xy بین دو گرهٔ درخت SPQR متناظر با دو یال جهت‌دار مجازی است که یکی از آن‌ها یک یال در G_x و دیگری یالی در G_y است. هر یال در یک گراف G_x می‌تواند حداکثر در یک درخت SPQR یال مجازی باشد.

یک درخت SPQR، T، یک گراف دوهمبند G_T را نمایش می‌دهد که اینگونه ساخته می‌شود: هرگاه یال xy در درخت SPQR، یال مجازی ab، در گراف G_x را با یال مجازی cd، در G_y متناظر کند، یک گراف بزرگتر با ادغام کردن a و c و ساختن یک راس فوقانی و ادغام کردن b و d و ساختن راس فوقانی دیگر و حذف دو یال مجازی ساخته می‌شود.با این کار گراف بزرگتر جمع دو گروهکی (Clique-sum ) برای دو گراف G_x و G_y است. با انجام این گام برای هر یال درخت SPQR گراف G_T ساخته می‌شود، ترتیب این گام‌ها تأثیری در نتیجهٔ نهایی ندارد. هر راس در گراف G_x با یک راس منحصربه‌فرد در G_T متناظر می‌شود.(راس فوقانی که از ادغام این راس به وجود آمده است.)

معمولاً" در یک درخت SPQR دو گرهٔ S یا دو گرهٔ P نمی‌توانند مجاور باشند، زیرا اگر چنین اتفاقی بیفتد دو گرهٔ مجاور می توانند ادغام شوند و یک گرهٔ بزرگتر را تولید کنند. با این فرض درخت SPQR به طور منحصربه‌فرد از گرافش مشخص می شود. وقتی که یک گراف G با یک درخت SPQR که هیچ دو گرهٔ P یا S مجاور ندارد نشان داده شود آنگاه گراف‌های G_x متناظر با گره‌های درخت 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.