مقاطع تحصیلی
جستجو در منظومه
2 می‌خواهیم عدد احاطه گر گراف شکل 13 را مشخص نماییم. aالف) ابتدا کران پایین n + 1 ∆ را بررسی می‌کنیم که عدد = 3 14 6 را d bمی‌دهد. پس 3 (≤ γ)G .ب) اما حداقل یکی از رئوس a ، b ، c و d باید انتخاب شود. چرا؟ cپ) حداقل یکی از رئوس f و g باید انتخاب شود. چرا؟ g f eت) حداقل یکی از رئوس i و h باید انتخاب شود. چرا؟ث) حداقل یکی از رئوس m و n باید انتخاب شود. چرا؟ iج) بنابراین حداقل 4 رأس در هر ٔ مجموعه احاطه گر باید باشد. لذا 4 (≤ γ)G و h jبا توجه به اینکه{ c, f, h, m } یک ٔ مجموعه احاطه گر است لذا 4 (≥ γ)G بنابراین k= 4 (γ)G . l m nشکل 13مثال: عدد احاطه گری گراف شکل 14 را به دست آورید و یک ٔ مجموعه احاطه گر a b c dمینیمم برای آن ارائه کنید.حل: برای احاطه کردن رأس a الزم است یکی از دو رأس a و b در ٔ مجموعه e f g hاحاطه گر باشند. به همین صورت یکی از رئوس e و f و نیز یکی از رئوس i و jنیز باید در هر مجموعه احاطه گر باشند. اما این سه رأس انتخاب شده در هر حالت i j k lنمی‌توانند رئوس l, h, d را احاطه کنند. لذا حداقل یک رأس دیگر یعنی حداقل 4 شکل 14رأس برای ٔ احاطه رئوس این گراف الزم است: یعنی 4 ≥ (G γ) از طرفی { b, f, j, h }یک ٔ مجموعه احاطه گراست و لذا 4 ≤ (G γ .) بنابراین داریم = 4 (G γ .)51 درس دوم: مدل سازی با گراف