Question

mst
winter_15-16_a
shortest_path

הוכיחו/הפריכו:

א. נתון G=(V,E)G = (V,E) גרף לא מכוון ופונקציית משקל w:ERw:E \to \mathbb{R}. אם ב-GG יש מעגל, אזי הקשת הכי קלה בו מופיעה בהכרח בכל עפ"מ.

ב. נתון G=(V,E)G=(V,E) גרף לא מכוון פונקציית משקל w:ERw: E \to \mathbb{R} כך שאין שתי קשתות במשקל זהה. אזי, מסלול בן זוג צמתים בעפ"מ הוא בהכרח הקל ביותר בגרף GG.

1

Answers

א. הטענה לא נכונה, למשל בגרף הבא, הקשת במשקל 2 לא נמצאת באף עפ"מ.

ב. הטענה לא נכונה, למשל בגרף הבא משקל המסלול הקל ביותר מ-3 ל-1 בגרף הוא 4 ובעפ"מ הוא 5.

1
Feedback