5 , 8 מציאת המסלולים הקצרים ביותר בין כל הזוגות עד כה הכרנו שיטות למציאת מסלולים קצרים ביותר מקדקוד מקור יחיד . בסעיף זה נכיר שיטות שונות למציאת מסלולים קצרים ביותר בין כל זוגות הקדקודים בגרף . ב . הוכיחו , אס בגרף מכוון אציקלי יש מסלול המילטון , נניח , ( vj , v , ..., v ) אז 2 n יש לו מיון טופולוגי יחיד ( כלומר ו סידור אחד ויחיד של הקדקודיס מהווה מיון טופולוגי חוקי . ( ג . אם ידוע שלגרף יש לו מיון טופולוגי יחיד , האם נובע מכך שיש מסלול המילטון ? הוכיחו או הראו דוגמאות נגדיות . ד . כתבו אלגוריתם יעיל למציאת מסלול המילטון בגרף מכוון אציקלי . האלגוריתם נדרש למצוא מסלול כזה , אם ישנו , או להודיע שלא קיים מסלול כזה , אם איננו . שאלה 5 . 30 ( רשות ) נתון גרף מכוון . כמה זמן דרוש למציאת כל הצמתים שמכל אחד מהם ניתן להגיע אל כל צומתי הגרף ? הוכיחו את תשובתכם . שאלה 5 . 31 ( רשות ) א . הוכיחו כי הגרף המכוון G אינו מכיל מעגלים אס ורק אם DFS ( G ) אינו מניב קשתות לאחור . ב . האם האלגוריתם מיון טופולוגי יוצר יחס כזה 1 / M