شاه کلید نکات
شاه کلید سوال
1 مشخص کنید کدام یک ازمجموعه های زیر برای گراف شکل 5 احاطه گر هست و کدام نیست؟
الف A = {a, b, c, d, e}
ب B = {f, g, h, I, j}
پ C = {a, b, j, h, g}
ت D = {a, I, h}
ث E = {f, g, h, e, d}
ج F = {f, g, h, e}
چ H = {g, h, e}
الف
احاطه گر هست
ب
احاطه گر هست
پ
احاطه گر نیست
ت
احاطه گر هست
ث
احاطه گر هست
ج
احاطه گر هست
٢ از مجموعه های مطرح شده در سؤال 1 که احاطه گر بودند در کدام یک از آنها رأس یا رأس هایی وجود دارد که با حذف آنها مجموعه باقیمانده هنوز احاطه گر باشد؟
تعریف: یک مجموعه احاطه گر را که با حذف هر یک از رأس هایش دیگر احاطه گر نباشد احاطه گر مینیمال می نامیم.
قسمت ت؛ اگر از مجموعه ی\(E = \left\{ {f\;,\;g\;,\;h\;,\;e\;,\;d} \right\}\) رأس\(d\) را حذف کنیم، مجموعه جدید همان مجموعه\(F = \left\{ {f\;,\;g\;,\;h\;,\;e} \right\}\) بوده که احاطه گر است.
3 مجموعه ای احاطه گر با کمترین تعداد رأس که می توانید، بنویسید و پاسخ خود را با پاسخ هم کلاسی های خود مقایسه کنید.
\(F = \left\{ {c\;,\;j\;,\;f} \right\}\)
4 یک مجموعه احاطه گر مینیمال مشخص کنید که مینیمم نباشد.
\(A = \left\{ {a\;,\;b\;,\;c\;,\;d\;,\;e} \right\}\)
5 آیا می توان هر مجموعه احاطه گر دلخواه غیرمینیمال را با حذف برخی رئوسش به یک مجموعه احاطه گر مینیمال تبدیل کرد؟ (استدلال کنید)
بله؛ اگر\(A = \left\{ {{v_1}\;,\;{v_2}\;,\; \cdots \;,\;{v_n}} \right\}\) یک مجموعه احاطه گر باشد، عضوی مانند v1 را در نظر می کیریم، اگر با حذف آن، هنوز مجموعه احاطه گر باقی ماند، آن را حذف می کنیم، در غیر این صورت آن را نگه داشته و همین کار را برای سایر رئوس انجام می دهیم. با توجه به غیر مینیمال بودنِ مجموعه، قطعاً حداقل یک عضو یافت می شود که با حذف آن، هنوز احاطه گر خواهد ماند.
1736019749.png)
