زیرگراف ها¶

زیر گراف القایی¶

زیرگراف القایی یک زیر گراف است که رئوسش یک زیر مجموعه از رئوس گراف اصلی و یال هایش تمام یال های میان آن رئوس است. هر گراف \(n\) راسی، \(2^n\) زیرگراف القایی دارد.

زیرگراف فراگیر¶

زیرگراف فراگیر یک زیرگراف است که رئوسش تمام رئوس گراف و یال هایش یک زیر مجموعه دلخواه از یال ها باشد. هر گراف \(m\) یالی، \(2^m\) زیرگراف فراگیر دارد.

چند نکته¶

• تنها زیرگراف فراگیر القایی، خود گراف است.
• تعداد زیرگراف های یک گراف بستگی به شکل گراف دارد

افراز گراف¶

منظور از افراز گراف، ارائه چند زیرگراف است به طوری که یال های این زیر گراف ها اشتراک نداشته باشند و همه یال های گراف پوشانده شده باشند. به عبارت دیگر هر یال از گراف دقیقا در یک زیرگراف آمده باشد. به افراز می توانید مانند دسته بندی یا رنگ آمیزی یال ها نگاه کنید. شکل زیر، افراز گراف \(K_4\) به دو گراف \(P_4\) است:

عدد استقلال و عدد خوشه ای¶

بزرگ ترین زیر گراف القایی که هیچ یالی نداشته باشد، بزرگترین مجموعه مستقل نامیده می شود و به اندازه راس های آن، عدد استقلال گراف می گویند و آن را با \(\alpha\) یا \(\alpha (G)\) نمایش می دهند. (حرف یونانی آلفا خوانده می شود)

بزرگ ترین زیر گراف القایی که بین هر دو راسش یال باشد و به عبارتی دیگر یک گراف کامل باشد، بزرگترین خوشه‌ی گراف نامیده می شود و به اندازه راس های آن، عدد خوشه ای گراف می گویند و آن را با \(\omega\) یا \(\omega (G)\) نمایش می دهند. (حرف یونانی اومگا خوانده می شود)

این دو تعریف تعاریف مهمی هستند و مسائل جالبی حول آن ها مطرح می شود.