שאלה על גרף טורניר

[student47]

שאלה על גרף טורניר

גרף (G=(V,E נקרא גרף טורניר אם הוא מתקבל ע"י מתן כיוון (אחד מתוך שניים אפשריים) לכל קשת בגרף מלא, לא מכוון, עם אותה קבוצת קדקדים.

מסלול המילטוני בגרף, הוא מסלול העובר בכל קדקדי הגרף תוך שהוא מבקר בכל קדקד בדיוק עם אחת.

אני צריך לכתוב אלגוריתם יעיל שמחזיר מסלול המילטוני ב"גרף טורניר" הנתון כקלט.

ראשית, יש טענה שאומרת שלכל "גרף טורניר" יש מסלול המילטוני.

ההוכחה מופיעה כאן (ויקיפדיה), ויש לי כמה שאלות לגביה:
http://he.wikipedia.org/wiki/גרף_תחרות

שאלה 1:

T גג הוא גרף תחרות מהסיבה שלאחר השמטת הקדקד v, נשארים עם גרף שבו בין כל 2 קדקדים ישנה קשת עם כיוון?

שאלה 2:

למה מכך שיש מסלול המילטון, ניתן לסדר את כל הקדקדים v0,v1,v2,..,vn-1, כך שכל אחד יופיע פעם אחת והשורה מהווה מסלול מ-v0 ל-vn-1? מי מבטיח שהמסלול ההמילטוני יעבור בין הקדקדים בסדר הזה? v0 אחריו v1 אחריו v2...עד vn-1?

אולי הוא יתחיל ב-v3 אחריו v2 אחריו v5 וכו'..עד vn-1, כשל קדקד מופיע פעם אחת בדיוק?

שאלה 3:

כש"מוסיפים חזרה את v שהשמטנו", חייבים להוסיף אותו בדיוק עם אותן הקשתות שחלו בו בגרף המקורי, ועם אותם שכנים שהיו לו בגרף המקורי?

שאלה 4:

למה מובטח ש-vi-1 מצביע ל-v? הרי ל-v לא בהכרח יש קשתות נכנסות. הניחו בהתחלה שיש לו דרגת יציאה גדולה מאפס, אבל לא הניחו דבר לגבי דרגת הכניסה שלו.

שאלה 5:

אילו vi-1 לא היה מצביע ל-v. כיצד זה סותר את המינימליות של i?

שאלה 6:

כעת לגבי האלגוריתם שמחזיר מסלול המילטוני בגרף טורניר הנתון כקלט.

האם אפשר להשמיט קדקד עם דרגת יציאה גדולה מ-0, לקרוא לפונקציה שמוצאת מסלול המילטוני בגרף שמתקבל, ואז להחזיר את הקדקד לגרף?

כלומר ממש לפי ההוכחה מויקיפדיה?

או שזה קשקוש מוחלט מה שכתבתי? מה עושה פונקציה שמוצאת מסלול המילטוני? איך היא עושה את זה.

המון תודה לעונים

 

[אורי769]

תשובות

1. כן
2. המיספור v0,v1,... הוא מספור שניתן בהתאם למסלול ההימלטוני שקיים. במלים אחרות - ב-T^ יש מסלול המילטוני לפי ההנחה. לכן באופן שרירותי נבחר למספר את הקודקודים של T^ לפי הסדר שהמסלול הזה משרה.
3. כל הקודקודים של T הם שכנים של v. ודאי שכאשר "מחזירים" את v אז זה כולל את הצלעות. רוב הצלעות אינן משנות, כל מה שצריך זה להראות שבעזרת v ניתן להרחיב את המסלול המילטון. זה לב ההוכחה. אני מציע שאם לא הבנת את זה נסה את זה עם דוגמא.
4 ו-5. נכון שלא הניחו דבר על דרגת הכניסה של v. אבל כל קודקוד, ובפרט (v(i-1 יכול לקיים אחת משתים: או שהוא מצביע על v או ש-v מצביע עליו. לפי ההנחה i זה האינדקס המינימלי ש-v מצביע על vi. לכן בהכרח (v(i-1 מצביע על v.
6. כן. ההוכחה הזו היא למעשה אלגוריתם למציאת המסלול.