شاه کلید نکات
شاه کلید سوال
می دانیم در هر گراف، هر رأس خودش و تمام رئوس مجاورش را احاطه می کند.
1 در گراف مقابل ∆ چند است؟
\(\Delta = 3\)
٢ هر رأس حداکثر چند رأس را احاطه می کند و این تعداد چه ارتباطی با ∆ دارد؟
هر رأس خودش و تمام رئوس مجاورش را احاطه می کند، یعنی 4 رأس.
این تعداد همان\(\Delta + 1\) است.
3 آیا 2 رأس می توانند همه رئوس گراف G را احاطه کنند؟
خیر
4 حداقل\(\left[ {\frac{{10}}{4}} \right]\) رأس برای احاطه همه رئوس لازم است. چرا؟
یک رأس آن حداکثر 4 رأس را احاطه می کند. حال اگر رأس دیگری را چنان انتخاب کنبم که رئوس احاطه شده قبلی مجاور آن نباشند، آنگاه این رأس نیز 4 رأس دیگر را احاطه می کند. لذا از بین 10 رأس، 8 رأس احاطه شده اند که باید برای احاطه ی دو رأس باقی مانده از رأس جدیدی استفاده کنیم؛ پس حداقل 3 رأس برای احاطه همه رأس ها نیاز داریم. از طرفی\(\Delta + 1 = [\frac{{10}}{4}] + 1 = 3\) می باشد.
5 (G)γ چند است؟
\(\gamma (G) = 3\)
6 در یک گراف دلخواه با ماکزیمم درجه ∆، یک رأس دلخواه حداکثر چند رأس را احاطه می کند؟
\(\Delta + 1\)
7 تعداد کمتر از\(\left[ {\frac{n}{{\Delta + 1}}} \right]\) رأس نمی توانند تمام n رأس یک گراف را احاطه کنند. چرا؟
یک رأس دلخواه حداکثر\(\Delta + 1\) رأس را احاطه می کند. حال برای تعیین حداقل تعداد رئوسی که تمام \(n\) رأس گراف را احاطه کنند، باید حساب کرد برای جابجایی\(n\) مسافر به چند تاکسی با ظرفیت حداکثر \(\Delta + 1\)
نفر احتیاج داریم. برای این کار نسبت\(\frac{n}{{\Delta + 1}}\) را حساب می کنیم، اگر عدد صحیح شد که جواب می باشد، در غیر این صورت کوچکترین عدد صحیح بعدی آن جواب است تا اینکه تمام رئوس احاطه شده باشند و این همان\(\left[ {\frac{n}{{\Delta + 1}}} \right]\) است
1736019749.png)
