שאלה על מסלול המילטוני
בהינתן גרף מכוון G (חסר מעגלים), אני רוצה לתת אלגוריתם שבודק האם G מכיל מסלול המילטוני.
האם נכון לומר של-G מיון טופולוגי יחיד <=> ב-G קיים מסלול המילטוני?
אנסה להוכיח כיוון אחד קודם כל..
<=:
ב-G קיים מסלול המילטוני: P=v1->v2->...->vn .
צריך להוכיח: ל-G מיון טופולוגי יחיד.
נניח בשלילה של-G יש 2 מיונים טופולוגיים שונים: T1,T2.
מאחר שב-G המסלול ההמילטוני P, אז סדר הופעת הקדקדים ב-P מהווה מיון טופולוגי. כלומר v1,v2,...,vn זה מיון טופולוגי של G, שנסמנו ב-T1.
כי לכל 2 קדקדים vi , vi+1 ב-G (או במילים אחרות: לכל 2 קדקדים ב-P שהוא מסלול המילטוני ולכן מכיל את כל קדקדי G), כך שיש קשת מ-vi ל-vi+1, מתקיים zz f[vi]>f[vi+1] zz (כמסקנה ממשפט הסוגריים?).
שאלה 1: עד כאן, האם מה שכתבתי פה, זו הוכחה נכונה לכך ש-T1 הוא מיון טופולוגי של G?
כעת, מההנחה בשלילה, T2 הוא מיון טופולוגי אחר של G.
שאלה 2: שניי מיונים טופולוגיים הם שונים אם קיימים זוג קדקדים vi,vj ב-G כך שבמיון אחד vi מופיע לפני vj, ובמיון השני vj מופיע לפני vi?
אם התשובה היא כן, אז קיימים איזשהם vi,vj ב-G כך שב-T2 הם מופיעים בסדר הפוך מהסדר שלהם ב-T1.
כלומר בה"כ, ב-T1 הקדקד vi הופיע לפני vj. המסלול P המילטוני ולכן יש מסלול מ-vi ל-vj.
כעת ב-T2 הם מופיעים בסדר הפוך...למה אני לא רואה את הסתירה...? מה בדיוק הסתירה כאן?
אודה מאד למי שיוכל לעזור.
לילה טוב.
בהינתן גרף מכוון G (חסר מעגלים), אני רוצה לתת אלגוריתם שבודק האם G מכיל מסלול המילטוני.
האם נכון לומר של-G מיון טופולוגי יחיד <=> ב-G קיים מסלול המילטוני?
אנסה להוכיח כיוון אחד קודם כל..
<=:
ב-G קיים מסלול המילטוני: P=v1->v2->...->vn .
צריך להוכיח: ל-G מיון טופולוגי יחיד.
נניח בשלילה של-G יש 2 מיונים טופולוגיים שונים: T1,T2.
מאחר שב-G המסלול ההמילטוני P, אז סדר הופעת הקדקדים ב-P מהווה מיון טופולוגי. כלומר v1,v2,...,vn זה מיון טופולוגי של G, שנסמנו ב-T1.
כי לכל 2 קדקדים vi , vi+1 ב-G (או במילים אחרות: לכל 2 קדקדים ב-P שהוא מסלול המילטוני ולכן מכיל את כל קדקדי G), כך שיש קשת מ-vi ל-vi+1, מתקיים zz f[vi]>f[vi+1] zz (כמסקנה ממשפט הסוגריים?).
שאלה 1: עד כאן, האם מה שכתבתי פה, זו הוכחה נכונה לכך ש-T1 הוא מיון טופולוגי של G?
כעת, מההנחה בשלילה, T2 הוא מיון טופולוגי אחר של G.
שאלה 2: שניי מיונים טופולוגיים הם שונים אם קיימים זוג קדקדים vi,vj ב-G כך שבמיון אחד vi מופיע לפני vj, ובמיון השני vj מופיע לפני vi?
אם התשובה היא כן, אז קיימים איזשהם vi,vj ב-G כך שב-T2 הם מופיעים בסדר הפוך מהסדר שלהם ב-T1.
כלומר בה"כ, ב-T1 הקדקד vi הופיע לפני vj. המסלול P המילטוני ולכן יש מסלול מ-vi ל-vj.
כעת ב-T2 הם מופיעים בסדר הפוך...למה אני לא רואה את הסתירה...? מה בדיוק הסתירה כאן?
אודה מאד למי שיוכל לעזור.
לילה טוב.