Question

dfs

נתון גרף מכוון G=(V,E)G = (V,E).

א. צומת vVv \in V יקרא יעד גלובלי אם לכל צומת uVu \in V קיים מסלול מ-uu ל-vv.

גרף GG נקרא גרף מעקפים אם לכל u,vVu,v \in V קיים wVw \in V כך שקיים מסלול מכוון מ-uu ל-ww ומ-vv ל-ww.

הוכיחו: GG גרף מעקפים אמ"מ קיים ב-GG יעד גלובלי.

ב. הציעו אלגוריתם יעיל ככל האפשר המכריע האם GG גרף מעקפים.

2

Answers

א. נניח שב-GG קיים יעד גלובלי ww נשים לב שעל פי הגדרה לכל u,vVu,v \in Vקיים מסלול מ-uu ל-ww וגם מ-vv ל-ww ולכן GG גרף מעקפים.

נניח כעת ש-GG גרף מעקפים, נניח שב-GG אין יעד גלובלי ונסתכל על צומת vv שישיג ממספר מקסימלי של צמתים. מכיוון ש-vv אינו יעד גלובלי אז קיים צומת uu כך ש-vv אינו ישיג מ-uu. מכיוון ש-GG גרף מעקפים אז קיים צומת ww כך ש-ww ישיג מ-vv וגם מ-uu ולכן ww ישיג ממספר צמתים גדול יותר מאשר vv - סתירה.

ב. אבחנה מיידית: צומת vv הוא יעד גלובלי ב-GG אמ"מ הוא שורש ב-GTG^T ולכן כל אלגוריתם שמכריע אם קיים שורש בגרף מכריע גם אם GG גרף מעקפים.ניתן להכריע אם קיים שורש בגרף בסיבוכיות לינארית על ידי הרצת DFS.

1
Feedback