Question

scc
spring17_b

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

נגדיר: vVv \in V הוא צומת שלילי אמ"מ הוא חלק ממעגל שלילי כלשהו בגרף (המעגל לא בהכרח פשוט - ייתכנו צמתים שעוברים דרכם יותר מפעם אחת).

הציעו אלגוריתם הרץ בסיבוכיות זמן O(VE)O(|V||E|) ומחזיר את קבוצת כל הצמתים השליליים ב-GG.

רמז: ניתן להשתמש בגרף הרכיבים הקשירים היטב של GG.

1

Answers

טענה: צומת הוא שלילי אמ"מ הוא שייך לרק"ה שבו יש מעגל שלילי.

הוכחה: נניח שצומת uu שייך לרק"ה שבו יש מעגל שלילי v1,,vk,v1v_1, \ldots, v_k, v_1 אז צומת uu שייך למעגל השלילי

u,v1,,vk,v1×l,,u u, \ldots \overbrace{v_1, \ldots, v_k, v_1}^{\times l}, \ldots, u

כאשר ll מספר מספיק גדול שיבטיח שמשקל המעגל המתואר הוא אכן שלילי.

מצד שני, אם צומת הוא שלילי אז הוא נמצא על מעגל שלילי כלשהו (לאו דווקא פשוט), נשים לב שבמעגל כזה חייב להיות תת מעגל פשוט שלילי (אחרת נסיר את כל המעגלים הפשוטים שהם לא שליליים ונקבל סתירה).

אלגוריתם: נמצא את גרף הרק"ה ונחזיר את כל הצמתים ששייכים לרק"ה עם מעגל שלילי (ניתן לבדוק זאת על ידי אלג בלמן פורד למשל).

נכונות: ישירות מהטענה.

סיבוכיות:

  • מציאת הרק"ה: O(E+V)O(|E| + |V|)
  • בדיקת מעגלים שליליים CCO(E(C)V(C))=O(VE)\displaystyle{\sum_{C \in \mathcal{C}}}O(|E(C)||V(C)|) = O(|V||E|)

כאשר C\mathcal{C} קבוצת הרכיבים קשירים היטב ו-V(C),E(C)V(C), E(C) קבוצת הצמתים והקשתות של רק"ה CC בהתאמה.

1
Feedback