یک زیرگراف فراگیر یک زیرگراف است که تمام رئوس نمودار اصلی را در بر می گیرد. درخت پوشا یک زیرگراف فراگیر است که اغلب مورد توجه است. یک چرخه در یک نمودار که شامل تمام رئوس نمودار باشد، یک چرخه پوشا نامیده می شود.
چند زیرگراف فراگیر وجود دارد؟
2n زیرگراف القایی (همه زیرمجموعه های رئوس) و 2m زیرگراف پوشا وجود دارد (همه زیرمجموعه یال ها).
چگونه یک زیرگراف فراگیر پیدا کنم؟
و طبق تعریف زیرگراف فراگیر یک گراف G یک زیرگراف است که فقط با حذف یال به دست می آید. اگر با حذف یک یال، دو یال، سه یال و غیره زیر مجموعه یال ها را بسازیم. همانطور که m لبه وجود دارد، 2^m زیر مجموعه نیز وجود دارد. بنابراین G دارای 2^m زیرگراف فراگیر است.
منظور از پوشاندن درخت چیست؟
درخت پوشاننده یک نمودار (G) زیرمجموعه ای از G است که تمام رئوس آن را با استفاده از حداقل تعداد یال ها پوشش می دهد. برخی از ویژگی های درخت پوشا را می توان از این تعریف استنباط کرد: از آنجایی که "یک درخت پوشا تمام رئوس را می پوشاند"، نمی توان آن را قطع کرد.
نظریه گراف فراگیر چیست؟
یک درخت پوشا زیرمجموعه ای از نمودار G است که همه رئوس آن با حداقل تعداد ممکن یال پوشیده شده است. بنابراین، یک درخت پوشا چرخه ندارد و نمی توان آن را قطع کرد. با این تعریف، می توان نتیجه گرفت که هر نمودار G متصل و غیر جهت دار حداقل یک درخت پوشا دارد.
