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

خانواده‌ای از گراف‌ها که آرمانی هستند

بعضی از گراف‌های ایده‌آل آشنا تر:
گراف دو بخشی: گرافی که می‌تواند با دو رنگ، رنگ آمیزی(گراف) شود؛ مانند درخت (تئوری گراف)، گراف‌های بدون دور.
گراف خطی از گراف‌های دو قسمتی (ر.ک. نظریه کونیگ) گراف رخ (گراف خطی از گراف‌های کامل دو بخشی) یک مورد خاص است.
گراف وتری گرافی که در آن هر دور با طول چهار یا بیشتر یک وتر دارد؛ وتر یالی است که دو رأس از دور که بین آن‌ها یالی نیست را به هم وصل می‌کند که شامل جنگل‌ها، درخت‌های k تایی (گراف بیشینه با عرض درخت (treewidth)مشخص)، گراف تقسیم (گرافی است که می‌تواند به یک دسته و یک مجموعه مستقل تقسیم شود) ،گراف بلوکی (گرافی که در آن هر جزء دو اتصال یک دسته است)، گراف فاصله (گرافی که در آن هر راس نشان دهنده یک فاصله از یک خط و هر یال نشان دهنده یک تقاطع ناخالی بین دو فاصله است).
گراف بدیهتا آرمانی (گراف فاصله برای فواصل تو در تو)، گراف آستانه (گرافی است که در آن دو راس مجاور هستند که وزن آن‌ها از مقدار عددی حد آستانه بالاتر باشد) ،گراف آسیاب بادی (با پیوستن دسته‌های مساوی در یک رأس مشترک تشکیل می‌شود)، و گراف قویا وتری(strongly chordal) (گرافی که در آن هر دور زوج با طول شش یا بیشتر دارای یک وتر فرد می‌باشد)
گراف‌های مقایسه‌ای که از مجموعه‌های جزئی مرتب شده با اتصال یک جفت از عناصر با یال زمانی که به ترتیب جزئی مربوط هستندمی‌باشند که شامل گراف دو بخشی، مکمل گراف فاصله، گراف جزئی کامل، گراف آستانه، گراف آسیاب بادی، گراف جایگشت (گرافی که در آن یال نشان دهنده یک جفت از عناصر هستند که توسط یک جایگشت معکوس شده‌اند)، و هم گراف cograph))، گراف‌هایی که‌ها تازه تشکیل شده توسط عملیات بازگشتی مجزا و متمم است.
گراف‌های کاملاً ترتیب پذیر: گرافی است که می‌تواند به گونه‌ای باشد که به یک الگوریتم رنگ آمیزی حریصانه مطلوب که در هر گراف القایی است ترتیب دهد. این خدمات عبارتند از گراف دو قسمتی، گراف وتری، گراف مقایسه، گراف فاصله -ارثی (که کوتاه‌ترین فاصله درزیرگراف‌ها ی القایی متصل برابراست با آنهایی که در کل گراف هستند)، و گراف چرخی که دارای عدد فرد از رئوس است.
گراف ذوزنقه، گراف تقاطع ذوزنقه که یک جفت ازیال‌های موازی در دو خط موازی قرار دارند؛ که عبارتند از گراف فاصله زمانی، گراف جزئیات کامل، گراف آستانه، گراف آسیاب بادی. مکمل آن‌ها زیر مجموعه‌ای از گراف مقایسه‌ای است.

ارتباط با قضایای کمترین – بیشترین

در همهٔ گراف‌ها، عدد دسته یک حد پایین برای عدد رنگی فراهم می‌کند؛ چون به همهٔ راس‌ها در یک گروه باید رنگ مجزا و مخصوص تخصیص داده شود. . گراف‌های آرمانی گراف‌هایی هستند که در آن‌ها این کران پائین دقیق است، نه تنها برای خود گراف، بلکه برای هر زیرگراف القائی آن. برای گراف‌هایی که آرمانی نیستند عدد رنگی و عدد دسته می‌تواند متفاوت باشد؛ برای مثال یک دور با طول پنج به سه رنگ در هر رنگ مجزا نیاز دارد اما بزرگترین گروه آن سایز دو دارد.
یک برهانی که کلاسی از گراف‌ها آرمانی هستند می‌تواند همانند نظریهٔ کمترین –بیشترین دیده شود: کمترین تعداد رنگ‌هایی که برای این گراف‌ها لازم است برابر بزرگترین سایز یک دسته است. تعداد زیادی از نظریه‌های مهم کمترین-بیشترین در ترکیبات را می‌توان در این قالب بیان کرد. برای مثال نظریه ی دیل ورث (Dilworth) بیان می‌کند که کمترین تعداد زنجیره‌ها در یک ناحیه از مجموعه جزئاً مرتب زنجیره‌ها، برابر با بزرگترین سایز ضد زنجیره است و می‌توان اینگونه تعبیر کرد که مکمل‌های گراف‌های قیاسی کامل هستند. نظریه ی میرسکی (mirsky) بیان می‌کند که کمترین تعداد ضد زنجیرها در یک ناحیه به تعداد ضد زنجیرها برابر بزرگترین سایز یک زنجیره است همانند آرمانی بودن گراف‌های مقایسه‌ای.
آرمانی بودن گراف‌های جایگشتی برابر است با اینکه در هر رشته از عنصرهای مرتب شده، طول طولانی‌ترین زیررشته ی نزولی برابر است با کمترین تعداد رشته‌ها در یک ناحیه رشته‌های صعودی. نظریه اردوس-زکرس ( Erdős–Szekeres) یک نتیجه ساده از این عبارت است.
نظریه ی کونیگ (König) در تئوری گراف بیان می‌کند که راس مینیمم در یک گراف دوبخشی تطابق بیشینه را پوشش می‌دهد و بالعکس می‌تواند به عنوان مکمل گراف دوبخشی آرمانی تعبیر شود. نظریه دیگر در مورد گراف‌های دو بخشی این است که رنگ آمیزی یال برابر بیشترین درجه آنها، معادل آرمانی بودن گراف خطی از گراف‌های دو بخشی است.

ویژگی‌ها و نظریه گراف آرمانی

برگ (berge) هنگام بررسی گراف آرمانی دو نظریه مهم در ساختار آن داد که بعدها ثابت شد.
از این دو نظریه، اولی نظریه گراف آرمانی لاواز (Lovász) در ۱۹۷۲ که بیان کرد که یک گراف آرمانی است اگر و تنها اگر مکمل آن آرمانی است؛ بنابراین، آرمانی بودن (برابری حداکثر اندازه دسته و عدد رنگی در هر زیرگراف القایی) معادل برابری حداکثر اندازه مجموعه مستقل و عدد پوشش دسته است.
نظریه دوم، حدس زده شده توسط برگ، خصوصیات ممنوع گراف برای گراف آرمانی را ارائه می‌کند. دور القایی با طول فرد با اندازه حداقل ۵ یک حفره فرد نامیده می‌شود. یک زیرگراف القایی که مکمل یک حفره فرد است ضدحفره فرد نامیده می‌شود. یک دور فرد با طول بزرگتر از ۳ نمی‌تواند کامل باشد، زیرا عدد رنگی آن سه است و عدد دسته آن دو است. به‌طور مشابه، مکمل دور فرد با طول 2k + ۱ نمی‌تواند کامل باشد، زیرا عدد رنگی آن k + ۱ است وعدد دسته آن K است. (به عبارتی، این نقص از این گراف از نظریه گراف آرمانی است و نقص کامل بودن دور فرد). از آنجا که این گراف‌ها آرمانی نیستند، هر گراف آرمانی باید یک گراف برگ، یعنی یک گراف بدون حفره فرد و بدون ضدحفره فرد باشد. برگ برعکس این را حدس زد که هر گراف برگ آرمانی است. این در نهایت به عنوان نظریه گراف قویا آرمانی از چادنفسکی، رابرتسون، سیمور، و توماس (۲۰۰۶) به اثبات رسیده‌است.
قضیه گراف آرمانی اثبات کوتاهی دارد، اما اثبات قضیه قویا آرمانی طولانی و تکنیکی و برپایه تجزیه ساختاری عمیق گراف برگ است. روش‌های تجزیه‌های مرتبط نیز شروعی برای مطالعه دیگر نمونه‌های گراف به ویژه برای گراف پنجه آزاد شد.

الگوریتم‌ها در گراف کامل

در همهٔ گراف‌های کامل مسئله ی رنگ آمیزی گراف‌ها، مشکل بزرگترین دسته و مشکل بزرگترین مجموعه ی مستقل همگی در زمان چند جمله‌ای حل می‌شوند. (Grötschel, Lovász & Schrijver 1988). این الگوریتم برای حالت کلی شامل استفاده از روش بیضی برای برنامه‌ریزی خطی است اما الگوریتم‌های ترکیبی کارآمد تری برای بسیاری از موارد خاص شناخته شده‌است.
برای سال‌های زیادی پیچیدگی شناخت گراف‌های برگ و گراف‌های کامل بازماند. از تعریف گراف‌های برگ فوراً این برداشت می‌شود که شناخت آن‌ها در co-NP است (Lovász 1983). نهایتاً، پس از اثبات قضیه قوی گراف کامل، یک الگوریتم زمان چندجمله‌ای توسط Chudnovsky, Cornuéjols, Liu, Seymour , Vušković کشف شد.