مجموعه چیره

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

مجموعه چیره یا مجموعه غالب برای گراف (G=(V, E زیرمجموعه‌ای از گره‌هاست به گونه‌ای که هر گره یا درون این مجموعه‌ است یا همسایه‌ای در این مجموعه دارد. شمار گره‌های کوچکترین مجموعه چیره را عدد چیرگی گراف می‌نامیم. یافتن مجموعه چیره‌ای برای گراف G و با عدد چیرگی Y(G) کوچک‌تر از K \in \mathbb{R} پرسمانی ان‌پی سخت است Grandoni (2006). بنابراین تاکنون الگوریتم بهینه‌ای برای یافتن این مجموعه چیره پیدا نشده است.

مجموعه‌های چیره (گره‌های قرمز).

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

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

پژوهش‌ها درباره‌ی مجموعه‌ی چیره از دهه‌ی ۱۹۵۰ آغاز شدند و در میانه‌ی ۱۹۷۰ با به اوج رسیدن پژوهش‌ها بیش از ۳۰۰ جستار در این زمینه نوشته شد. [۱]

کاربردها[ویرایش]

این پرسمان کاربردهای بسیاری در زمینه‌ی مسیریابی و رایانش‌های توزیع‌شده یا خوشه‌ای دارد. برای نمونه در یک شبکه، فرستادنِ پلکانی پیام از خوشه‌ای به خوشه‌ی دیگری می‌تواند از راه سرخوشه‌ها انجام شود. سرخوشه گره‌ای است که مسیریابی درون و میان خوشه‌ای را انجام می‌دهد. پرسش اینجاست که برای چنین شبکه‌ای کدام گره‌ها باید برای سرخوشگی برگزیده شوند تا بتوان از هر خوشه‌ای به خوشه‌ای دیگر پیام فرستاد و هم‌چنین، کم‌ترین سرخوشه‌ها را داشته باشیم. یافتن مجموعه‌ی چیره‌ی کمینه برای چنین شبکه‌ای هم‌ارز است با یافتن کم‌ترین شمار سرخوشه‌ها.

کران‌ها[ویرایش]

برای گراف G دارای n \geq 1 گره‌ و با بیشینه درجه \Delta، نابرابری‌های زیر را برای عدد چیرگی Y(G) داریم:[۲]

  • یک گره‌ می‌تواند دست بالا بر \Delta گره‌‌ی دیگر چیره شود. بنابراین Y(G) \geq \frac{n}{1+\Delta}.
  • مجموعه همه گره‌‌ها در هر گراف یک مجموعه چیره است، از این رو Y(G) \leq n.
  • اگر هیچ گره‌‌ی تنهایی در گراف نباشد، آن‌گاه دو مجموعه چیره‌ی سوا (disjoint) برای گراف خواهیم داشت. بنابراین در هر گرافی بدون گره‌ای تنها داریم Y(G) \leq \frac{n}{2}.

چیرگی ناوابسته[ویرایش]

مجموعه‌های چیره پیوند نزدیکی با مجموعه‌های ناوابسته در گراف دارند. مجموعه‌ای ناوابسته یک مجموعه‌ چیره‌ نیز است اگر و تنها اگر یک مجموعه ناوابسته بیشینه باشد. بنابراین هر مجموعه ناوابسته بیشینه مجموعه‌ای چیره‌ی کمینه است. پس کوچکترین مجموعه ناوابسته بیشینه بی‌گمان کوچک‌ترین مجموعه چیره‌ ناوابسته خواهد بود. اندازه کوچک‌ترین مجموعه چیره‌ ناوابسته (یا همان گونه که گفته شد کوچکترین مجموعه ناوابسته بیشینه) عدد چیرگی‌ ناوابسته نامیده و با i(G) می‌شود.
کوچک‌ترین مجموعه چیره‌ در گرافی بی‌گمان یک مجموعه ناوابسته نخواهد بود ولی اندازه آن همیشه کوچکتر یا برابر اندازه کوچکترین مجموعه ناوابسته بیشینه است: Y(G) \leq i(G).
خانواده‌هایی از گراف‌ها هستند که کوچکترین مجموعه ناوابسته بیشینه آنها با کوچکترین مجموعه چیره‌شان برابر است. برای نمونه (Allan & Laskar (۱۹۷۸ نشان دادند که اگر G گرافی پنجه‌آزاد باشد،‌ داریم i(G)=Y(G).
اگر برای همه زیرگرافهای درهازیده‌ی (induced) H از G داشته باشیم Y(H)=i(H) آنگاه گراف G چیره‌ی فرساخت (perfect) نامیده می‌شود. از آن‌جایی که هر زیر گراف درهاخته (induced) گراف پنجه آزاد خود نیز پنجه‌آزاد است، بنابراین هر گراف پنجه‌آزاد چیره‌ی فرساخت می‌باشد (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۴ را نتیجه می‌دهد.

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

اگر گراف بیشینه درجه \Delta داشته باشد. آنگاه الگوریتم تقریبی حریصانه کوچکترین مجموعه چیره‌ را به صورت (O(log \Delta-تقریبی پیدا می‌کند. پرسمان یک 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, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998b), Domination in Graphs: Advanced Topics, Marcel Dekker, ISBN 0-8247-0034-1, OCLC 38201061 .
  2. Haynes, Hedetniemi & Slater 1998a، فصل دوم