Question

topological_sort

יהא G=(V,E)G = (V,E) גרף מכוון. קבוצה AVA \subseteq V תקרא גרעין אם לכל u,vAu,v \in A מתקיים (u,v)E(u,v) \notin E ולכל vVAv \in V \setminus A קיים aAa \in A כך ש-(a,v)E(a,v) \in E.

הציעו אלגוריתם המוצא גרעין בגרף מכוון חסר מעגלים ופועל בזמן O(V+E)O(|V| + |E|).

עליכם לנתח את סיבוכיות האלגוריתם ולהוכיח את נכונותו.

1

Answers

אלגוריתם:

  • אתחול A,BA \leftarrow \emptyset, B \leftarrow \emptyset
  • עבור על הצמתים לפי סדר מיון טופולוגי של GG ולכל צומת uVABu \in V \setminus A \setminus B בצע:
  1. AA{u}A \leftarrow A \cup \{u\}
  2. BB{v:(u,v)E}B \leftarrow B \cup \{v : (u,v) \in E \}
  • החזר את AA

נכונות:

אבחנה מידית: בסיום האלגוריתם AA ו-BB חלוקה של VV.

טענה: בכל שלב בריצת האלגוריתם AA גרעין ב-G[AB]G[A\cup B].

הוכחה באינדוקציה:

בסיס: באתחול טריוויאלי.

צעד: נניח שבצעד ה-ii הטענה מתקיימת ובצעד ה-i+1i+1 הוספנו את הצומת vv ל-AA ואת כל השכנים שלו ל-BB. נשים לב שלכל צומת, ww, שהוספנו ל-BB מתקיים ש-(v,w)E(v,w) \in E בנוסף נשים לב שלא קיים צומת uAu \in A כך ש-(u,v)E(u,v) \in E כי אחרת היינו מוסיפים את vv ל-BB כאשר הוספנו את uu ל-AA ולכן הטענה ממשיכה להתקיים.

נכונות האלגוריתם נובעת מהאבחנה + הטענה.

סיבוכיות: מיון טופולוגי + מעבר בודד על הצמתים - O(V+E)O(|V| + |E|).

1
Feedback