גרף לא מכוון G=\left(V,E\right) יקרא גרף דו-צדדי (Bipartite Graph) אם קיימת חלוקה של צמתי הגרף לקבוצות L,R כך ש-G\left[L\right] ו-G\left[R\right] הם גרפים חסרי קשתות.
בהינתן גרף לא מכוון G=\left(V,E\right) הציעו אלגוריתם המכריע אם G הוא גרף דו צדדי.
האלגוריתם
- קלט: גרף לא מכוון וקשיר 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 הוא גרף דו-צדדי. נגדיר:
L=\left\{ v\,:\,d_{s}(v)\equiv_{2}0\right\} ,\,R=\left\{ v\,:\,d_{s}(v)\equiv_{2}1\right\}
ע“פ הנחה נובע כי לכל קשת (u,v)\in E מתקיים d_{s}(u)\not\equiv_{2}d_{s}(v) ולכן הצמתים u ו-v נמצאים בצדדים שונים של החלוקה ולכן G\left[L\right] ו-G\left[R\right] הם חסרי קשתות, כלומר גרף G הוא גרף דו-צדדי.