گراف آرمانی

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

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

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

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

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

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

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

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

قضیه گراف ایده‌آل (لاسلو لوواس ۱۹۷۲)

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

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

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

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

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

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

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