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

در گراف \(G\) مثال قبل، \(\gamma(G)=2\) است، پس باید تمام مجموعه‌های احاطه‌گر دو عضوی را پیدا کنیم.

ابتدا مجموعهٔ احاطه‌گرِ هر رأس را می‌نویسیم (هر رأس خودش و همسایه‌هایش را احاطه می‌کند):

\[N[a]=\{a,b,e\},\quad N[b]=\{a,b,c,d\},\quad N[c]=\{b,c,d\},\quad N[d]=\{b,c,d,e\},\quad N[e]=\{a,d,e\}\]

هیچ رأسی درجهٔ ۴ ندارد، پس با یک رأس نمی‌توان همهٔ رأس‌ها را احاطه کرد و \(\gamma(G)=2\) است. حال تمام دوتایی‌ها را بررسی می‌کنیم:

• \(\{a,b\}\): \(\{a,b,e\}\cup\{a,b,c,d\}=\{a,b,c,d,e\}\) ✔
• \(\{a,c\}\): \(\{a,b,e\}\cup\{b,c,d\}=\{a,b,c,d,e\}\) ✔
• \(\{a,d\}\): \(\{a,b,e\}\cup\{b,c,d,e\}=\{a,b,c,d,e\}\) ✔
• \(\{a,e\}\): \(\{a,b,e\}\cup\{a,d,e\}=\{a,b,d,e\}\) ✘ (رأس \(c\) احاطه نشده است)
• \(\{b,c\}\): \(\{a,b,c,d\}\cup\{b,c,d\}=\{a,b,c,d\}\) ✘ (رأس \(e\) احاطه نشده است)
• \(\{b,d\}\): \(\{a,b,c,d\}\cup\{b,c,d,e\}=\{a,b,c,d,e\}\) ✔
• \(\{b,e\}\): \(\{a,b,c,d\}\cup\{a,d,e\}=\{a,b,c,d,e\}\) ✔
• \(\{c,d\}\): \(\{b,c,d\}\cup\{b,c,d,e\}=\{b,c,d,e\}\) ✘ (رأس \(a\) احاطه نشده است)
• \(\{c,e\}\): \(\{b,c,d\}\cup\{a,d,e\}=\{a,b,c,d,e\}\) ✔
• \(\{d,e\}\): \(\{b,c,d,e\}\cup\{a,d,e\}=\{a,b,c,d,e\}\) ✔

بنابراین گراف \(G\) هفت مجموعهٔ احاطه‌گر مینیمم دارد:

\[\{a,b\},\ \{a,c\},\ \{a,d\},\ \{b,d\},\ \{b,e\},\ \{c,e\},\ \{d,e\}\]