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

در گراف شکل ۵ هر رأس با رأس‌های زیر مجاور است. هر رأس را همراه با همسایه‌هایش در نظر می‌گیریم:

• \(a: b, e, f\)
• \(b: a, c, g\)
• \(c: b, d, h\)
• \(d: c, e, i\)
• \(e: a, d, j\)
• \(f: a, h, i\)
• \(g: b, i, j\)
• \(h: c, f, j\)
• \(i: d, f, g\)
• \(j: e, g, h\)

برای هر مجموعه بررسی می‌کنیم که آیا هر رأس یا خودش در مجموعه است یا با یکی از اعضای مجموعه مجاور است.

الف) \(A=\{a,b,c,d,e\}\) احاطه‌گر است. زیرا \(f\) با \(a\)، \(g\) با \(b\)، \(h\) با \(c\)، \(i\) با \(d\) و \(j\) با \(e\) مجاور است.

ب) \(B=\{f,g,h,i,j\}\) احاطه‌گر است. زیرا \(a\) با \(f\)، \(b\) با \(g\)، \(c\) با \(h\)، \(d\) با \(i\) و \(e\) با \(j\) مجاور است.

پ) \(C=\{a,b,j,h,g\}\) احاطه‌گر نیست. رأس \(d\) نه در \(C\) است و نه با رأسی از \(C\) مجاور است، چون همسایه‌های \(d\) یعنی \(c\)، \(e\) و \(i\) هیچ‌کدام در \(C\) نیستند.

ت) \(D=\{a,i,h\}\) احاطه‌گر است. زیرا \(b\) و \(e\) و \(f\) با \(a\)، \(c\) و \(j\) با \(h\)، \(d\) و \(g\) با \(i\) مجاور هستند.

ث) \(E=\{f,g,h,e,d\}\) احاطه‌گر است. زیرا \(a\) با \(f\)، \(b\) با \(g\)، \(c\) با \(h\)، \(i\) با \(f\) و \(j\) با \(e\) مجاور است.

چ) \(F=\{f,g,h,e\}\) احاطه‌گر است. زیرا \(a\) با \(f\)، \(b\) با \(g\)، \(c\) با \(h\)، \(d\) با \(e\)، \(i\) با \(f\) و \(j\) با \(e\) مجاور است.

ح) \(H=\{g,h,e\}\) احاطه‌گر است. زیرا \(a\) با \(e\)، \(b\) با \(g\)، \(c\) با \(h\)، \(d\) با \(e\)، \(f\) با \(h\)، \(i\) با \(g\) و \(j\) با \(e\) مجاور است.

نتیجه: مجموعه‌های \(A\)، \(B\)، \(D\)، \(E\)، \(F\) و \(H\) احاطه‌گر هستند و مجموعهٔ \(C\) احاطه‌گر نیست.