Question

mst

משאית בגובה xx לא יכולה לעבור מתחת לגשר שגובהו פחות מ-xx. לחברת משלוחים יש צי משאיות בגבהים שונים והיא ממוקמת בנקודה aa. כדי להגיע מנקודה aa לנקודה bb יש לעבור, כתלות במסלול שנבחר, מתחת למספר גשרים בדרך. החברה מעוניינת לדעת לכל נקודה bb עבורה היא מבצעת משלוח, מה הגובה המקסימלי האפשרי עבור משאית כך שהיא תוכל להגיע מנקודה aa לנקודה bb.

פורמלית:

בהינתן גרף לא מכוון, G=(V,E)G = (V, E), ופונקציית מגבלת גובה על הקשתות, h:ER+h:E \to \mathbb{R^+}, קשת במסלול PP תקרא צוואר בקבוק אם גובהה הוא הנמוך ביותר מבין כל קשתות המסלול.

בהינתן צומת ss אנו רוצים למצוא עץ מסלולים, TT, מ-ss לשאר צמתי הגרף כך שגובה צוואר הבקבוק בכל מסלול הוא הגדול ביותר האפשרי.

א. מצאו עץ מסלולים בגרף הבא, מ-ss לשאר צמתי הגרף כך שגובה צוואר הבקבוק בכל מסלול הוא הגדול ביותר האפשרי.

tikz

ב. תארו אלגוריתם שבהינתן גרף לא מכוון, G=(V,E)G = (V, E), פונקציית מגבלת גובה על הקשתות, h:ER+h:E \to \mathbb{R^+}, וצומת ss מוצא עץ מסלולים, TT, מ-ss לשאר צמתי הגרף כך שגובה צוואר הבקבוק בכל מסלול הוא הגדול ביותר האפשרי. על האלגוריתם לרוץ בזמן O(ElogV)O(E \log V)בנוסף לעץ המסלולים, האלגוריתם צריך לחשב מהו גובה צוואר הבקבוק עבור כל צומת בגרף.

יש להוכיח נכונות ולנתח סיבוכיות.

1

Answers

No answers yet ¯\_(ツ)_/¯
Feedback