گراف آرمانی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو
گراف پلِی از درجهٔ ۹ که با ۳ رنگ، رنگ شده‌است و یک گروهک سه رأسی آن. در این گراف و هر یک از زیرگراف‌های القایی آن، عدد رنگی برابر عدد گروهک است. پس یک گراف آرمانی است.

گراف آرمانی یا گراف ایدئال در نظریهٔ گراف، گرافی است که عدد رنگی هر زیرگراف القایی آن برابر اندازهٔ بزرگترین گروهک آن زیرگراف باشد.

در هر گرافی عدد گروهک کران پایینی از عدد رنگی ارائه می‌کند، زیرا در یک رنگ‌آمیزی صحیح هر یک از رئوس درون گروهک باید رنگ مجزایی داشته باشند. گراف‌های آرمانی گراف‌هایی هستند که در آن‌ها این کران پایین دقیق است، نه‌تنها برای خود گراف، بلکه برای هر زیرگراف القایی آن. برای گراف‌های کلی‌تر عدد رنگی و گروهک می‌توانند متفاوت باشند. مثلاً یک دور به طول ۵ در هر رنگ‌آمیزی صحیح نیازمند ۳ رنگ است، اما اندازهٔ بزرگ‌ترین گروهک آن ۲ است.

گراف آرمانی دربرگیرندهٔ دسته‌های مهمی از گراف‌هاست و این باعث می‌شود که عدد رنگی و اندازهٔ گروهک آن‌ها یکی باشد. به‌عنوان مثال، در همهٔ گراف‌های آرمانی، مسئلهٔ رنگ‌آمیزی گراف، مسئلهٔ بزرگ‌ترین گروهک، مسئلهٔ بزرگ‌ترین مجموعهٔ مستقل، همگی در یک زمان چندجمله‌ای به دست می‌آیند. به‌علاوه قضیه‌های بزرگترین-کوچکترین متعددی درترکیبیات، مانند قضیهٔ Dilworth، می‌توانند در قالب آرمانی کردن گراف‌های متناظرشان بیان شوند.

نظریهٔ گراف آرمانی از سال ۱۹۵۸ توسط Tibor Gallai گسترش پیدا کرد، نتیجهٔ کار او را می‌توان این‌گونه تعبیر کرد که مکمل یک گراف دوبخشی آرمانی است. این نتیجه را می‌توان معادل قضیه کونیگ دانست؛ یک دستاورد خیلی قدیمی‌تر که با تطابق (matching) و پوشش رأسی در گراف‌های دوبخشی مرتبط بود. اولین بار در مقاله‌ای در سال ۱۹۶۳، نوشتهٔ کلود برژ، از اصطلاح «گراف آرمانی» استفاده شد. در این مقاله او گراف آرمانی را تعریف کرد و با این کار، دستاورد Gallai و نتایج متعددی شبیه به آن را یکی کرد. همچنین مشخصه‌های آن را تعریف کرد، که بعدها ثابت شدند و نظریهٔ قوی گراف آرمانی را شکل دادند.

گراف‌های آرمانی مشهور[ویرایش]

مشخصه‌ها و نظریهٔ قوی گراف آرمانی[ویرایش]

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

قضیه گراف آرمانی (لاسلو لوواس، ۱۹۷۲):

یک گراف آرمانی است، اگر و تنها اگر مکمل آن نیز آرمانی باشد.

یک دور القایی با طول فرد حداقل ۵، یک سوراخ فرد نامیده می‌شود. یک زیرگراف القایی که مکمل یک سوراخ فرد باشد یک ضدسوراخ فرد نامیده می‌شود. یک گراف که شامل هیچ سوراخ فرد یا ضدسوراخ فرد نیست یک گراف برژ (Berge) نامیده می‌شود. با توجه به خاصیت نظریهٔ گراف آرمانی، یک گراف آرمانی الزاماً یک گراف بِرگ است؛ اما این که برعکس این هم درست است مدت زیادی ذهن مردم را به خود مشغول کرده بود. این مسئله معروف به تخمین قوی گراف آرمانی بود و در نهایت در سال ۲۰۰۲ به آن جواب مثبت داده شد.

قضیه قوی گراف آرمانی (چادناوسکی، رابرتسون، سیمور، توماس ۲۰۰۲):

یک گراف آرمانی است، اگر و تنها اگر گراف برژ باشد.

از آن‌جا که خیلی از نتایج از روش‌های ساختاری به دست آمده‌اند، اثبات نظریه طولانی و اصولی است. تلاش‌ها برای حل کردن مسئله، باعث ایجاد بینش عمیقی در زمینهٔ نظریهٔ ساختاری گراف شده‌است که در آن مسائل مرتبط زیادی همچنان بی‌پاسخ مانده‌اند. به‌عنوان مثال، مدتی پیش[نیازمند منبع] ثابت شد که مسئلهٔ تشخیص دادن گراف‌های بِرگ متعلق به co-NP است، اما مشخص نبود که آیا متعلق به P نیز هست یا خیر، تا این‌که نظریهٔ قوی گراف‌های آرمانی ثابت شد. (مدت کمی پس از آن الگوریتمی مستقل از نظریهٔ قوی گراف آرمانی، با زمان اجرای چندجمله‌ای توسط ماریا چادناوسکی، ژرارد کورنژول، شینمینگ لیو، پال سیمور، و کریستینا ووشکویچ کشف شد.)

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

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