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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
نمودار 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 است . ( به عبارتی، این نقص از این گراف از نظریه گراف آرمانی است و نقص کامل بودن دور فرد ) . از آنجا که این گراف‌ها آرمانی نیستند ، هر گراف آرمانی باید یک گراف برگ ، یعنی یک گراف بدون حفره فرد و بدون ضدحفره فرد باشد. برگ برعکس این را حدس زد که هر گراف برگ آرمانی است. این در نهایت به عنوان نظریه گراف قویا آرمانی از چادنفسکی ، رابرتسون ، سیمور، و توماس (۲۰۰۶) به اثبات رسیده است.

قضیه گراف آرمانی اثبات کوتاهی دارد، اما اثبات قضیه قویا آرمانی طولانی و تکنیکی و برپایه تجزیه ساختاری عمیق گراف برگ است. روش‌های تجزیه‌های مرتبط نیز شروعی برای مطالعه دیگر نمونه‌های گراف به ویژه برای گراف پنجه آزاد شد.

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

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

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

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