جواب تمرین صفحه 52 درس 2 ریاضیات گسسته (گراف و مدل سازی)

الف

حداقل سه ایستگاه باید نصب شود که می توان آن ایستگاه ها را به صورت\(\left\{ {g\;,\;a\;,\;k} \right\}\)  یا\(\left\{ {f\;,\;d\;,\;j} \right\}\)  یا\(\left\{ {g\;,\;b\;,\;i} \right\}\)  یا\(\left\{ {d\;,\;c\;,\;i} \right\}\)  یا ... انتخاب کرد.

ب

حداقل دو ایستگاه دیگر باید احداث نمود. این دو ایستگاه می تواند\(\left\{ {g\;,\;i} \right\}\)  یا\(\left\{ {f\;,\;k} \right\}\)  یا ... باشد.

ابتدا هر روستا را به عنوان یک رأس گراف (با حرف کوچک انگلیسی) مشخص می کنیم، سپس بین دو رأس (دو روستا) به شرطی یال رسم می کنیم که فاصله ی بین آن دو بیشتر از 10 کیلومتر نباشد.

\(\gamma (G) \ge \left[ {\frac{{15}}{{8 + 1}}} \right] + 1 = 2\)

یک مجموعه احاطه گری می تواند\(\left\{ {c\;,\;m} \right\}\)  باشد، بنابراین کافیست دو بیمارستان در روستاهای\(c\)  و\(m\)  احداث کرد.

الف

\(\gamma (G) \ge \left[ {\frac{8}{{3 + 1}}} \right] = 2\)

مجموعه \(\left\{ {a\;,\;g} \right\}\) یک مجموعه احاطه گری برای آن است؛ بنابراین: \(\gamma (G) = 2\)

ب

\(\gamma (G) \ge \left[ {\frac{{10}}{{4 + 1}}} \right] = 2\)

مجموعه \(\left\{ {e\;,\;j} \right\}\) یک مجموعه احاطه گری برای آن است؛ بنابراین: \(\gamma (G) = 2\)

پ

\(\gamma (G) \ge \left[ {\frac{{12}}{{5 + 1}}} \right] = 2\)

مجموعه \(\left\{ {f\;,\;d\;,\;l} \right\}\) یک مجموعه احاطه گری برای آن است؛ بنابراین: \(\gamma (G) = 2\)  

ت

\(\gamma (G) \ge \left[ {\frac{{19}}{{5 + 1}}} \right] + 1 = 4\)

از طرفی از هر مثلث حداقل یک رأس باید انتخاب کنیم، به عنوان نمونه مجموعه \(\left\{ {f\;,\;i\;,\;k\;,\;l\;,\;e} \right\}\) یک مجموعه احاطه گری برای آن است؛ بنابراین: \(\gamma (G) = 5\)

ث

\(\gamma (G) \ge \left[ {\frac{{20}}{{5 + 1}}} \right] + 1 = 4\)

از طرفی از هر پنج ضلعی حداقل دو رأس باید انتخاب کنیم، لذا 8=2×4 یعنی \(\gamma (G) = 8\) به عنوان نمونه، رئوس قرمز رنگ به عنوان یک مجموعه احاطه گری محسوب می شوند.

حداقل یک رأس با ماکزیمم درجه (رأس فول) وجود دارد. با فرض اینکه گراف دارای\(n \)  رأس باشد، حداقل باید\(n - 1\)  یال داشته باشد که می توان شکل مقابل را برای آن پیشنهاد کرد.

حداقل میزان تعداد یال\(\frac{{n(n - 1)}}{2}\)  می باشد ( حالتی که گراف کامل باشد)، در هر صورت\(\Delta \;(G) = n - 1\)  است.

با توجه به اینکه در هر دو، حداکثر درجه رئوس 2 می باشد، داریم:

\(\gamma \;({P_n}) = \gamma \;({C_n}) = \left[ {\frac{n}{{1 + 2}}} \right] = \left[ {\frac{n}{3}} \right]\)

در گراف \(-k\) منتظم n رأسی، \(\Delta = \delta = k\) می باشد، بنابراین: \(\gamma \;(G) \ge \left[ {\frac{n}{{k + 1}}} \right]\)

\(\gamma \;(G) \ge \left[ {\frac{{12}}{{2 + 1}}} \right] = 4\) ، مجموعه ی\(\left\{ {a\;,\;b\;,\;c\;,\;d} \right\}\)  یک مجموعه ی احاطه گری است، بنابراین عدد احاطه گری آن 4 می باشد:

الف

مجموعه احاطه گری گراف روبرو\(\left\{ a \right\}\)  است.

ب

در گراف مقابل مجموعه احاطه گری\(\left\{ {a\;,\;b} \right\}\)  است.

پ

کافیست گراف را به صورت k بخشی رسم کنیم و در هر بخش رأسی که همه ی رئوس آن بخش را احاطه می کند، در نظر بگیریم.

الف

مجموعه احاطه گری آن \(\left\{ {a\;,\;b} \right\}\) است.

ب

گراف مقابل دارای سه مجموعه ی احاطه گری به اندازه 2 می باشد، که عبارتند از:

 \(\left\{ {a\;,\;d} \right\}\) و \(\left\{ {f\;,\;c} \right\}\) و \(\left\{ {e\;,\;b} \right\}\) 

الف

کافیست مطابق شکل روبرو، یک گراف دو بخشی رسم کنیم به طوری که یک بخش آن شامل k رأس و بخش آن شامل n-k رأس باشد.

ب

مطابق شکل روبرو باید گراف را رسم کرد که دو مجموعه ی احاطه گری آن\(\left\{ {{v_1}\;,\;{v_n}} \right\}\)  و\(\left\{ {{v_1}\;,\;{v_{n - 1}}} \right\}\)  می باشند.

الف

مجموعه\(\left\{ {b\;,\;e\;,\;h\;,\;k} \right\}\)  یک 4- مجموعه است.

ب

مجموعه\(\left\{ {b\;,\;c\;,\;f\;,\;g\;,\;j\;,\;k} \right\}\)  یک مجموعه احاطه گر مینیمال 6 عضوی است.