موضوع مقاله: مجموعه چیره | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مجموعه چیره | مقدمه: مجموعه چیره یا مجموعه غالب یا مجموعه احاطه‌گری برای گراف (G=(V, E زیرمجموعه‌ای از گره‌هاست به گونه‌ای که هر گره یا درون این مجموعه است یا همسایه‌ای در این مجموعه دارد. | ## بخش 1: مجموعه چیره | یافتن مجموعه چیره‌ای برای گراف و با عدد چیرگی کوچک‌تر از مسئله ای ان‌پی سخت است . هم‌چنین، به آسانی می‌توان نشان داد که هیچ‌یک از مجموعه‌های تک گره‌ای چیره نیستند. تاریخچه پژوهش‌ها دربارهٔ مجموعهٔ چیره از دههٔ ۱۹۵۰ آغاز شدند و در میانهٔ ۱۹۷۰ با به اوج رسیدن پژوهش‌ها بیش از ۳۰۰ جستار در این زمینه نوشته شد.. کاربردها این مسئله کاربردهای بسیاری در زمینهٔ مسیریابی و رایانش‌های توزیع‌شده یا خوشه‌ای دارد. برای نمونه در یک شبکه، فرستادنِ پلکانی پیام از خوشه‌ای به خوشهٔ دیگری می‌تواند از راه سرخوشه‌ها انجام شود. پرسش اینجاست که برای چنین شبکه‌ای کدام گره‌ها باید برای سرخوشگی برگزیده شوند تا بتوان از هر خوشه‌ای به خوشه‌ای دیگر پیام فرستاد و هم‌چنین، کم‌ترین سرخوشه‌ها را داشته باشیم. یافتن مجموعهٔ چیرهٔ کمینه برای چنین شبکه‌ای هم‌ارز است با یافتن کم‌ترین شمار سرخوشه‌ها. اگر هیچ گرهٔ تنهایی در گراف نباشد، آن‌گاه دو مجموعه چیرهٔ سوا (disjoint) برای گراف خواهیم داشت؛ بنابراین در هر گرافی بدون گره‌ای تنها داریم . چیرگی ناوابسته مجموعه‌های چیره پیوند نزدیکی با مجموعه‌های ناوابسته در گراف دارند. مجموعه‌ای ناوابسته یک مجموعه چیره نیز است اگر و تنها اگر یک مجموعه ناوابسته بیشینه باشد؛ بنابراین هر مجموعه ناوابسته بیشینه مجموعه‌ای چیرهٔ کمینه است. پس کوچکترین مجموعه ناوابسته بیشینه بی‌گمان کوچک‌ترین مجموعه چیره ناوابسته خواهد بود. اندازه کوچک‌ترین مجموعه چیره ناوابسته (یا همان گونه که گفته شد کوچکترین مجموعه ناوابسته بیشینه) عدد چیرگی ناوابسته نامیده و با می‌شود. کوچک‌ترین مجموعه چیره در گرافی بی‌گمان یک مجموعه ناوابسته نخواهد بود ولی اندازه آن همیشه کوچکتر یا برابر اندازه کوچکترین مجموعه ناوابسته بیشینه است: . خانواده‌هایی از گراف‌ها هستند که کوچکترین مجموعه ناوابسته بیشینه آنها با کوچکترین مجموعه چیره‌شان برابر است. نمونه‌ها شکل‌های a و b مجموعه چیره ناوابسته هستند در حالی‌که در شکل c مجموعه چیره نشان داده شده است یک مجموعه ناوابسته نیست. پس کوچکترین مجموعه ناوابسته بیشینه در (L(G کوچکترین مجموعه چیره در این گراف نیز خواهد بود. یک مجموعه ناوابسته در (L(G متناظر یک تطابق در گراف G خواهد بود و یک مجموعه چیره در (L(G متناظر یک مجموعه چیره یالی در گراف G است؛ بنابراین اندازه کوچکترین تطابق بیشینه با کوچکترین مجموعه چیره یالی برابر خواهد بود. | ## بخش 2: مجموعه چیره | الگوریتم‌ها و پیچیدگی محاسباتی آن‌ها بین مسئله یافتن کوچکترین مجموعه چیره و مسئله مجموعه پوشا شماری عملیات L - کاهشی در زمان چندجمله‌ای وجود دارد (Kann ۱۹۹۲، صفحات ۱۰۸–۱۰۹). این اعمال کاهشی (که در ادامه تعریف خواهند شد) نشان می‌دهند که یک الگوریتم کارامد برای یافتن کوچکترین مجموعه چیره می‌تواند یک روش کارامد برای یافتن مجموعه پوشا باشد (و بلعکس). هم‌چنین این اعمال کاهشی نسبت تقریب را حفظ می‌کنند: برای هر α یک الگوریتم با تقریب α در زمان چندجمله‌ای برای یافتن کوچکترین مجموعه چیره، یک الگوریتم با تقریب α در زمان چند جمله‌ای را برای یافتن مجموعه پوشا به ما خواهد داد (و بلعکس). با استفاده از یک الگوریتم حریصانهٔ ساده یک عامل لگاریتمی تقریبی یافت می‌شود و پیدا کردن یک زیر فاکتور تقریبی لگاریتمی NP-hard است. به صورت دقیق‌تر الگوریتم حریصانه یک ضریب تقریبی برابر با |۱ + log |V برای یافتن کوچکترین مجموعه چیره فراهم می‌کند. 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) برابر خواهد بود. علاوه بر این یک الگوریتم ساده برای نگاشتن مجموعه چیره به مجموعه پوشا و بلعکس وجود دارد. به گونه ویژه یک الگوریتم کارامد با تقریب α برای یافتن مجموعه پوشا منجر به رسیدن به یک الگوریتم کارامد با تقریب α برای یافتن کوچکترین مجموعه چیره خواهد شد (و بالعکس). زیر مجموعه‌های S برای مجموعه پوشا (S, U) با {U = {۱, ۲, … , ۶ را به روش زیر می‌سازیم: left S1 = {۱, ۲, ۵}, S2 = {۱, ۲, ۳, ۵}, S3 = {۲, ۳, ۴, ۶}, S4 = {۳, ۴}, S5 = {۱, ۲, ۵, ۶}, S6 = {۳, ۵, ۶} در این نمونه {D = {۳, ۵ یک مجموعه چیره برای G به شمار می‌رود که در نتیجه {C = {S3, S۵ یک مجموعه پوشا برای گراف خواهد بود. به عنوان نمونه گره شماره ۴ توسط گره ۳ مغلوب شده است و عضو U ∈ ۴ در مجموعه S۳ ∈ C قرار دارد. تبدیل از مجموعه پوشا به مجموعه چیره (S, U) را به عنوان یک نمونه از مجموعه پوشا با مجموعه مرجع U و خانواده زیرمجموعه‌های {S = {Si: i ∈ I در نظر بگیرید. بلعکس می‌توان گفت که اگر D یک مجموعه چیره برای گراف G باشد آنگاه می‌توان یک مجموعه چیره دیگر به نام X برای گراف تعریف کرد به گونه‌ای که |X| ≤ |D| و X ⊆ I. | ## بخش 3: مجموعه چیره | در این مثال {C = {S1, S۴ یک مجموعه پوشا است که مجموعه چیره {D = {۱, ۴ را نتیجه می‌دهد. با داشتن D می‌توان یک مجموعه چیره {X = {۱, ۳, ۴ را ساخت به گونه‌ای که X زیر مجموعه I است و بزرگتر از مجموعه D نیست. آنگاه الگوریتم تقریبی حریصانه کوچکترین مجموعه چیره را به صورت (O(log -تقریبی پیدا می‌کند. الگوریتم دقیق کوچکترین مجموعه چیره برای یک گراف n گرهٔ در زمان (O(2nn با در نظر گرفتن همه زیرمجموعه‌های رئوس پیدا خواهد شد. یک الگوریتم سریعتر نیز وجود دارد که همین کار را در زمان (O(1.5048n انجام می‌دهد. شمار مجموعه‌های چیره کمینه حداکثر ۱٫۷۱۵۹n است و همه این مجموعه‌ها می‌توانند در زمان (O(1.7159n مشخص شوند. پیچیدگی پارامتری کردن پیدا کردن یک مجموعه چیره با اندازه K مسئله بسیار مهمی در نظریه پیچیدگی پارامتری کردن است. این مشهورترین مسئله برای کلاس [W[۲ است و در بسیاری از کاهش‌ها برای نشان دادن تعامل با سایر مسائل استفاده می‌شود. از طرف دیگر اگر گراف داده شده دو وجهی باشد مسئله NP-hard باقی می‌ماند اما یک الگوریتم پارامتر ثابت شناخته می‌شود. در حقیقت مسئله دارای شالوده‌ای به اندازۀ خطی k است و زمان‌های اجرا در k√ و مکعب n نمایی هستند و امکان دارد از طریق استفاده از برنامه‌نویسی پویا به جای افراز شاخه‌ای شالوده به دست آید. گونه‌های دیگر تخمین vizing عدد غلبۀ ضرب دکارتی گرافها را به عدد چیرگی فاکتورهای آن مرتبط می‌کند. اگر S یک مجموعه چیره همبند باشد آنگاه می‌توان یک درخت فراگیر روی گراف G ایجاد کرد به گونه‌ای که S مجموعۀ گره‌های نابرگ را تشکیل دهد و به گونه وارون نیز اگر T یک درخت فراگیر روی یک گراف با بیش از دو گره باشد، آن‌گاه گره‌های نا برگ درخت یک مجموعه چیره همبند را تشکیل می‌دهند. بنابراین یافتن کوچکترین مجموعه چیره همبند با پیدا کردن درخت فراگیر با بیشینۀ شمار برگ معادل است. مجموعه تماماً چیره، مجموعه‌ای از گره‌های گراف (شامل گره‌های موجود در مجموعه چیره) است که دارای یک همسایه در مجموعه چیره هستند. شکل c در بالا یک مجموعه چیره را نشان می‌دهد که هم مجموعۀ چیره همبند و هم مجموعه تماماً چیره است. | ## جمع‌بندی | بخش‌بندی مسلط (domatic) نوعی بخش‌بندی است که گره‌های را به مجموعه‌های چیره مجزا تقسیم می‌کند.