شاه کلید نکات
شاه کلید سوال
1 یک شبکه رایانه ای متشکل از 16 رایانه را در نظر بگیرید که در آن هر رایانه، مطابق شکل 9 به چند رایانه دیگر متصل است.
گراف شکل 9 یک مدلسازی از شبکه مورد نظر است که در آن هر رأس نمایشگر یک رایانه است و یال بین دو رأس نمایانگر آن است که رایانه های نظیر به آن دو رأس مستقیما با هم در ارتباط اند. می خواهیم مجموعه ای با کمترین تعداد ممکن از رایانه ها (رأس ها) انتخاب کنیم. به طوری که توسط این مجموعه از رایانه ها به تمام رایانه های این شبکه وصل باشیم. مجموعه انتخاب شده از رئوس برای گراف مورد نظر چه نوع مجموعه ای است؟
مجموعه احاطه گر مینیمم.
٢ با توجه به رابطه\(\left[ {\frac{n}{{\Delta + 1}}} \right] \le \gamma \left( G \right)\) حداقل چند رأس برای احاطه کردن تمام رئوس این گراف لازم است؟ آیا می توانید مجموعه ای احاطه گر با این تعداد رأس مشخص نمایید؟
\(\left[ {\frac{{16}}{{4 + 1}}} \right] + 1 = 4\)
\(\left\{ {a\;,\;b\;,\;c\;,\;d} \right\}\)
٣ گراف های C10 , P9 , P10 و C9 را رسم کنید و عدد احاطه گری هر یک را مشخص نمایید.
4 گرافی مشخص کنید که برای آن عدد احاطه گر برابر\(\left[ {\frac{n}{{\Delta + 1}}} \right]\) باشد.
در گراف\({P_9}\) عدد احاطه گری\(\left[ {\frac{9}{{2 + 1}}} \right] = 3\) است.
٥ گرافی مشخص کنید که برای آن عدد احاطه گر برابر\(\left[ {\frac{n}{{\Delta + 1}}} \right]\) باشد.
\(\left\{ {{v_2}\;,\;{v_4}\;,\;{v_6}\;,\;{v_8}\;,\;{v_{11}}} \right\}\) =مجموعه احاطه گر مینیمم
\( \Rightarrow \gamma (G) = 5 \ne \left[ {\frac{{11}}{4}} \right] + 1\)
1736019749.png)
