Question

shortest_path
summer_18_b

נתון גרף מכוון, G=(V,E)G = (V, E), ונתונה פונקציה f:VN{+,}f:V \to \mathbb{N} \cup \{+, -\}. כלומר, בכל צומת של הגרף נתון מספר טבעי או סימן חיבור או חיסור.

מסלול בגרף v1,,vkv_1, \ldots, v_k הוא חוקי אם ניתן לפרש את f(v1)f(vk)f(v_1) \ldots f(v_k) כביטוי אלגברי חוקי, וערך המסלול הוא ערך הביטוי האלגברי המתאים.

א. נתון הגרף הבא:

tikz

ערכי ff מסומנים על הצמתים ונתון ש-f(s)=f(t)=0f(s) = f(t) = 0. מצאו מסלול חוקי מ-ss ל-tt עם ערך מינימלי או קבעו שלא קיים כזה.

ב. בהינתן גרף מכוון, G=(V,E)G = (V, E), זוג צמתים s,tVs,t \in V ופונקציה ff כמתואר למעלה, הציעו אלגוריתם שקובע אם קיים מסלול חוקי כלשהו מ-ss ל-tt. יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

ג. בהינתן גרף מכוון, G=(V,E)G = (V, E), זוג צמתים s,tVs,t \in V ופונקציה ff כמתואר למעלה, הציעו אלגוריתם שמוצא מסלול חוקי מ-ss ל-tt עם ערך מינימלי או קובע שאין כזה. הניחו כי בגרף לא קיים מעגל חוקי עם ערך שלילי.יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

1

Answers

א.

tikz

ב. אלגוריתם:

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

סיבוכיות:

  • הסרת הקשתות ובדיקת קשירות ניתן לעשות בזמן לינארי.

ג. אלגוריתם:

  • נסיר את כל הקשתות הלא חוקיות כמו בסעיף הקודם.
  • נמשקל את הגרף באופן הבא:
w(uv)={f(v)f(u)=+f(v)f(u)=0otherwise w(uv) = \begin{cases} f(v) & f(u) = + \\ -f(v) & f(u) = - \\ 0 & \text{otherwise} \end{cases}
  • בגרף המתקבל נמצא מסלול קל ביותר מ-ss ל-tt.
1
Feedback