گراف-ایده‌آل

انگلیسی
نمودار Paley از مرتبه ۹، رنگ شده با سه رنگ و نمایش یک دسته از سه راس. در این گراف و هر یک از زیرگراف‌های القایی آن عدد رنگی برابر است با عدد دسته، پس یک گراف آرمانی است.در تئوری گراف، یک گراف آرمانی گرافی است که رنگ آمیزی گراف هر زیر گراف القایی، برابر سایز بزرگترین گروه آن زیرگراف باشد. در سایه تئوری قوی گراف آرمانی، از سال ۲۰۰۲ می‌دانیم که گراف‌های آرمانی همانند گراف‌های برگ هستند. گراف G یک گراف برگ است اگر خود گراف G یا مکملش یک دورالقایی به طول فرد حداقل ۵ داشته باشد.
گراف‌های آرمانی دربرگیرنده تعداد زیادی دسته‌های مهم گراف‌ها هستند و در یکی کردن نتایج مربوط به رنگ آمیزی‌ها و گروه‌ها در آن دسته‌ها، بکار می‌روند. بعنوان مثال در همه گراف‌های آرمانی مسئله‌ی رنگ آمیزی گراف، مسئله‌ی بزرگترین گروه و مسئله‌ی بزرگترین مجموعه‌ی مستقل همگی در زمان چند جمله‌ای بدست می‌آیند. علاوه بر این، برخی از تئوری‌های مهم کوچکترین-بزرگترین در ترکیبات، مانند تئوری Dilworth می‌توانند در قالب ایده‌آل کردن گراف متناظرشان بیان شوند.
نظریه گراف ایده‌آل از سال ۱۹۵۸ به وسیله Tibor Gallai گسترش پیدا کرد، نتیجه کار او را می‌توان اینگونه تعبیر کرد که مکمل گراف دوبخشی ایده‌آل است؛ این نتیجه نیز می‌تواند به عنوان یک معادل ساده از نظریه König دانست. برآمدی خیلی قدیمی‌تر که با تطابق و پوشش راسی در گراف‌های دو بخشی مرتبط بود. اولین استفاده واژه گراف آرمانی به نظر می‌رسد در یک مقاله ۱۹۶۳ از کلود برگ است و پس از آن گراف برگ نامیده شد. در این مقاله او نتیجه Gallai را با برخی از نتایج مشابه، بوسیله تعریف گراف آرمانی یکی کرد و برابری گراف ایده‌آل و گراف برگ را حدس زد. حدس برگ در سال ۲۰۰۲ بعنوان نظریه‌ی قوی گراف آرمانی ثابت شده است.
خانواده‌ای از گراف‌ها که آرمانی هستند
بعضی از گراف‌های ایده‌آل آشنا‌تر:
گراف دو بخشی: گرافی که می‌تواند با دو رنگ، رنگ آمیزی(گراف) شود؛ مانند درخت (تئوری گراف)، گراف‌های بدون دور.
گراف خطی از گراف‌های دو قسمتی (ر.ک. نظریه کونیگ) گراف رخ (گراف خطی از گراف‌های کامل دو بخشی) یک مورد خاص است.
گراف وتری گرافی که در آن هر دور با طول چهار یا بیشتر یک وتر دارد؛ وتر یالی است که دو راس از دور که بین آنها یالی نیست را به هم وصل می‌کند که شامل جنگل‌ها، درخت‌های k تایی (گراف بیشینه با عرض درخت (treewidth)مشخص)، گراف تقسیم (گرافی است که می‌تواند به یک دسته و یک مجموعه مستقل تقسیم شود) ،گراف بلوکی (گرافی که در آن هر جزء دو اتصال یک دسته است)، گراف فاصله (گرافی که در آن هر راس نشان دهنده یک فاصله از یک خط و هر یال نشان دهنده یک تقاطع ناخالی بین دو فاصله است).
گراف بدیهتا آرمانی (گراف فاصله برای فواصل تو در تو)، گراف آستانه (گرافی است که در آن دو راس مجاور هستند که وزن آنها از مقدار عددی حد آستانه بالاتر باشد) ،گراف آسیاب بادی (با پیوستن دسته‌های مساوی در یک راس مشترک تشکیل می‌شود)، و گراف قویا وتری(strongly chordal) (گرافی که در آن هر دور زوج با طول شش یا بیشتر دارای یک وتر فرد می‌باشد)
گراف‌های مقایسه‌ای که از مجموعه‌های جزئی مرتب شده با اتصال یک جفت از عناصر با یال زمانی که به ترتیب جزئی مربوط هستندمی باشند که شامل گراف دو بخشی، مکمل گراف فاصله، گراف جزئی کامل، گراف آستانه، گراف آسیاب بادی، گراف جایگشت (گرافی که در آن یال نشان دهنده یک جفت از عناصر هستند که توسط یک جایگشت معکوس شده‌اند)، و هم گراف cograph))، گراف‌هایی که‌ها تازه تشکیل شده توسط عملیات بازگشتی مجزا و متمم است.
گراف‌های کاملا ترتیب پذیر: گرافی است که می‌تواند به گونه‌ای باشد که به یک الگوریتم رنگ آمیزی حریصانه مطلوب که در هر گراف القایی است ترتیب دهد. این خدمات عبارتند از گراف دو قسمتی، گراف وتری، گراف مقایسه، گراف فاصله -ارثی (که کوتاه‌ترین فاصله درزیرگراف‌ها ی القایی متصل برابراست با آنهایی که در کل گراف هستند)، و گراف چرخی که دارای عدد فرد از رئوس است.
گراف ذوزنقه، گراف تقاطع ذوزنقه که یک جفت ازیال‌های موازی در دو خط موازی قرار دارند؛ که عبارتند از گراف فاصله زمانی، گراف جزئیات کامل، گراف آستانه، گراف آسیاب بادی. مکمل آنها زیر مجموعه‌ای از گراف مقایسه‌ای است.
ارتباط با قضایای کمترین – بیشترین
در همه گراف‌ها، عدد دسته یک حد پایین برای عدد رنگی فراهم می‌کند؛ چون به همه راس‌ها در یک گروه باید رنگ مجزا و مخصوص تخصیص داده شود. . گراف‌های آرمانی گراف‌هایی هستند که در آن‌ها این کران پائین دقیق است، نه تنها برای خود گراف، بلکه برای هر زیرگراف القائی آن. برای گراف‌هایی که آرمانی نیستند عدد رنگی و عدد دسته می‌تواند متفاوت باشد؛ برای مثال یک دور با طول پنج به سه رنگ در هر رنگ مجزا نیاز دارد اما بزرگترین گروه آن سایز دو دارد.
یک برهانی که کلاسی از گراف‌ها آرمانی هستند می‌تواند همانند نظریه کمترین –بیشترین دیده شود: کمترین تعداد رنگ‌هایی که برای این گراف‌ها لازم است برابر بزرگترین سایز یک دسته است. تعداد زیادی از نظریه‌های مهم کمترین-بیشترین در ترکیبات را می‌توان در این قالب بیان کرد. برای مثال نظریه‌ی دیل ورث (Dilworth) بیان می‌کند که کمترین تعداد زنجیره‌ها در یک ناحیه از مجموعه جزئا مرتب زنجیره‌ها، برابر با بزرگترین سایز ضد زنجیره است و می‌توان اینگونه تعبیر کرد که مکمل‌های گراف‌های قیاسی کامل هستند. نظریه‌ی میرسکی (mirsky) بیان می‌کند که کمترین تعداد ضد زنجیرها در یک ناحیه به تعداد ضد زنجیرها برابر بزرگترین سایز یک زنجیره است همانند آرمانی بودن گراف‌های مقایسه‌ای.
آرمانی بودن گراف‌های جایگشتی برابر است با اینکه در هر رشته از عنصرهای مرتب شده، طول طولانی‌ترین زیررشته‌ی نزولی برابر است با کمترین تعداد رشته‌ها در یک ناحیه رشته‌های صعودی. نظریه اردوس-زکرس ( Erdős–Szekeres) یک نتیجه ساده از این عبارت است.
نظریه‌ی کونیگ (König) در تئوری گراف بیان می‌کند که راس مینیمم در یک گراف دوبخشی تطابق بیشینه را پوشش می‌دهد و بالعکس می‌تواند به عنوان مکمل گراف دوبخشی آرمانی تعبیر شود. نظریه دیگر در مورد گراف‌های دو بخشی این است که رنگ آمیزی یال برابر بیشترین درجه آنها، معادل آرمانی بودن گراف خطی از گراف‌های دو بخشی است.
ویژگی‌ها و نظریه گراف آرمانی
برگ (berge) هنگام بررسی گراف آرمانی دو نظریه مهم در ساختار آن داد که بعدها ثابت شد.
از این دو نظریه، اولی نظریه گراف آرمانی لاواز (Lovász) در ۱۹۷۲ که بیان کرد که یک گراف آرمانی است اگر و تنها اگر مکمل آن آرمانی است؛ بنابراین، آرمانی بودن (برابری حداکثر اندازه دسته و عدد رنگی در هر زیرگراف القایی) معادل برابری حداکثر اندازه مجموعه مستقل و عدد پوشش دسته است.
یک دور با هفت راس و مکمل آن، در هر مورد رنگ آمیزی بهینه و حداکثر دسته (نشان داده شده است با یال‌های سنگین) نشان داده می‌شود. از آنجا که نه گراف تعداد رنگ برابر با سایز دسته استفاده می‌کند، نه ایده‌آل است.نظریه دوم، حدس زده شده توسط برگ، خصوصیات ممنوع گراف برای گراف آرمانی را ارائه می‌کند. دور القایی با طول فرد با اندازه حداقل ۵ یک حفره فرد نامیده می‌شود. یک زیرگراف القایی که مکمل یک حفره فرد است ضدحفره فرد نامیده می‌شود. یک دور فرد با طول بزرگتر از ۳ نمی‌تواند کامل باشد، زیرا عدد رنگی آن سه است و عدد دسته آن دو است. به طور مشابه، مکمل دور فرد با طول 2k + ۱ نمی‌تواند کامل باشد، زیرا عدد رنگی آن k + ۱ است وعدد دسته آن K است. (به عبارتی، این نقص از این گراف از نظریه گراف آرمانی است و نقص کامل بودن دور فرد). از آنجا که این گراف‌ها آرمانی نیستند، هر گراف آرمانی باید یک گراف برگ ، یعنی یک گراف بدون حفره فرد و بدون ضدحفره فرد باشد. برگ برعکس این را حدس زد که هر گراف برگ آرمانی است. این در نهایت به عنوان نظریه گراف قویا آرمانی از چادنفسکی، رابرتسون، سیمور، و توماس (۲۰۰۶) به اثبات رسیده است.
قضیه گراف آرمانی اثبات کوتاهی دارد، اما اثبات قضیه قویا آرمانی طولانی و تکنیکی و برپایه تجزیه ساختاری عمیق گراف برگ است. روش‌های تجزیه‌های مرتبط نیز شروعی برای مطالعه دیگر نمونه‌های گراف به ویژه برای گراف پنجه آزاد شد.
الگوریتم‌ها در گراف کامل
در همه گراف‌های کامل مسئله‌ی رنگ آمیزی گراف‌ها، مشکل بزرگترین دسته و مشکل بزرگترین مجموعه‌ی مستقل همگی در زمان چند جمله‌ای حل می‌شوند. . این الگوریتم برای حالت کلی شامل استفاده از روش بیضی برای برنامه‌ریزی خطی است اما الگوریتم‌های ترکیبی کارآمد‌تری برای بسیاری از موارد خاص شناخته شده است.
برای سال‌های زیادی پیچیدگی شناخت گراف‌های برگ و گراف‌های کامل بازماند. از تعریف گراف‌های برگ فورا این برداشت می‌شود که شناخت آنها در co-NP است (Lovász 1983). نهایتا، پس از اثبات قضیه قوی گراف کامل، یک الگوریتم زمان چندجمله‌ای توسط Chudnovsky, Cornuéjols, Liu, Seymour , Vušković کشف شد.