گراف شکافته

در شاخه نظریه گراف از ریاضیات، گراف شکافته الگو:انگلیسی (یا گراف شکافته‌شده)، گرافی است که رئوس آن را می‌توان به یک کلیک و یک مجموعه مستقل افراز نمود. گراف‌های شکافته را اولین بار فولدس و همر مطالعه نموده، و همچنین به‌طور مستقل توسط تیشکویچ و چرنیاک معرفی شدند.

ممکن است گراف شکافته شده بیش از یک افراز به کلیک و مجموعه مستقل داشته باشد؛ به عنوان مثال، مسیر a-b-c گراف شکافته شده‌ای است که رئوس آن را می‌توان به سه روش مختلف افراز نمود:

1. کلیک $a,b$ و مجموعه مستقل $c$
2. کلیک $b,c$ و مجموعه مستقل $a$
3. کلیک $b$ و مجموعه مستقل $a,c$

گراف‌های شکافته شده را می‌توان برحسب زیرگراف های القاء شده ممنوعه شان مشخصه سازی نمود: یک گراف دلخواه شکافته شده‌است اگر و تنها اگر هیچ زیرگراف القاء شده آن که چهار یا پنج رأس داشته یا دارای یک جفت یال مجزا باشد (متمم یک ۴-دور)، دوری نباشد.

ارجاعات

• الگو:یادکرد-ویکی

منابع

• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation.
• الگو:Citation
• الگو:Citation.
• الگو:Citation. Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), Mathematical notes of the Academy of Sciences of the USSR 48 (6): 1239–1245, الگو:DOI.
• الگو:Citation.
• الگو:Citation.

برای مطالعه بیشتر

• A chapter on split graphs appears in the book by Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs".