گراف شکافته

در شاخه نظریه گراف از ریاضیات، گراف شکافته  (یا گراف شکافته‌شده)، گرافی است که رئوس آن را می‌توان به یک کلیک و یک مجموعه مستقل افراز نمود. گراف‌های شکافته را اولین بار فولدس و همر مطالعه نموده، و همچنین به‌طور مستقل توسط تیشکویچ و چرنیاک معرفی شدند. had a more general definition, in which the graphs they called split graphs also included bipartite graphs (that is, graphs that be partitioned into two independent sets) and the complements of bipartite graphs (that is, graphs that can be partitioned into two cliques).  use the definition given here, which has been followed in the subsequent literature; for instance, it is , Definition 3.2.3, p.41.

ممکن است گراف شکافته شده بیش از یک افراز به کلیک و مجموعه مستقل داشته باشد؛ به عنوان مثال، مسیر a-b-c گراف شکافته شده‌ای است که رئوس آن را می‌توان به سه روش مختلف افراز نمود:
 کلیک  و مجموعه مستقل 
 کلیک  و مجموعه مستقل 
 کلیک  و مجموعه مستقل 
گراف‌های شکافته شده را می‌توان برحسب زیرگراف های القاء شده ممنوعه شان مشخصه سازی نمود: یک گراف دلخواه شکافته شده‌است اگر و تنها اگر هیچ زیرگراف القاء شده آن که چهار یا پنج رأس داشته یا دارای یک جفت یال مجزا باشد (متمم یک ۴-دور)، دوری نباشد.; , Theorem 6.3, p. 151.

 ارجاعات 



 منابع 

 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .

 .
 . 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, .
 .
 .

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

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

رده:خانواده‌های گراف
رده:رده‌های تقاطعی گراف‌ها
رده:گراف‌های تام