مجموعه چیره: تفاوت میان نسخهها
ایجاد یک مقاله نو از طریق ایجادگر برچسب: منبعدهی نادرست (پخ) |
(بدون تفاوت)
|
نسخهٔ ۱۱ دسامبر ۲۰۱۳، ساعت ۰۸:۲۶
در نظریه گراف، مجموعه غالب برای گراف (G=(V, E زیرمجموعهای از رئوس به نام D است که به ازای هر راس خارج از D حداقل یک راس مجاور داخل مجموعه خواهیم داشت. تعداد رئوس کوچکترین مجموعه غالب را عدد غالب گراف G یا (γ(G مینامیم.
مسئله یافتن مجموعه غالبی که دارای ویژگی γ(G) ≤ K برای G و K مشخص باشد یک مسئله NP-complete است. بنابراین تا کنون الگوریتم کارامدی برای یافتن کوچکترین مجموعه غالب پیدا نشده است.
اشکال a تا c سه نمونه از مجموعه غالب برای گراف داده شده هستند. در هر مثال هر راس سفید با حداقل یک راس قرمز مجاور است، در اصطلاح گفته میشود
که راس سفید توسط راس قرمز مغلوب شده است. عدد غالب گراف مثال برابر ۲ است. همان طور که در شکلهای b و c نشان داده شده است مجموعهای غالب با اندازه ۲ وجود دارد و به راحتی میتوان بررسی کرد که هیچ مجموعه غالبی با یک راس وجود نخواهد داشت.
تاریخچه
همانطور که (Hedetniemi & Laskar (1990 متذکر شدهاند، مسئله یافتن مجموعه غالب از دهه ۱۹۵۰ به بعد روی کار آمد اما تعداد پژوهشها روی این مسئله در اواسط دهه ۱۹۷۰ به طرز چشمگیری افزایش یافت. فهرست آنها در بیش از ۳۰۰ مقاله مرتبط به این موضوع آمده است.
حدود
G را یک گراف با n ≥ 1 راس و با ماکزیمم درجه Δ در نظر بگیرید. نامساویهای زیر بر روی (γ(G اثبات شدهاند (Haynes, Hedetniemi & Slater 1998a، فصل دوم):
یک راس حداکثر میتواند Δ راس دیگر را مغلوب کند. بنابراین (γ(G) ≥ n / (1 + Δ.
مجموعه همه راسها در هر گراف یک مجموعه غالب به شمار میرود در نتیجه γ(G) ≤ n.
اگر هیچ راس منزوی در گراف G وجود نداشته باشد، آنگاه دو مجموعه غالب مجزا برای گراف خواهیم داشت. بنابراین در هر گرافی بدون راس منزوی داریم: γ(G) ≤ n/2.
مجموعههای غالب مستقل
مجموعههای غالب رابطه بسیار نزدیکی با مجموعهی مستقل در گراف دارند. مجموعه مستقل یک مجموعه غالب نیز هست اگر و تنها اگر یک مجموعه مستقل بیشینه باشد. بنابراین هر مجموعه مستقل بیشینه لزوما یک مجموعه غالب کمینه است. پس کوچکترین مجموعه مستقل بیشینه قطعا کوچکترین مجموعه غالب مستقل خواهد بود. اندازه کوچکترین مجموعه غالب مستقل (یا همان طور که گفته شد کوچکترین مجموعه مستقل بیشینه) عدد غالب مستقل یا (i(G گراف G گفته میشود.
کوچکترین مجموعه غالب در یک گراف قطعا یک مجموعه مستقل نخواهد بود ولی اندازه آن همیشه کوچکتر یا مساوی اندازه کوچکترین مجموعه مستقل بیشینه خواهد بود یعنی (γ(G) ≤ i(G.
خانوادههایی از گرافها وجود دارند که کوچکترین مجموعه مستقل بیشینه آنها با کوچکترین مجموعه غالبشان برابر است. برای مثال (Allan & Laskar (1978 نشان دادند که (γ(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 1992، صفحات 108–109). این اعمال کاهشی (که در ادامه تعریف خواهند شد) نشان میدهند که یک الگوریتم کارامد برای یافتن کوچکترین مجموعه غالب میتواند یک روش کارامد برای یافتن مجموعه پوشا باشد (و بلعکس). همچنین این اعمال کاهشی نسبت تقریب را حفظ میکنند: برای هر α یک الگوریتم با تقریب α در زمان چندجملهای برای یافتن کوچکترین مجموعه غالب، یک الگوریتم با تقریب α در زمان چند جملهای را برای یافتن مجموعه پوششی به ما خواهد داد (و بلعکس).
مسئله مجموعه پوششی یک مسئله معروف NP-hard است. نسخه انتخابی یافتن مجموعه پوششی یکی از ۲۱ مسئله NP-COMPLETE کارپ بود که در سال ۱۹۷۲ به عنوان یک مسئله NP_COMPLETE شناخته شدند.
تقریبی بودن مسئله یافتن مجموعه پوششی به خوبی درک شده است. با استفاده از یک الگوریتم حریصانهی ساده یک عامل لگاریتمی تقریبی یافت میشود و پیدا کردن یک زیر فاکتور تقریبی لگاریتمی NP-hard است. به صورت دقیقتر الگوریتم حریصانه یک ضریب تقریبی برابر با |1 + log |V برای یافتن کوچکترین مجموعه غالب فراهم میکند. (Raz & Safra (1997 نشان دادند که در صورتی که P = NP نباشد آنگاه هیچ الگوریتمی به ضریب تقریبی بهتر از |c log |V به ازای برخی از c > 0 دست نخواهد یافت.
L-کاهشی
اعمال کاهشی زیر نشان میدهد که مسئله یافتن کوچترین مجموعه غالب و مجموعه پوششی (تحت این عملیات کاهشی) معادل هستند. با داشتن نمونهای از یکی از دو سوال فوق میتوان به معادل آن در مسئله دیگر دست یافت.
تبدیل از مجموعه غالب به مجموعه پوششی
برای گراف داده شده (G = (V, E که {V = {1, 2, ..., 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 = {1, 2, ..., 6 را به روش زیر میسازیم:
S1 = {1, 2, 5}, S2 = {1, 2, 3, 5}, S3 = {2, 3, 4, 6}, S4 = {3, 4},
S5 = {1, 2, 5, 6}, S6 = {3, 5, 6}
در این مثال {D = {3, 5 یک مجموعه غالب برای G به شمار میرود که در نتیجه {C = {S3, S5 یک مجموعه پوششی برای گراف خواهد بود. به عنوان مثال راس شماره ۴ توسط راس ۳ مغلوب شده است و عضو U ∈ 4 در مجموعه S3 ∈ 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|.
شکل سمت چپ ساختار{ U = {a, b, c, d, e} ، I = {1, 2, 3, 4} ، S1 = {a, b, c ،
S2 = {a, b} ، S3 = {b, c, d} و S4 = {c, d, e} را نشان میدهد.
در این مثال {C = {S1, S4 یک مجموعه پوششی است که مجموعه غالب {D = {1, 4 را نتیجه میدهد.
{D = {a, 3, 4 یک مجموعه غالب دیگر برای گراف G است.با داشتن D میتوان یک مجموعه غالب {X = {1, 3, 4 را ساخت به طوری که X زیر مجموعه I است و بزرگتر از مجموعه D نیست. مجموعه غالب X، مجموعهی پوششی {C = {S1, S3, S4 را نتیجه میدهد.
حالتهای خاص
اگر گراف ماکزیمم درجه Δ داشته باشد. آنگاه الگوریتم تقریبی حریصانه کوچکترین مجموعه غالب را به صورت (O(log Δ-تقریبی پیدا میکند. مسئله یک PTAS برای حالتهای خاص گرافهای تک سطحه (unit disk graph) و گرافهای مسطح تعریف میکند. کوچکترین مجموعه غالب در زمان خطی برای گرافهای سری موازی (series-parallel) یافت میشود.
الگوریتم دقیق
کوچکترین مجموعه غالب برای یک گراف n راسی در زمان (O(2nn با در نظر گرفتن همه زیرمجموعههای رئوس پیدا خواهد شد. (Fomin, Grandoni & Kratsch (2009 اثبات کردند که این کار در زمان (O(1.5137n و با حافظه نمایی و همچنین در زمان (O(1.5264n با حافظه چندجملهای انجام خواهد شد. یک الگوریتم سریعتر نیز وجود دارد که همین کار را در زمان (O(1.5048n انجام میدهد. این الگوریتم توسط (van Rooij, Nederlof & van Dijk (2009 معرفی شده است (آنها همچنین نشان دادند که تعداد کوچکترین مجموعههای غالب نیز در همین زمان قابل محاسبه است). تعداد مجموعههای غالب کمینه حداکثر 1.7159n است و همه این مجموعهها میتوانند در زمان (O(1.7159n مشخص شوند.
پیچیدگی پارامتری کردن
پیدا کردن یک مجموعه غالب با اندازه K مسئله بسیار مهمی در نظریه پیچیدگی پارامتری کردن است. این مشهورترین مسئله برای کلاس [W[2 است و در بسیاری از کاهشها برای نشان دادن تعامل با سایر مسائل استفاده میشود.به طور خاص این مسئله در شرایطی که هیچ الگوریتمی با زمان اجرای f(k)nO(1) به ازای هر تابع f وجود نداشته باشد پارامتر ثابت و آسان کاربرد ( fixed-parameter tractable) نیست. مگر اینکه ارثبری W به [FPT=W[2 تبدیل شود.
از طرف دیگر اگر گراف داده شده دو وجهی باشد مسئله NP-hard باقی میماند اما یک الگوریتم پارامتر ثابت شناخته میشود. در حقیقت مسئله دارای شالودهای به اندازهی خطی k است و زمانهای اجرا در k√ و مکعب n نمایی هستند و امکان دارد از طریق استفاده از برنامهنویسی پویا به جای افراز شاخهای شالوده به دست آید.
انواع دیگر
تخمین vizing عدد غلبهی ضرب دکارتی گرافها را به عدد غالب فاکتورهای آن مرتبط میکند.کارهای زیادی روی مجموعههای غالب همبند انجام شده است. اگر S یک مجموعه غالب همبند باشد آنگاه میتوان یک درخت فراگیر روی گراف G ایجاد کرد به طوری که S مجموعهی رئوس غیر برگ را تشکیل دهد و به طور معکوس نیز اگر T یک درخت فراگیر روی یک گراف با بیش از دو راس باشد، آنگاه رئوس غیر برگ درخت یک مجموعه غالب همبند را تشکیل میدهند. بنابراین یافتن کوچکترین مجموعه غالب همبند با پیدا کردن درخت فراگیر با حداکثر تعداد برگ معادل است.
مجموعه تماما غالب، مجموعهای از رئوس گراف (شامل رئوس موجود در مجموعه غالب) است که دارای یک همسایه در مجموعه غالب هستند. شکل c در بالا یک مجموعه غالب را نشان میدهد که هم مجموعهی غالب همبند و هم مجموعه تماما غالب است.در این مثالها شکل a و b هیچ یک از این دو نوع نیستند.
بخشبندی مسلط (domatic) نوعی بخشبندی است که رئوس را به مجموعههای غالب مجزا تقسیم میکند.عدد تسلط (domatic number) حداکثر اندازهی یک بخشبندی مسلط است.
نام | گواهی | زبان برنامه نویسی | توضیحات مختصر |
---|---|---|---|
OpenOpt | BSD | پایتون | از گرافهای Networkx استفاده میکند، میتواند حل کنندگان رایگان و تجاری را به کار برد، رئوس داخلی و خارجی. |
منابع
- Alber, Jochen; Fellows, Michael R; Niedermeier, Rolf (2004), "Polynomial-time data reduction for dominating set", Journal of the ACM, 51 (3): 363–384, doi:10.1145/990308.990309.
- Allan, Robert B.; Laskar, Renu (1978), "On domination and independent domination numbers of a graph", Discrete Mathematics, 23 (2): 73–76, doi:10.1016/0012-365X(78)90105-X.
- Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum dominating set", A Compendium of NP Optimization Problems.
- Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics, 164 (1–3): 87–147, doi:10.1016/S0012-365X(96)00045-3, MR 1432221.
- Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms", Journal of the ACM, 56 (5): 25:1–32, doi:10.1145/1552285.1552286.
- Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), "Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications", ACM Transactions on Algorithms, 5 (1): 9:1–17, doi:10.1145/1435375.1435384.
- Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), "Dominating sets in planar graphs: branch-width and exponential speed-up", SIAM Journal on Computing, 36 (2): 281, doi:10.1137/S0097539702419649.
- Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, p. 190, problem GT2.
- Grandoni, F. (2006), "A note on the complexity of minimum dominating set", Journal of Discrete Algorithms, 4 (2): 209–214, doi:10.1016/j.jda.2005.03.002.
- Guha, S.; Khuller, S. (1998), "Approximation algorithms for connected dominating sets", Algorithmica, 20 (4): 374–387, doi:10.1007/PL00009201.
- Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentals of Domination in Graphs, Marcel Dekker, ISBN 0-8247-0033-3, OCLC 37903553.
- Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998b), Domination in Graphs: Advanced Topics, Marcel Dekker, ISBN 0-8247-0034-1, OCLC 38201061.
- Hedetniemi, S. T.; Laskar, R. C. (1990), "Bibliography on domination in graphs and some basic definitions of domination parameters", Discrete Mathematics, 86 (1–3): 257–277, doi:10.1016/0012-365X(90)90365-O.
- Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF). PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm
{{citation}}
: نگهداری CS1: پست اسکریپت (link). - Raz, R.; Safra, S. (1997), "A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP", Proc. 29th Annual ACM Symposium on Theory of Computing, ACM, pp. 475–484, doi:10.1145/258533.258641, ISBN 0-89791-888-6.
- Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), "Linear-time computability of combinatorial problems on series-parallel graphs", Journal of the ACM, 29 (3): 623–641, doi:10.1145/322326.322328.
- van Rooij, J. M. M.; Nederlof, J.; van Dijk, T. C. (2009), "Inclusion/Exclusion Meets Measure and Conquer: Exact Algorithms for Counting Dominating Sets", Proc. 17th Annual European Symposium on Algorithms, ESA 2009, Lecture Notes in Computer Science, vol. 5757, Springer, pp. 554–565, doi:10.1007/978-3-642-04128-0_50, ISBN 978-3-642-04127-3.