Question

bottleneck
bfs

יהא G=(V,E)G = (V, E) גרף לא מכוון עם משקלות אי-שליליות על הקשתות. יהיו s,tVs,t \in V. עבור מסלול pp ב-GG, צוואר הבקבוק של pp הוא משקל הקשת הקלה ביותר ב-pp.

הציעו אלגוריתם המוצא מסלול בעל צוואר בקבוק מקסימלי מבין כל המסלולים מ-ss ל-tt. על האלגוריתם לרוץ בסיבוכיות זמן של O(ElogV)O(|E| \log |V|).

1

Answers

טענה: המסלול מ-ss ל-tt בעץ פורס מקסימלי של GG הוא בעל צוואר בקבוק מקסימלי.

הוכחה: נסתכל על החתך שנוצר על ידי הסרת צוואר בקבוק במסלול מ-ss ל-tt בעץ פורש המקסימלי ונניח בשלילה שקיים מסלול עם צוואר בקבוק גדול יותר, אז מסלול כזה חייב לחצות את החתך שנוצר (לפחות פעם אחת) משקל קשת שחוצה את החתך גדול ממש ממשקל הקשת שהסרנו - סתירה לכך שהעץ הוא עץ פורש מקסימלי.

כדי למצוא עץ פורש מקסימלי ניתן למצוא עפ"מ על המשקלים הנגדיים למשקלים המקוריים.

1
Feedback