شاه کلید نکات
شاه کلید سوال
در استان مرکزی، در نزدیکی شهر محلات، سه روستای خورهه، آبگرم و حاجی آباد وجود دارد. اگر بخواهیم جاده هایی بین این سه روستا طراحی کنیم، به طوری که پس از تکمیل راه ها، هیچ روستایی تنها نماند (حداقل به یک روستای دیگر وصل باشد) به چند طریق می توان چنین راه هایی را طراحی کرد؟
اگر روستاها را K، A و H بنامیم، در این صورت یافتن تعداد چنین راه هایی معادل است با پیدا کردن تعدادی گراف های ساده که با سه رأس K، A و H می توان تعریف کرد به طوری که در آنها هیچ رأسی تنها نباشد.
1 از چهار گراف ساده زیر کدام ها مورد نظرند و کدام ها را نباید شمرد؟
گراف های (ب) و (ت) را نباید شمرد؛ زیرا یک رأس تنها می ماند.
٢ کل جاده های بین سه روستا یعنی کل گراف های ممکن که با سه رأس می توان تعریف کرد برابر است با:
\(\left| S \right| = {2^{\left( {\scriptstyle3\atop\scriptstyle2} \right)}} = \;...\)
(بین هر دو روستا از این سه روستا می توان یک جاده درنظر گرفت که هر جاده می تواند در طراحی ما، باشد یا نباشد.)
\(\left| S \right| = {2^{\left( {\scriptstyle3\atop\scriptstyle2} \right)}} = \;{2^3} = 8\)
٣ اگر Ak را مجموعه راه های طراحی شده ای که در آنها روستای K تنها بماند تعریف کنیم، به همین صورت Aa و Ah را تعریف کنید و با استفاده از نتیجه اصل شمول جواب را بیابید و گراف های متناظر با آنها را رسم کنید.
\(\begin{array}{l}\left. \begin{array}{l}\left| {{A_k}} \right| = \left| {{A_a}} \right| = \left| {{A_h}} \right| = 2\\\left| {{A_k} \cap {A_a}} \right| = \left| {{A_a} \cap {A_h}} \right| = \left| {{A_k} \cap {A_h}} \right| = 1\\\left| {{A_k} \cap {A_a} \cap {A_h}} \right| = 1\end{array} \right\}\\\\ \Rightarrow \left| {\overline {{A_k}} \cap \overline {{A_a}} \cap \overline {{A_h}} } \right| = \left| {\overline {{A_k} \cup {A_a} \cup {A_h}} } \right|\\ = \left| S \right| - \left| {{A_k} \cup {A_a} \cup {A_h}} \right|\\\\ \Rightarrow \left| {\overline {{A_k}} \cap \overline {{A_a}} \cap \overline {{A_h}} } \right| = 8 - (2 + 2 + 2 - 1 - 1 - 1 + 1) = 4\end{array}\)
٤ توضیح دهید که چرا تساوی های زیر برقرارند؟
الف \(\left| {{A_k}} \right| = \left| {{A_a}} \right| = \left| {{A_h}} \right| = 2\)
ب \(\left| {{A_k} \cap {A_a}} \right| = \left| {{A_k} \cap {A_h}} \right| = \left| {{A_a} \cap {A_h}} \right| = 1\)
پ \(\left| {{A_k} \cap {A_a} \cap {A_h}} \right| = 1\)
الف
یکی از روستاها را کنار گذاشته و فقط بین دو روستای دیگر می تواند یک جاده باشد یا نباشد؛ لذا 2 حالت داریم.
ب
یک رأس مانده و فقط یک حالت داریم و آن گراف تهی است.
پ
تمام رئوس بدون یال هستند (بین روستاها جاده نیست) که گراف تهی بوده و فقط یک حالت محسوب می شود.
1736019749.png)
