Question

bfs

מציאת קוטר הגרף:

יהא G=(V,E)G = (V, E) גרף קשיר ולא מכוון. לכל זוג צמתים u,vVu,v \in V המרחק δ(u,v)\delta(u,v) בין הצמתים הוא מספר הקשתות במסלול קצר ביותר בניהם. קוטר הגרף, dd, מוגדר כמרחק המקסימלי בין כל זוגות הצמתים בגרף, כלומר d=maxu,vV{δ(u,v)}d = \max_{u,v \in V}\{\delta(u,v)\}.

א. בהינתן גרף, GG, וצומת vv שידוע כי הוא קצה של קוטר ב-GG הציעו אלגוריתם המחזיר את הקוטר של GG ופועל בסיבוכיות זמן O(V+E)O(|V| + |E|) עליכם לנתח את סיבוכיות האלגוריתם ולהוכיח את נכונותו.

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

1

Answers

אלגוריתם:

  • בחר צומת כלשהו, rr.
  • הרץ BFS מ-rr ובחר צומת עם מרחק מקסימלי מ-rr, uu.
  • הרץ BFS מ-uu והחזר את המרחק של הצומת עם המרחק המקסימלי מ-uu.

טענה: uu הוא קצה של קוטר בעץ.

הוכחה: נניח בשלילה שלא. נסתכל על קצוות של קוטר, aa ו-bb ועל האב הקדמון המשותף של uu aa,ו-bb, ww. אם uu לא קצה של קוטר אז אחד מהשניים מתקיים: δ(w,u)<δ(w,a)\delta(w, u) < \delta(w,a) אוδ(w,u)<δ(w,b)\delta(w, u) < \delta(w,b).

קיבלנו סתירה לכך ש-uu צומת במרחק מקסימלי מ-rr כי:δ(r,a)=δ(r,w)+δ(w,a)\delta(r, a) = \delta(r, w) + \delta(w, a), δ(r,b)=δ(r,w)+δ(w,b)\delta(r, b) = \delta(r, w) + \delta(w, b) ו-δ(r,u)=δ(r,w)+δ(w,u)\delta(r, u) = \delta(r, w) + \delta(w, u).

נכונות האלגוריתם: נובע מהטענה ומההגדרה של קוטר.

סיבוכיות: מריצים פעמיים BFS ובנוסף עוברים על כל הצמתים כדי למצוא צומת עם מרחק מקסימלי. סך הכלO(V+E)O(|V| + |E|).

2
Feedback