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

یک گراف و درخت SPQR آن
در نظریه گراف، یکی از زیرشاخه‌های ریاضیات، مولفه‌های سه‌همبند یک گراف دوهمبند یک دستگاه از گراف‌های کوچک‌تر است که همه برش‌های دوراسی گراف را توصیف می‌کند. درخت SPQR یک داده ساختار درختی است که در علوم رایانه، به ویژه در الگوریتم‌های گراف، برای نشان دادن مولفه‌های سه همبند یک درخت استفاده می‌شود.درخت SPQR یک گراف را می‌توان در یک زمان خطی بنا کرد.این گراف کاربردهای متعددی در الگوریتم‌های پویای رنگ‌آمیزی گراف دارد.
ساختارهای بنیادین درخت SPQR، مولفه‌های سه همبند گراف، و اتصال بین این اجزا و تعبیه مسطح یک گراف مسطح، را اولین بار ساندرز مک‌لین(1973) بررسی کرد.پژوهشگران دیگری همچون دی‌باتیستا وتاماسیا این ساختارها را، پیش از رسمی شدن به عنوان درخت SPQR در الگوریتم‌های کارآمد استفاده کرده بودند.
ساختار
یک درخت SPQR فرم یک درخت بدون ریشه را دارد که در آن هر گره x با یک گراف بدون جهت یا یک گراف چندگانه G x متناظر شده‌است. گره و گراف متناظر با آن یکی از 4 فرم زیر را داراست:
در یک گره S، گراف متناظر یک گراف دوری با بیشتر از 2 راس یا یال است.این مورد مشابه ترکیب سری در گراف‌های سری- موازی است؛ S نشان دهنده سری(series) است.
در یک گره P، گراف متناظر یک گراف دوقطبی(یک گراف چندگانه دارای دو راس با تعداد یال بیشتر از 2) است.یک همزاد مسطح( ) برای یک گراف دوری. این مورد مشابه ترکیب موازی در گراف‌های سری- موازی است؛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 و ساختن راس فوقانی دیگر و حذف دو یال مجازی ساخته می‌شود.با این کار گراف بزرگتر جمع دو گروهکی ( ) برای دو گراف 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 ارتباط دارند، می‌توانند به صورت دلخواه جابه‌جا شوند. همه نمایش‌های مسطح می‌توانند به این صورت توصیف شوند.