מסלול המילטוני בגרף הוא מסלול העובר בכל צומת בגרף בדיוק פעם אחת. בגרף מלא G בלתי מכוון עם n צמתים קיימים s מסלולים המילטונים זרים בקשתות שביחד עוברים בכל קשת ב-G בדיוק פעם אחת. האם n זוגי או אי-זוגי?
אשמח להסבר כיצד לגשת לשאלות בנושא מסלול המילטוני.
כל מסלול המילטוני עובר בכל צומת בדיוק פעם אחת. מאחר וקיימים n צמתים בגרף, נוכל להסיק כי המסלול מכיל בדיוק n-1 קשתות. מאחר והמסלולים זרים בקשתות, נוכל להסיק כי s המסלולים עוברים ב- s(n-1) קשתות. נתון כי המסלולים עוברים בכל הקשתות ב-G ולכן ב-G יש בדיוק s(n-1) קשתות. כמו כן, נתון כי גרף G מלא ולא מכוון. לכן יש בדיוק C_{n}^{2} קשתות.
סה"כ קיבלנו את המשוואה הבאה:
\begin{align*}
C_{n}^{2}=s(n-1)&\Leftrightarrow{n \choose 2}=s(n-1)\\&\Leftrightarrow\frac{n!}{2!\cdot(n-2)!}=s(n-1)\\&\Leftrightarrow n=2s
\end{align*}
לכן, נוכל להסיק כי מספר הצמתים הוא זוגי.
לייק 1