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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک گراف و درخت SPQR آن

در نظریه‌ی گراف، یکی از زیرشاخه‌های ریاضیات، مولفه‌های سه‌همبند یک گراف دوهمبند یک دستگاه از گراف‌های کوچک‌تر است که همه‌ی برش‌های دوراسی گراف را توصیف می کند.درخت 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 و ساختن راس فوقانی دیگر و حذف دو یال مجازی ساخته می شود.با این کار گراف بزرگتر جمع دو گروهکی (Clique-sum ) برای دو گراف 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 ارتباط دارند، می توانند به صورت دلخواه جابه‌جا شوند. همه‌ی نمایش‌های مسطح می توانند به این صورت توصیف شوند.

منابع[ویرایش]

پیوند به بیرون[ویرایش]