جواب فعالیت صفحه ۵۰ ریاضیات گسسته

حل:

الف) ابتدا کران پایین را حساب می‌کنیم. در این گراف \(n=8\) و بیشترین درجه \(\Delta=3\) است (رأس‌های \(c\) و \(e\) هر کدام سه همسایه دارند). پس
\[\left\lceil \frac{8}{3+1} \right\rceil = \left\lceil \frac{8}{4} \right\rceil = 2\]
یعنی \(\gamma(G)\ge 2\). اما در ادامه می‌بینیم که با دو رأس نمی‌توان همهٔ رأس‌ها را احاطه کرد.

ب) برای احاطه کردن رأس \(h\) باید حداقل یکی از رأس‌های \(e\) یا \(h\) در مجموعهٔ احاطه‌گر باشد، چون فقط این دو رأس \(h\) را احاطه می‌کنند. با انتخاب هر کدام از آن‌ها، رأس‌های \(a\)، \(b\)، \(c\) و \(g\) هنوز احاطه نشده‌اند.

پ) رأس‌های \(a\)، \(b\)، \(c\) و \(g\) یک چهارضلعی تشکیل می‌دهند، اما هیچ رأسی از گراف به‌تنهایی هر چهار رأس را احاطه نمی‌کند. پس برای احاطه کردن این چهار رأس حداقل دو رأس دیگر لازم است.

ت) بنابراین در هر مجموعهٔ احاطه‌گر از گراف \(G\) حداقل ۳ رأس باید باشد، یعنی \(\gamma(G)\ge 3\).

ث) از طرف دیگر، مجموعهٔ \(\{a,c,e\}\) احاطه‌گر است: رأس \(a\) رئوس \(a,b,g\) را، رأس \(c\) رئوس \(b,c,d,g\) را و رأس \(e\) رئوس \(d,e,f,h\) را احاطه می‌کند و همهٔ ۸ رأس پوشش داده می‌شوند. پس \(\gamma(G)\le 3\).

در نتیجه
\[\gamma(G)=3\]