مجموعه غالب

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

در نظریه گراف، مجموعه غالب برای گراف (G=(V, E زیرمجموعه‌ای از رئوس به نام D است که به ازای هر راس خارج از D حداقل یک راس مجاور داخل مجموعه خواهیم داشت. تعداد رئوس کوچکترین مجموعه غالب را عدد غالب گراف G یا (γ(G می‌نامیم.
مسئله یافتن مجموعه غالبی که دارای ویژگی γ(G) ≤ K برای G و K مشخص باشد یک مسئله NP-complete است. بنابراین تا کنون الگوریتم کارامدی برای یافتن کوچکترین مجموعه غالب پیدا نشده است.

مجموعه‌های غالب (رئوس قرمز).

اشکال a تا c سه نمونه از مجموعه غالب برای گراف داده شده هستند. در هر مثال هر راس سفید با حداقل یک راس قرمز مجاور است، در اصطلاح گفته می‌شود که راس سفید توسط راس قرمز مغلوب شده است. عدد غالب گراف مثال برابر ۲ است. همان طور که در شکل‌های b و c نشان داده شده است مجموعه‌ای غالب با اندازه ۲ وجود دارد و به راحتی می‌توان بررسی کرد که هیچ مجموعه غالبی با یک راس وجود نخواهد داشت.

تاریخچه[ویرایش]

همان‌طور که (Hedetniemi & Laskar (۱۹۹۰ متذکر شده‌اند، مسئله یافتن مجموعه غالب از دهه ۱۹۵۰ به بعد روی کار آمد اما تعداد پژوهش‌ها روی این مسئله در اواسط دهه ۱۹۷۰ به طرز چشمگیری افزایش یافت. فهرست آنها در بیش از ۳۰۰ مقاله مرتبط به این موضوع آمده است.

حدود[ویرایش]

G را یک گراف با n ≥ ۱ راس و با ماکزیمم درجه Δ در نظر بگیرید. نامساوی‌های زیر بر روی (γ(G اثبات شده‌اند:[۱] یک راس حداکثر می‌تواند Δ راس دیگر را مغلوب کند. بنابراین (γ(G) ≥ n / (۱ + Δ.

مجموعه همه راس‌ها در هر گراف یک مجموعه غالب به شمار می‌رود در نتیجه γ(G) ≤ n.

اگر هیچ راس منزوی در گراف G وجود نداشته باشد، آن‌گاه دو مجموعه غالب مجزا برای گراف خواهیم داشت. بنابراین در هر گرافی بدون راس منزوی داریم: γ(G) ≤ n/۲.

مجموعه‌های غالب مستقل[ویرایش]

مجموعه‌های غالب رابطه بسیار نزدیکی با مجموعه‌ی مستقل در گراف دارند. مجموعه مستقل یک مجموعه غالب نیز هست اگر و تنها اگر یک مجموعه مستقل بیشینه باشد. بنابراین هر مجموعه مستقل بیشینه لزوما یک مجموعه غالب کمینه است. پس کوچکترین مجموعه مستقل بیشینه قطعا کوچکترین مجموعه غالب مستقل خواهد بود. اندازه کوچکترین مجموعه غالب مستقل (یا همان طور که گفته شد کوچکترین مجموعه مستقل بیشینه) عدد غالب مستقل یا (i(G گراف G گفته می‌شود.
کوچک‌ترین مجموعه غالب در یک گراف قطعا یک مجموعه مستقل نخواهد بود ولی اندازه آن همیشه کوچکتر یا مساوی اندازه کوچکترین مجموعه مستقل بیشینه خواهد بود یعنی (γ(G) ≤ i(G.
خانواده‌هایی از گراف‌ها وجود دارند که کوچکترین مجموعه مستقل بیشینه آنها با کوچکترین مجموعه غالبشان برابر است. برای مثال (Allan & Laskar (۱۹۷۸ نشان دادند که (γ(G) = i(G اگر گراف G یک گراف Claw-free باشد.
اگر برای همه زیرگرافهای القایی H از G داشته باشیم (γ(H) = i(H آنگاه گراف G کاملا غالب نامیده می‌شود. از آن‌جایی که هر زیر گراف القایی یک گراف claw-free خود نیز claw-free است بنابراین هر گراف claw-free کاملا غالب است (Faudree, Flandrin & Ryjáček 1997).

مثال‌ها[ویرایش]

شکل‌های a و b مجموعه غالب مستقل هستند در حالی‌که در شکل c مجموعه غالب نشان داده شده است یک مجموعه مستقل نیست.

برای هر گراف G گراف خطی آن (L(G یک گراف claw-free خواهد بود. پس کوچکترین مجموعه مستقل بیشینه در (L(G کوچکترین مجموعه غالب در این گراف نیز خواهد بود. یک مجموعه مستقل در (L(G متناظر یک تطابق در گراف G خواهد بود و یک مجموعه غالب در (L(G متناظر یک مجموعه غالب یالی در گراف G است. بنابراین اندازه کوچکترین تطابق بیشینه با کوچکترین مجموعه غالب یالی برابر خواهد بود.

الگوریتم‌ها و پیچیدگی محاسباتی آن‌ها[ویرایش]

بین مسئله یافتن کوچکترین مجموعه غالب و مسئله مجموعه پوشا تعدادی عملیات L - کاهشی در زمان چندجمله‌ای وجود دارد (Kann ۱۹۹۲، صفحات ۱۰۸–۱۰۹). این اعمال کاهشی (که در ادامه تعریف خواهند شد) نشان می‌دهند که یک الگوریتم کارامد برای یافتن کوچکترین مجموعه غالب می‌تواند یک روش کارامد برای یافتن مجموعه پوشا باشد (و بلعکس). هم‌چنین این اعمال کاهشی نسبت تقریب را حفظ می‌کنند: برای هر α یک الگوریتم با تقریب α در زمان چندجمله‌ای برای یافتن کوچکترین مجموعه غالب، یک الگوریتم با تقریب α در زمان چند جمله‌ای را برای یافتن مجموعه پوشا به ما خواهد داد (و بلعکس).
مسئله مجموعه پوشا یک مسئله معروف NP-hard است. نسخه انتخابی یافتن مجموعه پوشا یکی از ۲۱ مسئله NP-COMPLETE کارپ بود که در سال ۱۹۷۲ به عنوان یک مسئله NP_COMPLETE شناخته شدند.
تقریبی بودن مسئله یافتن مجموعه پوشا به خوبی درک شده است. با استفاده از یک الگوریتم حریصانه‌ی ساده یک عامل لگاریتمی تقریبی یافت می‌شود و پیدا کردن یک زیر فاکتور تقریبی لگاریتمی NP-hard است. به صورت دقیق‎تر الگوریتم حریصانه یک ضریب تقریبی برابر با |۱ + log |V برای یافتن کوچکترین مجموعه غالب فراهم می‌کند. (Raz & Safra (۱۹۹۷ نشان دادند که در صورتی که P = NP نباشد آنگاه هیچ الگوریتمی به ضریب تقریبی بهتر از |c log |V به ازای برخی از c > ۰ دست نخواهد یافت.

L-کاهشی[ویرایش]

اعمال کاهشی زیر نشان می‌دهد که مسئله یافتن کوچترین مجموعه غالب و مجموعه پوشا (تحت این عملیات کاهشی) معادل هستند. با داشتن نمونه‌ای از یکی از دو سوال فوق می‌توان به معادل آن در مسئله دیگر دست یافت.

تبدیل از مجموعه غالب به مجموعه پوشا[ویرایش]

برای گراف داده شده (G = (V, E که {V = {۱, ۲, ... , n یک مجموعه پوشا (S, U) را به روش زیر می‌سازیم: U را همان V در نظر گرفته و خانواده‌ای از زیرمجموعه‌های {S = {S1, S2, ... , Sn را می‌سازیم به صورتی که Sv شامل راس v و همه همسایه‌های این راس در گراف G باشد.

حال اگر D یک مجموعه غالب برای گراف G باشد آنگاه {C = {Sv: v ∈ D یک راه‌حل محتمل برای مسئله مجموعه پوشا خواهد بود و داریم |C| = |D|. هم‌چنین اگر {C = {Sv: v ∈ D یک جواب احتمالی برای مسئله مجموعه پوشا باشد آنگاه D یک مجموعه غالب برای گراف G خواهد بود به طوری که |D| = |C|.

بنابراین اندازه کوچک‌ترین مجموعه غالب برای گراف G با اندازه کوچکترین مجموعه پوشا برای (S, U) برابر خواهد بود. علاوه بر این یک الگوریتم ساده برای نگاشتن مجموعه غالب به مجموعه پوشا و بلعکس وجود دارد. به طور خاص یک الگوریتم کارامد با تقریب α برای یافتن مجموعه پوشا منجر به رسیدن به یک الگوریتم کارامد با تقریب α برای یافتن کوچکترین مجموعه غالب خواهد شد (و بالعکس).

برای مثال گراف G در شکل روبرو را در نظر بگیرید. زیر مجموعه‌های S برای مجموعه پوشا (S, U) با {U = {۱, ۲, ... , ۶ را به روش زیر می‌سازیم:

Dominating-set-2.svg


S۱ = {۱, ۲, ۵}, S۲ = {۱, ۲, ۳, ۵}, S۳ = {۲, ۳, ۴, ۶}, S۴ = {۳, ۴},
S۵ = {۱, ۲, ۵, ۶}, S۶ = {۳, ۵, ۶}
در این مثال {D = {۳, ۵ یک مجموعه غالب برای G به شمار می‌رود که در نتیجه {C = {S3, S۵ یک مجموعه پوشا برای گراف خواهد بود. به عنوان مثال راس شماره ۴ توسط راس ۳ مغلوب شده است و عضو U ∈ ۴ در مجموعه S۳ ∈ C قرار دارد.

تبدیل از مجموعه پوشا به مجموعه غالب[ویرایش]

(S, U) را به عنوان یک مثال از مجموعه پوشا با مجموعه مرجع U و خانواده زیرمجموعه‌های {S = {Si: i ∈ I در نظر بگیرید. فرض می‌کنیم U و مجموعه اندیس‌های i مجزا باشند. گراف (G = (V, E را به صورت زیر می‌سازیم:
مجموعه رئوس را V = I ∪ U تعریف می‌کنیم که یک یال i, j} ∈ E} بین هر زوج i, j ∈ I وجود دارد. هم‌چنین یال {i, u} برای هر i ∈ I و u ∈ Si وجود دارد. گراف G به یک خوشه (i) و یک مجموعه مستقل (U) افرازپذیر خواهد بود.
حال اگر {C = {Si: i ∈ D یک راه حل احتمالی به ازای یک زیرمجموعه D ⊆ I برای مسئله مجموعه پوشا باشد آنگاه D یک مجموعه غالب برای G است به طوری که |D| = |C|:
برای هر u ∈ U یک i ∈ D وجود دارد به طوری که u ∈ Si. گراف G را طوری می‌سازیم که u و i در G مجاور باشند. به این ترتیب u توسط i مغلوب خواهد شد. از آنجایی که D باید ناتهی باشد برای هر i ∈ I یک همسایه در D خواهیم داشت.
بلعکس می‌توان گفت که اگر D یک مجموعه غالب برای گراف G باشد آنگاه می‌توان یک مجموعه غالب دیگر به نام X برای گراف تعریف کرد به طوری که |X| ≤ |D| و X ⊆ I. به سادگی هریک از u ∈ D ∩ U را با یک همسایه i ∈ I از u جایگزین می‌کنیم. به این ترتیب {C = {Si: i ∈ X یک جواب محتمل برای مسئله مجموعه پوشا است به طوری که |C| = |X| ≤ |D|.

Dominating-set-reduction.svg

شکل سمت چپ ساختار{ U = {a, b, c, d, e}، I = {۱, ۲, ۳, ۴} ، S۱ = {a, b, c، S۲ = {a, b}، S۳ = {b, c, d} و S۴ = {c, d, e} را نشان می‌دهد.
در این مثال {C = {S1, S۴ یک مجموعه پوشا است که مجموعه غالب {D = {۱, ۴ را نتیجه می‌دهد.
{D = {a, 3, ۴ یک مجموعه غالب دیگر برای گراف G است. با داشتن D می‌توان یک مجموعه غالب {X = {۱, ۳, ۴ را ساخت به طوری که X زیر مجموعه I است و بزرگتر از مجموعه D نیست. مجموعه غالب X، مجموعه‌ی پوشا {C = {S1, S3, S۴ را نتیجه می‌دهد.

حالت‌های خاص[ویرایش]

اگر گراف ماکزیمم درجه Δ داشته باشد. آنگاه الگوریتم تقریبی حریصانه کوچکترین مجموعه غالب را به صورت (O(log Δ-تقریبی پیدا می‌کند. مسئله یک PTAS برای حالتهای خاص گرافهای تک سطحه (unit disk graph) و گرافهای مسطح تعریف می‌کند. کوچکترین مجموعه غالب در زمان خطی برای گرافهای سری موازی (series-parallel) یافت می‌شود.

الگوریتم دقیق[ویرایش]

کوچکترین مجموعه غالب برای یک گراف n راسی در زمان (O(۲nn با در نظر گرفتن همه زیرمجموعه‌های رئوس پیدا خواهد شد. (Fomin, Grandoni & Kratsch (۲۰۰۹ اثبات کردند که این کار در زمان (O(۱٫۵۱۳۷n و با حافظه نمایی و هم‌چنین در زمان (O(۱٫۵۲۶۴n با حافظه چندجمله‌ای انجام خواهد شد. یک الگوریتم سریعتر نیز وجود دارد که همین کار را در زمان (O(۱٫۵۰۴۸n انجام می‌دهد. این الگوریتم توسط (van Rooij, Nederlof & van Dijk (۲۰۰۹ معرفی شده است (آنها هم‌چنین نشان دادند که تعداد کوچکترین مجموعه‌های غالب نیز در همین زمان قابل محاسبه است). تعداد مجموعه‌های غالب کمینه حداکثر ۱٫۷۱۵۹n است و همه این مجموعه‌ها می‌توانند در زمان (O(۱٫۷۱۵۹n مشخص شوند.

پیچیدگی پارامتری کردن[ویرایش]

پیدا کردن یک مجموعه غالب با اندازه K مسئله بسیار مهمی در نظریه پیچیدگی پارامتری کردن است. این مشهورترین مسئله برای کلاس [W[۲ است و در بسیاری از کاهش‌ها برای نشان دادن تعامل با سایر مسائل استفاده می‌شود. به طور خاص این مسئله در شرایطی که هیچ الگوریتمی با زمان اجرای f(k)nO(1) به ازای هر تابع f وجود نداشته باشد پارامتر ثابت و آسان کاربرد (fixed-parameter tractable) نیست. مگر اینکه ارث‌بری W به [FPT=W[۲ تبدیل شود.

از طرف دیگر اگر گراف داده شده دو وجهی باشد مسئله NP-hard باقی می‌ماند اما یک الگوریتم پارامتر ثابت شناخته می‌شود. در حقیقت مسئله دارای شالوده‌ای به اندازه‌ی خطی k است و زمان‌های اجرا در k√ و مکعب n نمایی هستند و امکان دارد از طریق استفاده از برنامه‌نویسی پویا به جای افراز شاخه‌ای شالوده به دست آید.

انواع دیگر[ویرایش]

تخمین vizing عدد غلبه‌ی ضرب دکارتی گرافها را به عدد غالب فاکتورهای آن مرتبط می‌کند. کارهای زیادی روی مجموعه‌های غالب همبند انجام شده است. اگر S یک مجموعه غالب همبند باشد آنگاه می‌توان یک درخت فراگیر روی گراف G ایجاد کرد به طوری که S مجموعه‌ی رئوس غیر برگ را تشکیل دهد و به طور معکوس نیز اگر T یک درخت فراگیر روی یک گراف با بیش از دو راس باشد، آن‌گاه رئوس غیر برگ درخت یک مجموعه غالب همبند را تشکیل می‌دهند. بنابراین یافتن کوچکترین مجموعه غالب همبند با پیدا کردن درخت فراگیر با حداکثر تعداد برگ معادل است.

مجموعه تماما غالب، مجموعه‌ای از رئوس گراف (شامل رئوس موجود در مجموعه غالب) است که دارای یک همسایه در مجموعه غالب هستند. شکل c در بالا یک مجموعه غالب را نشان می‌دهد که هم مجموعه‌ی غالب همبند و هم مجموعه تماما غالب است. در این مثالها شکل a و b هیچ یک از این دو نوع نیستند. بخش‌بندی مسلط (domatic) نوعی بخش‌بندی است که رئوس را به مجموعه‌های غالب مجزا تقسیم می‌کند. عدد تسلط (domatic number) حداکثر اندازه‌ی یک بخش‌بندی مسلط است.

نام گواهی زبان برنامه نویسی توضیحات مختصر
OpenOpt BSD پایتون از گرافهای Networkx استفاده می‌کند، می‌تواند حل کنندگان رایگان و تجاری را به کار برد، رئوس داخلی و خارجی.

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

  1. Haynes, Hedetniemi & Slater 1998a، فصل دوم