Question

mst
shortest_path

ענו על הסעיפים הבאים:

1. תנו דוגמה לגרף G=(V,E)G = (V,E), צומת מקור sVs \in V ופונקציית משקל w:ERw:E \to \mathbb{R} כך שקיים עץ פורש מינימלי TT ועץ מרחקים קלים ביותר PP של GG כך שמשקל העץ PP גדול פי 10 ממשקל העץ TT.

2. תנו דוגמה לגרף G=(V,E)G = (V,E), צומת מקור sVs \in V, צומת יעד vVv \in V ופונקציית משקל w:ERw:E \to \mathbb{R} כך שקיים עץ פורש מינימלי TT ועץ מרחקים קלים ביותר PP של GG כך שמשקל המסלול מ-ss ל-vv ב-TT גדול פי 10 ממשקל המסלול ב-PP.

1

Answers

1. עבור הגרף הבא, משקל עפ"מ הוא 66 בעוד משקל עץ מרחקים קלים ביותר הוא 660.

2. נסתכל על מעגל עם 11 קשתות במשקל 1 ועל עפ"מ שמכיל את כל הקשתות פרט לקשת svsv, אז המרחק מ-ss ל-vv בעפ"מ הוא 10 בעוד המרחק ביניהם הוא 1.

1
Feedback