חישוביות 2025 סימסטר א - תרגיל 1 - שאלה 3 - רדוקצייה עצמית למסלול המילטון
Вставка
- Опубліковано 24 лис 2024
- בקשר לשאלה על הפיתרון האלטרנטיבי שהועלה בסרטון-
מסתבר שאכן אפשר לעשות משהו כזה: להסיר בכל פעם קשת שגם בלעדיה יש מסלול המילטוני בגרף, עד שמגיעים לגרוף שרשרת של קשותות שמהוות חלק ממסלול המילטוני יחיד. גרף כזה ניתן בקלות להמיר לסדרה של קודקודים המייצגים את (סדר) המסלול ההמילטוני.
היי אשמח לשאול על הדרך השניה שכתבת בתיאור איך כדאי להסביר במילים על המעבר על הגרף שקיבלנו בשביל לקבל סדר של קודקודים ככה שזה ייחשב פורמלי? תודה רבה
@@מעייןאיפרגן
לאחר שהסרנו את כל הקשתות שלא שותפות באף מסלול המילטוני, נבחר מן הגרף קודקוד שדרגת הכניסה שלו מינימלית (אם הגרף מכוון, יהיה קודקוד אחד שדרגת הכניסה שלו 0 ולכל שאר הקודקודים תהיה דרגת כניסה בדיוק 1, אם זה גרף לא מכוון, יהיו בגרף שני קודקודים שלכל אחד מחוברת רק צלע אחת, בעוד שלשאר הקודקודים מחוברות שתי צלעות, נוכל לבחור את אחד מתוך שני הקודקודים).
נשים לב שהגרף שקיבלנו הוא גרף שרשרת, ז.א שנוכל לטייל עליו כך שבכל צעד ישנה רק אפשרות אחת לאיזה קודקוד לעבור. ההילוך על המסלול שמתחיל בקודקוד שבחרנו הוא המסלול ההמילטוני, ונחזיר את רשימת הקודקודים בסדר של ההילוך שביצענו.