گراف آرمانی. گراف های دوبخشی
گراف های خطی گراف های دوبخشی
گراف های بازه ای (رأس ها نشان دهندهٔ بازه های خطی هستند و یال ها بازهٔ مشترک هر دو رأس)
گراف های وتری (هر دور با بیشتر از ۳ رأس یک وتر دارد، که یالی است بین دو رأس غیرمجاور در دور)
گراف فاصله-ارثی
گراف های جایگشت
گراف های ذوزنقه ای
گراف های قیاسی (یک رأس در ازای هم عضو یک مجموعهٔ منظم جزئی، و یک یال بین هر دو عضو قابل قیاس)
گراف های چرخی
گراف های انشعابی (گراف هایی که می توان آنها را به دو بخش تقسیم کرد. یک گروهک و یک مجموعهٔ مستقل)
گراف مینیل (هر دور به طول فرد بزرگتر از ۳، حداقل ۲ وتر داشته باشد)
گراف آرمانی یا گراف ایدئال در نظریهٔ گراف، گرافی است که عدد رنگی هر زیرگراف القایی آن برابر اندازهٔ بزرگترین گروهک آن زیرگراف باشد.
در هر گرافی عدد گروهک کران پایینی از عدد رنگی ارائه می کند، زیرا در یک رنگ آمیزی صحیح هر یک از رئوس درون گروهک باید رنگ مجزایی داشته باشند. گراف های آرمانی گراف هایی هستند که در آن ها این کران پایین دقیق است، نه تنها برای خود گراف، بلکه برای هر زیرگراف القایی آن. برای گراف های کلی تر عدد رنگی و گروهک می توانند متفاوت باشند. مثلاً یک دور به طول ۵ در هر رنگ آمیزی صحیح نیازمند ۳ رنگ است، اما اندازهٔ بزرگ ترین گروهک آن ۲ است.
گراف آرمانی دربرگیرندهٔ دسته های مهمی از گراف هاست و این باعث می شود که عدد رنگی و اندازهٔ گروهک آن ها یکی باشد. به عنوان مثال، در همهٔ گراف های آرمانی، مسئلهٔ رنگ آمیزی گراف، مسئلهٔ بزرگ ترین گروهک، مسئلهٔ بزرگ ترین مجموعهٔ مستقل، همگی در یک زمان چندجمله ای به دست می آیند. به علاوه قضیه های بزرگترین-کوچکترین متعددی درترکیبیات، مانند قضیهٔ Dilworth، می توانند در قالب آرمانی کردن گراف های متناظرشان بیان شوند.
گراف های خطی گراف های دوبخشی
گراف های بازه ای (رأس ها نشان دهندهٔ بازه های خطی هستند و یال ها بازهٔ مشترک هر دو رأس)
گراف های وتری (هر دور با بیشتر از ۳ رأس یک وتر دارد، که یالی است بین دو رأس غیرمجاور در دور)
گراف فاصله-ارثی
گراف های جایگشت
گراف های ذوزنقه ای
گراف های قیاسی (یک رأس در ازای هم عضو یک مجموعهٔ منظم جزئی، و یک یال بین هر دو عضو قابل قیاس)
گراف های چرخی
گراف های انشعابی (گراف هایی که می توان آنها را به دو بخش تقسیم کرد. یک گروهک و یک مجموعهٔ مستقل)
گراف مینیل (هر دور به طول فرد بزرگتر از ۳، حداقل ۲ وتر داشته باشد)
گراف آرمانی یا گراف ایدئال در نظریهٔ گراف، گرافی است که عدد رنگی هر زیرگراف القایی آن برابر اندازهٔ بزرگترین گروهک آن زیرگراف باشد.
در هر گرافی عدد گروهک کران پایینی از عدد رنگی ارائه می کند، زیرا در یک رنگ آمیزی صحیح هر یک از رئوس درون گروهک باید رنگ مجزایی داشته باشند. گراف های آرمانی گراف هایی هستند که در آن ها این کران پایین دقیق است، نه تنها برای خود گراف، بلکه برای هر زیرگراف القایی آن. برای گراف های کلی تر عدد رنگی و گروهک می توانند متفاوت باشند. مثلاً یک دور به طول ۵ در هر رنگ آمیزی صحیح نیازمند ۳ رنگ است، اما اندازهٔ بزرگ ترین گروهک آن ۲ است.
گراف آرمانی دربرگیرندهٔ دسته های مهمی از گراف هاست و این باعث می شود که عدد رنگی و اندازهٔ گروهک آن ها یکی باشد. به عنوان مثال، در همهٔ گراف های آرمانی، مسئلهٔ رنگ آمیزی گراف، مسئلهٔ بزرگ ترین گروهک، مسئلهٔ بزرگ ترین مجموعهٔ مستقل، همگی در یک زمان چندجمله ای به دست می آیند. به علاوه قضیه های بزرگترین-کوچکترین متعددی درترکیبیات، مانند قضیهٔ Dilworth، می توانند در قالب آرمانی کردن گراف های متناظرشان بیان شوند.
wiki: گراف آرمانی