Question

scc

יהא G=(V,E)G = (V,E) גרף מכוון. נאמר כי UVU \subseteq V היא קבוצה סגורה אם UU \neq \emptyset ואין קשת מכוונת היוצאת מצומת ב-UU לצומת שאינו ב-UU.

הציעו אלגוריתם הרץ בזמן O(V+E)O(|V| + |E|) המוצא קבוצה סגורה מגודל מינימלי.

1

Answers

אלגוריתם


  1. בנה גרף קשיר היטב SCC מG2.בצע מיון טופולוגי
  2. נגדיר פונ' משקל על רכיבי הקשירות להיות לפי מס' הצמתים ברכיב.
  3. מצא את המקור בSCC בעל משקל המינימלי וסמנו בU.
  4. החזר את U.

סיבוכיות


בניית גרף קשיר היטב והרצת מיון טופולוגי נעשה בסיבוכיות לינארית, כמו כן מציאת המקור . סך הכל נקבל סיבוכיות לינארית.

טענה: גרף קשיר היטב הוא DAG.

הוכחה: הוכח בתרגול.

טענה: U קבוצה סגורה מינימלית.

הוכחה: נניח בשלילה כי U אינה מינימלית, כלומר קיים צומת u בU כך שאם נסיר אותו מהקבוצה U נקבל קבוצה סגורה.

אם U הכילה רק את u נקבל סתירה לכך שאינה מנימלית כיוון שקבוצה סגורה לא יכולה להיות ריקה. לכן בהכרח קיים צומת אחר v בU , U הוגדר כרכיב קשיר היטב, ולכן קיים מסלול מv אל u, בסתירה לכך שU קבוצה סגורה. כלומר קיבלנו כי U קבוצה מנימלית.

נכונות

האלגוריתם עוצר(ניתן לבצע מיון טופולוגי) והוכחנו כי U קבוצה סגורה מינימלית בטענות להעיל.

-2
Feedback