مقاطع تحصیلی
جستجو در منظومه
روش دیگر برای حل: نوع دیگری از استدالل به این صورت است که باتوجه به کران پایین مطرح شده برای (γ)G و اینکه= 3 (∆)G داریم:(G γ (≤ 4 5 ⇒) G γ) ≤ 1 + n ∆ بنابراین (γ)G ≥ 2 و با توجه به ٔ مجموعه احاطه گر دو عضوی ارائه شده در باال داریم 2 ≥ (γ)G و لذا = 2 (γ .)Gکار در کالس1 تمام γ ــ مجموعه ِ های (مجموعه های احاطه گر مینیمم) گراف G در مثال قبل را بنویسید.2 عدد احاطه گری را برای هر a یک از گراف های زیر مشخص کنید.b ab g a b ab h g c hh f e c hf e d gd gc i j e fc j d e fd HG HG الف(ب(شکل 11فعالیت1 می‌خواهیم عدد احاطه گری گراف شکل 12 را مشخص کنیم.الف) ابتدا می‌بینیم که با توجه به کران پایین n + 1 ∆ برای (γ)G حداقل = 2 8 4 رأس برای a aاحاطه کردن رئوس الزم است اما در مراحل بعدی می‌بینیم که 2 رأس برای احاطه تمام رئوس g g b bاین گراف کافی نیست. c cب) برای احاطه کردن رأس h حداقل یکی از رئوس e یا h باید در ٔ مجموعه احاطه گر باشند و با h h dبودن هر کدام از آنها در ٔ مجموعه احاطه گر، رئوس g, c, b, a کماکان احاطه نشده باقی می‌مانند. e dپ) برای احاطه کردن رئوس g, c, b, a حداقل دو رأس دیگر نیاز هست، زیرا هیچ رأسی به eتنهایی نمی‌تواند هر چهارتای آنها را احاطه کند. f fت) بنابراین حداقل 3 رأس باید در هر ٔ مجموعه احاطه گر از گراف G باشد یعنی 3 (≤ γ . G G)Gث) از طرفی چون { a, c, e } یک ٔ مجموعه احاطه گر است، 3 (≥ γ .)G پس = 3 (γ .)G شکل 12فصل دوم: گراف و مدل سازی 50