שאלה 5 במסלול אלגוריתמים. בסעיף א מריצים את אלגוריתם דייקסטרה על גרף ממושקל G1 ובודקים כיצד שינוי אחיד במשקלי הקשתות (הכפלה או הוספה) משפיע על המסלול הקצר. בסעיף ב, שאין לו קשר לסעיף א, בונים סריקות DFS מקודקוד a על גרף מכוון G שנותנות עצים בגבהים שונים.
שאלה 5 במסלול אלגוריתמים. בסעיף א מריצים את אלגוריתם דייקסטרה על גרף ממושקל G1 ובודקים כיצד שינוי אחיד במשקלי הקשתות (הכפלה או הוספה) משפיע על המסלול הקצר. בסעיף ב, שאין לו קשר לסעיף א, בונים סריקות DFS מקודקוד a על גרף מכוון G שנותנות עצים בגבהים שונים.
עמוד 10, סעיף א: הגרף הממושקל G1
directed weighted graph G1, vertices S, A, B, C, D, T:
S -> A weight 7
S -> B weight 14
S -> C weight 13 (drawn as a long curve below)
A -> B weight 5
A -> T weight 32 (drawn as a long curve above)
B -> C weight 2
C -> T weight 26
C -> D weight 15
D -> T weight 6
עמוד 10, סעיף ב: הגרף המכוון G
directed graph G, vertices a, b, c, d:
a -> b (down-left)
a -> d (down-right)
a -> c (straight down)
d -> c (down-left)
לפניכם גרף ממושקל G1 : [הגרף ב-figures] איזה אלגוריתם מחזיר את המסלול הקצר (הקל) בין שני קודקודים בגרף ממושקל (אי־שלילי) כלשהו? מהי סיבוכיות זמן הריצה של האלגוריתם? נמקו את תשובתכם. נוסף על כך, הריצו את האלגוריתם שכתבתם, בעבור הגרף הנתון G1 , מצומת S לצומת T . בצעו מעקב שלב אחר שלב ורשמו את המסלול ואת אורכו (סכום משקליו).
עבור גרף G ממושקל כלשהו, הרצנו את האלגוריתם המוצא את המסלול הקצר (הקל) בין שני קודקודים, וקיבלנו מסלול העובר דרך הקשתות E(e_i , e_j , e_m , ...) . – האם המסלול הקצר בין שני הקודקודים יישאר בהכרח זהה אם משקל כל אחת מן הקשתות בגרף יוכפל ב־x (x > 1) ? נמקו את תשובתכם. – האם המסלול הקצר בין שני הקודקודים יישאר בהכרח זהה אם משקל כל אחת מן הקשתות בגרף יגדל ב־x (x > 1) ? נמקו את תשובתכם.
לפניכם גרף מכוון G : [הגרף ב-figures] הציגו שתי סריקות DFS מקודקוד התחלה a כך שיתקבלו שני עצים שהגבהים שלהם שונים זה מזה.
הוסיפו מספר מינימלי של קשתות כך שבשלוש סריקות DFS מקודקוד a , יתקבלו שלושה עצים שהגבהים שלהם שונים זה מזה. סרטטו את הגרף לאחר ההוספה, והציגו את שלוש הסריקות.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.