אלגוריתם המכריע אם גרף לא מכוון הוא גרף דו צדדי

האלגוריתם

• קלט: גרף לא מכוון וקשיר G=\left(V,E\right).
• פלט: האם הגרף G הוא דו-צדדי או לא.
• תיאור האלגוריתם:
  • שלב 1 - הרץ אלגוריתם BFS מצומת שרירותי s\in V.
  • שלב 2 - נעבור על הקשתות ואם בכל קשת מתקיים d_{s}(u)\not\equiv d_{s}(v) אז נקבל. אחרת, נדחה.

ניתוח סיבוכיות
בשלב 1 מריצים אלגוריתם BFS שלוקח O\left(V+E\right). בשלב 2 רצים על כל הקשתות כך שבכל קשת עושים בדיקה בסיבוכיות O\left(1\right) ולכן סה“כ סיבוכיות של שלב 2 הינה O\left(E\right). סה“כ נקבל סיבוכיות זמן O\left(V+E\right).

הוכחת נכונות
נוכיח שתי טענות עזר:

• טענת עזר 1: יהא G=\left(V,E\right) גרף דו צדדי עם צדדים L,R. יהא p מסלול בין u ל-v. אזי, אורך המסלול p זוגי אם“ם הצמתים $u,v נמצאים באותו צד.
• טענת עזר 2: יהא G=\left(V,E\right) גרף לא מכוון וקשיר ויהא s\in V. אזי G הוא גרף דו-צדדי אם“ם לכל קשת (u,v)\in E מתקיים d_{s}(u)\not\equiv_{2}d_{s}(v).

נכונות האלגוריתם נובע ע“פ טענת עזר 2 באופן ישיר.

הוכחת טענת עזר 1
נוכיח כי אם אורך המסלול p הוא זוגי אז הצמתים u,v נמצאים באותו צד ואם הוא אי-זוגי אז הצמתים u,v נמצאים בצדדים שונים. נוכיח את הטענה באינדוקציה על אורך המסלול |p|=l:

• בסיס האינדוקציה: אם l=0 אזי הטענה מתקיימת באופן ריק.
• סגור האינדוקציה: יהא p מסלול בין u ל-v באורך l>0. יהי w צומת שקודם ל-v במסלול p. היות ומתקיים (w,v)\in E נובע ע“פ הגדרת גרף דו-צדדי כי u,w נמצאים בצדדים שונים של הגרף. אורך המסלול בין u ל-w הוא l-1. נפריד למקרים:
  • אם l זוגי אז l-1 הוא אי-זוגי ולכן ע“פ הנחת האינדוקציה נובע כי הצמתים u ו-w נמצאים בצדדים שונים ולכן הצמתים u ו-v נמצאים באותו צד ע“פ הגדרת גרף דו-צדדי.
  • אם l אי-זוגי אז l-1 הוא זוגי ולכן ע“פ הנחת האינדוקציה נובע כי הצמתים u ו-w נמצאים באותו צד ולכן הצמתים u ו-v נמצאים בצדדים שונים של הגרף.

הוכחת טענת עזר 2
נפריד לשני כיוונים: כיוון ראשון: נניח כי G הוא גרף דו-צדדי ונוכיח כי לכל קשת (u,v)\in E מתקיים d_{1}(u)\not\equiv_{2}d_{2}(v). מאחר ו-G הוא גרף דו-צדדי, ניתן לחלק את הצמתים לשתי קבוצות L ו-R. נניח בלי הגבלת הכלליות כי s\in L. ע“פ טענת העזר 1 נקבל כי לכל צומת w\in L מתקיים d_{s}(w)\equiv_{2}0 ולכל צומת w\in R מתקיים d_{s}(w)\equiv_{2}1. לכן, לכל קשת (u,v)\in E בהכרח d_{s}(u)\not\equiv_{2}d_{s}(v) כי הצמתים u ו-v נמצאים בצדדים שונים ע“פ הגדרת גרף דו-צדדי.
כיוון שני: נניח כי לכל קשת (u,v)\in E מתקיים d_{s}(u)\not\equiv_{2}d_{s}(v) ונוכיח כי G הוא גרף דו-צדדי. נגדיר:

ע“פ הנחה נובע כי לכל קשת (u,v)\in E מתקיים d_{s}(u)\not\equiv_{2}d_{s}(v) ולכן הצמתים u ו-v נמצאים בצדדים שונים של החלוקה ולכן G\left[L\right] ו-G\left[R\right] הם חסרי קשתות, כלומר גרף G הוא גרף דו-צדדי.