Question

spring_9_b
shortest_path

יהא G=(V,E)G = (V,E) גרף מכוון עם משקלות חיוביות על הקשתות w:ER+w:E \to \mathbb{R}^+, ויהא sVs \in V. תהא f:VRf:V \to \mathbb{R}. נאמר כי ff היא פונקציית מסלולים קלים ביותר מ-ss אם לכל vVv \in V מתקיים ש-f(v)f(v) הוא משקל המסלול הקל ביותר מ-ss ל-vv ב-GG.

א. הוכיחו את הטענה הבאה: ff היא פונקציית מסלולים קלים ביותר מ-ss אם ורק אם

  • f(s)=0f(s) = 0
  • לכל vV{s}v \in V \setminus \{s\} מתקיים f(v)=minuvE(f(u)+w(uv))f(v) = \displaystyle{\min_{uv \in E}} (f(u) + w(uv)).

ב. הציעו אלגוריתם יעיל ככל שתוכלו, המקבל גרף כמתואר לעיל ופונקציה ff ומכריע האם ff היא פונקצית מסלולים קלים ביותר מ-ss. הוכיחו את נכונות האלגוריתם ונתחו סיבוכיות.

1

Answers

א. אם ff פונקציית מסלולים קלים ביותר ו-ww פונקציה חיובית (ממש) אז שני התנאים מתקיימים מתכונות מסלולים קלים ביותר.

מצד שני, אם ff מקיימת את שני התנאים אז:

טענה: ff היא חסם תחתון למשקל המסלול הקל ביותר.

הוכחה: באינדוקציה על מספר הקשתות, kk, במסלול קל ביותר לצומת vv.

בסיס: עבור k=0k = 0 הטענה מתקיימת.

עבור צומת vv ומסלול קל ביותר s,,vk,vs, \ldots, v_k, v לפי הנחת האינדוקציה מתקיים f(vk)d(s,vk)d(s,v)f(v_k) \leq d(s, v_k) \leq d(s, v) ו- f(v)f(vk)+w(vkv)d(s,v)f(v) \leq f(v_k) + w(v_kv) \leq d(s, v).

טענה: ff היא חסם עליון למשקל המסלול הקל ביותר.

הוכחה: נניח בשלילה שזה לא המצב ונסתכל על תת הגרף שמכיל את כל הצמתים כך ש-f(v)<d(s,v)f(v) < d(s, v) ואת הקשתות המתאימות, כלומר argminuvEf(v)+w(uv)\arg \displaystyle{\min_{uv \in E}} f(v) + w(uv) (אם יש שתי קשתות מתאימות עבור צומת מסוים נשבור שוויון בצורה שרירותית). אז בגרף המתואר דרגת הכניסה של כל צומת היא 1. מכיוון שהצומת ss לא נמצאת בגרף הזה הגרף הוא אוסף של מעגלים, אבל מכיוון שהפונקציה חיוביות ממש אז במעגל הפונקציה מונוטונית עולה ממש וזו סתירה.

ב. ניתן לעבור על כל הצמתים בסדר שרירותי ולוודא שהתנאי אכן מתקיים. הנכונות נובעת ישירות מהטענה והסיבוכיות היא לינארית.

1
Feedback