Question

spring_15_b
dfs
bridge

בגרף לא מכוון וקשיר קשת היא גשר אם הסרתה הופכת את הגרף ללא קשיר.

א. הוכיחו: אם בגרף לא מכוון וקשיר קיים גשר, אז לא ניתן לכוון את קשתות הגרף כך שהגרף המתקבל יהיה קשיר היטב.

ב. הוכיחו: יהי G=(V,E)G = (V, E) גרף לא מכוון וקשיר. יהי vVv \in V הצומת הראשון שנכנס למחסנית בריצת DFS כלשהי על הגרף. אזי vv הוא שורש של עץ ה-DFS המתקבל.

ג. הוכיחו: תהי (u,v)(u,v) קשת בעץ DFS. אם לא קיימת בגרף "קשת עוקפת" היוצאת מצאצא של vv (יתכן vv עצמו), אז (u,v)(u,v) היא גשר.

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

2

Answers

א. נניח בשלילה שקשת e={u,v}e = \{u,v\} היא גשר ונסמן ב-AA את כל הצמתים שישיגים מ-uu ב-G{e}G \setminus \{e\} כלומר הקשת ee היא הקשת היחידה שחוצה את AA

כעת, אם הכוון הוא (u,v)(u,v) נסתכל על צומת w/Aw \notin A אז לא קיים מסלול מ-ww ל-uu (כי אז קיימת קשת נוספת שנכנסת ל-AA).

מצד שני אם הכיוון הוא (v,u)(v,u) אז לא קיים מסלול מ-uu ל-ww (כי אז קיימת קשת נוספת שיוצאת מ-AA).

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

ג. נסמן ב-SS את קבוצת הצמתים שישיגים מ-vv ב-G{uv}G \setminus \{uv\} מכיוון שלא קיימות קשתות עוקפות ומכיוון שבגרף לא מכוון לא מתקבלות קשתות חוצות בריצת DFS מתקיים ש-

(u,v)(u,v) היא הקשת היחידה שחוצה את AA ובפרט הסרתה תגרום לכך שלא יהיה מסלול מ-uu ל-vv.

ד. האלגוריתם:

  • הרץ DFS וכוון את הקשתות כך:
  • קשתות עץ מהאבא לבן
  • קשתות אחוריות מהצאצא לאב הקדמון
  • בדוק אם rr, הצומת הראשון שנכנס למחסנית, ישיג מכל הצמתים בגרף ואם לא החזר שלא ניתן לכוון את הגרף, אחרת החזר את הגרף המכוון.

טענה: אם rr אינו ישיג מכל הצמתים אז קיים גשר בגרף.

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

נכונות: מהסעיפים הקודמים נובע שאם קיים גשר בגרף אז לא ניתן לכוון אותו ומהטענה נובע שאם בכיוון שהוצע rr לא ישיג מכל הצמתים אז קיים גשר. מצד שני, קל לראות, שאם rr כן ישיג מכל הצמתים אז הגרף קשיר היטב.

סיבוכיות: הרצת DFS ובדיקת ישיגות ניתן לעשות בזמן לינארי.

0
Feedback