תקציר תורת הגרפים, סמסטר א תשע״ג

הגדרות

• גרף הוא זוג [math]\displaystyle{ G=(V,E) }[/math] כך ש־[math]\displaystyle{ V }[/math] קבוצת קודקודים (נקראים גם "צמתים") ו־[math]\displaystyle{ E }[/math] רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
• לולאה היא צלע [math]\displaystyle{ (v,v) }[/math] כאשר [math]\displaystyle{ v\in V }[/math].
• גרף פשוט הוא גרף ללא לולאות וללא ריבוי צלעות (כלומר, אף צלע לא מופיע פעמיים ב־[math]\displaystyle{ E }[/math]).
• גרף מכוון הוא גרף בו הצלעות הן זוגות סדורים.
  • אי־הכוונה של גרף מכוון היא הפיכתו לגרף לא מכוון ע״י הפיכת צלעותיו לזוגות לא סדורים.
• גרף סופי הוא גרף בו [math]\displaystyle{ |V|,|E|\lt \infty }[/math].
• סדר של גרף הוא מספר הקודקודים בו, כלומר [math]\displaystyle{ |V| }[/math]. לעתים מסומן [math]\displaystyle{ n(G) }[/math].
• מידה של גרף היא מספר הצלעות – [math]\displaystyle{ |E| }[/math]. לעתים מסומנת [math]\displaystyle{ e(G) }[/math] או [math]\displaystyle{ m(G) }[/math].
• דרגה של קודקוד [math]\displaystyle{ v\in V }[/math] היא מספר הצלעות העוברות בו. מסומנת [math]\displaystyle{ d(v) }[/math] או [math]\displaystyle{ d_G(v) }[/math].
  • מתקיים [math]\displaystyle{ \sum_{v\in V}d_G(v)=2|E| }[/math].
  • הדרגה המקסימלית: [math]\displaystyle{ \Delta(G):=\max\{d_G(v):\ v\in V(G)\} }[/math].
  • הדרגה המינימלית: [math]\displaystyle{ \delta(G):=\min\{d_G(v):\ v\in V(G)\} }[/math].
  • דרגות החוץ והפנים של קודקוד בגרף מכוון הן [math]\displaystyle{ d_G^+(v):=|\{(v,u)\in E:\ u\in V\}|,\ d_G^-(v):=|\{(u,v)\in E:\ u\in V\}| }[/math] בהתאמה, כלומר מספר הצלעות היוצאות ומספר הצלעות הנכנסות לקודקוד בהתאמה.
    • מתקיים [math]\displaystyle{ \sum_{v\in V}d_G^+(v)=\sum_{v\in V}d_G^-(v)=|E| }[/math].
• איחוד של גרפים פשוטים [math]\displaystyle{ G,H }[/math] הוא [math]\displaystyle{ G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big) }[/math]. באותו אופן מוגדר איחוד זר.
• קבוצת השכנים של קודקוד [math]\displaystyle{ v }[/math] בגרף [math]\displaystyle{ G }[/math] היא [math]\displaystyle{ N_G(v):=\{u:\ (v,u)\in E(G)\} }[/math].

סוגים נפוצים

• גרף ריק מסדר [math]\displaystyle{ n }[/math] מסומן [math]\displaystyle{ N_n }[/math] הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ומידתו 0.
• גרף מלא/שלם מסדר [math]\displaystyle{ n }[/math] ([math]\displaystyle{ K_n }[/math]) הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ובין כל שני קודקודים יש צלע אחת בדיוק.
  • [math]\displaystyle{ K_{m,n} }[/math] הוא הגרף שקודקודיו הם [math]\displaystyle{ V\uplus U }[/math] (כאשר [math]\displaystyle{ |V|=n,|U|=m }[/math]) וצלעותיו [math]\displaystyle{ \{(v,u):\ v\in V\ \and\ u\in U\} }[/math].
• מסילה מסדר [math]\displaystyle{ n }[/math] ([math]\displaystyle{ P_n }[/math]) הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ושניתן לסדר את קודקודיו כ־[math]\displaystyle{ v_1,\dots,v_n }[/math] ואז [math]\displaystyle{ E=\{(v_i,v_{i+1}):\ 1\le i\lt n\} }[/math].
• מעגל מסדר [math]\displaystyle{ n\gt 2 }[/math] ([math]\displaystyle{ C_n }[/math]) הוא הגרף שסדרו [math]\displaystyle{ n }[/math] ושניתן לסדר את קודקודיו כ־[math]\displaystyle{ v_1,\dots,v_n }[/math] ואז [math]\displaystyle{ E=\{(v_i,v_{i+1}):\ 1\le i\lt n\}\cup\{(v_n,v_1)\} }[/math].
  • אם [math]\displaystyle{ \delta(G)\ge 2 }[/math] אז יש ב־[math]\displaystyle{ G }[/math] מעגל.
  • מותן (girth) של גרף [math]\displaystyle{ G }[/math] הוא אורך המעגל הקטן ביותר בגרף, ומסומן [math]\displaystyle{ g(G) }[/math]. אם אין בגרף מעגלים (יער) אז [math]\displaystyle{ g(G)=\infty }[/math].
    • [math]\displaystyle{ g(G)\le2 }[/math] אם״ם הגרף לא פשוט.
• גרף d־רגולרי הוא גרף שבו דרגת כל קודקוד היא [math]\displaystyle{ d }[/math].
  • גרף הוא ריק אם״ם הוא 0־רגולרי.
  • גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
  • גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
  • אם גרף סופי ופשוט הוא [math]\displaystyle{ d }[/math]־רגולרי כך ש־[math]\displaystyle{ d }[/math] אי־זוגי אזי הגרף מסדר זוגי.
  • גרף d⁺־רגולרי הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא [math]\displaystyle{ d }[/math]. באותו אופן מגדירים גרף [math]\displaystyle{ d^- }[/math]־רגולרי.

עצים

• יער הוא גרף פשוט ללא מעגלים.
  • עץ הוא יער קשיר.
    • גרף פשוט הוא עץ אם״ם בין כל שני קודקודים יש מסילה יחידה.
    • עלה הוא קודקוד בעץ שדרגתו 1.
    • בכל עץ סופי מסדר גדול מ־1 יש עלה.
    • גרף הוא עץ אם״ם הוא קשיר מינימלי, כלומר הוא קשיר וכל השמטת צלע יוצרת תת־גרף לא קשיר.
    • גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל.
    • חיפוש DFS: נרצה ליצור הילוך שעובר על כל קודקודי העץ. מתחילים באחד מהעלים. בכל צעד אם אנו נמצאים על קודקוד שעל כל ילדיו כבר נערך חיפוש, נפנה להורה שלו. אחרת נפנה לאחד מילדיו.
    • עץ פורש הוא תת־גרף פורש קשיר ללא מעגלים.
      • לכל גרף קשיר וסופי קיים עץ פורש.
        • בעיית הסוכן הנוסע: נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 2 מהפתרון המינימלי: מוצאים עץ פורש לגרף ומבצעים עליו חיפוש DFS.
  • ביער מסדר [math]\displaystyle{ n\in\mathbb N }[/math] עם [math]\displaystyle{ k }[/math] רכיבי קשירות יש [math]\displaystyle{ n-k }[/math] צלעות.
  • גרף הוא יער אם״ם אין לו מינור שאיזומורפי ל־[math]\displaystyle{ K_3 }[/math].

הילוכים

• הילוך בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה [math]\displaystyle{ v_0,v_1,\dots,v_n }[/math] כך ש־[math]\displaystyle{ \forall i:\ (v_i,v_{i+1})\in E }[/math].
  • אורך ההילוך הוא [math]\displaystyle{ n }[/math] – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
    • המרחב בין שני קודקודים [math]\displaystyle{ u,v }[/math] הוא המרחק המינימלי של הילוך בינהם (אם יש כזה) ומסומן [math]\displaystyle{ \mbox{dist}_G(u,v) }[/math].
      • הקוטר של גרף הוא [math]\displaystyle{ \mbox{diameter}(G)=\max\{\mbox{dist}_G(u,v):\ u,v\in V(G)\} }[/math].
  • ההילוך סגור אם [math]\displaystyle{ v_0=v_n }[/math].
• מסלול הוא הילוך שבו אין צלעות חוזרות.
• מסילה היא הילוך שבו אין קודקודים חוזרים, למעט אם הקודקוד הראשון שווה לקודקוד האחרון.
  • כל מסילה היא מסלול.
• קיים הילוך בין שני קודקודים אם״ם קיימת מסילה בינהם.
• רכיב קשירות בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות [math]\displaystyle{ \rightarrow }[/math] המקיים [math]\displaystyle{ u\rightarrow v }[/math] אם״ם יש מסילה בין [math]\displaystyle{ u,v }[/math].
  • מספר רכיבי הקשירות בגרף [math]\displaystyle{ G }[/math] יסומן [math]\displaystyle{ K(G) }[/math].
  • גרף קשיר הוא גרף שבו יש רכיב קשירות אחד.
    • גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.

• מסלול אוילר בגרף ללא לולאות הוא מסלול המכיל את כל צלעות הגרף.
  • אוילריאן הוא גרף בו קיים מסלול אוילר סגור.
  • סמי־אוילריאן הוא גרף בו קיים מסלול אוילר.
  • משפט אוילר: גרף קשיר וסופי ללא לולאות הוא אוילריאן אם״ם דרגות כל הקודקודים זוגיות.
    • גרף [math]\displaystyle{ G }[/math] קשיר וסופי ללא לולאות הוא סמי־אוילריאן שאינו אוילריאן אם״ם דרגות כל הקודקודים זוגיות פרט לשני קודקודים.
• מסילה המילטוניאנית בגרף היא מסילה המכילה את כל קודקודיו.
  • מעגל המילטוניאני הוא מסילה המילטוניאנית סגורה.
    • המילטוניאן הוא גרף בו קיים מעגל המילטוניאני.
      • משפט דיראק: יהי [math]\displaystyle{ G }[/math] גרף פשוט מסדר [math]\displaystyle{ n }[/math]. אם [math]\displaystyle{ \delta(G)\ge\frac n2 }[/math] אז [math]\displaystyle{ G }[/math] המילטוניאן.

תתי גרפים

• השמטת צלע [math]\displaystyle{ e\in E }[/math] מגרף [math]\displaystyle{ G }[/math] היא הפיכת הגרף ל־[math]\displaystyle{ G\setminus\{e\}:=(V,E\setminus\{e\}) }[/math].
• השמטת קודקוד [math]\displaystyle{ v\in V }[/math] מגרף [math]\displaystyle{ G }[/math] היא הפיכת הגרף ל־[math]\displaystyle{ G\setminus\{v\}:=(V\setminus\{v\},E\setminus\{(v,u):\ u\in V\}) }[/math].
• תת־גרף הוא הגרף המתקבל מסדרה של השמטות קודקודים ו/או צלעות.
  • תת־גרף פורש הוא תת־גרף המתקבל מסדרה של השמטות צלעות בלבד.
  • תת־גרף מושרה הוא תת־גרף המתקבל מסדרה של השמטות קודקודים בלבד.
    • אם [math]\displaystyle{ H }[/math] תת־גרף מושרה של [math]\displaystyle{ G }[/math] אזי [math]\displaystyle{ \forall u,v\in V(H):\ \Big((u,v)\in E(G)\iff(u,v)\in E(H)\Big) }[/math]. כלומר, כל שני קודקודים שכנים ב־[math]\displaystyle{ H }[/math] הם שכנים ב־[math]\displaystyle{ G }[/math].

איזומורפיזם

• איזומורפיזם בין מגרף [math]\displaystyle{ G }[/math] לגרף [math]\displaystyle{ H }[/math] הוא פונקציה [math]\displaystyle{ \varphi:V(G)\to V(H) }[/math] חח״ע ועל ששומרת צלעות, כלומר [math]\displaystyle{ (u,v)\in E(G)\iff(\varphi(u),\varphi(v))\in E(H) }[/math] לכל [math]\displaystyle{ u,v\in V(G) }[/math]. אם קיים איזומורפיזם בין [math]\displaystyle{ G,H }[/math] אז נאמר שהם איזומורפיים ונסמן [math]\displaystyle{ G\cong H }[/math] (זה יחס שקילות).
• אם [math]\displaystyle{ G\cong H }[/math] אז הפרמטרים הבאים שווים:
  • סדר: [math]\displaystyle{ |V(G)|=|V(H)| }[/math].
  • מידה: [math]\displaystyle{ |E(G)|=|E(H)| }[/math].
  • מספר רכיבי הקשירות: [math]\displaystyle{ K(G)=K(H) }[/math].
  • וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).
  • קוטר: [math]\displaystyle{ \mbox{diameter}(G)=\mbox{diameter}(H) }[/math].
• גרף מסומן הוא גרף שקודקודיו סומנו ע״י [math]\displaystyle{ \{v_i\}_{i=1}^n }[/math]. שני גרפים מסומנים הם זהים אם״ם קיים איזומורפיזם [math]\displaystyle{ \varphi }[/math] בינהם כך ש־[math]\displaystyle{ \forall i:\ \varphi(v_i)=v_i }[/math].
  • משפט קיילי: יש [math]\displaystyle{ n^{n-2} }[/math] עצים מסומנים מסדר [math]\displaystyle{ n }[/math].

גרף משלים

• הגרף המשלים של גרף [math]\displaystyle{ G=(V,E) }[/math] הוא [math]\displaystyle{ \overline G:=(V,V^2\setminus E) }[/math].
• [math]\displaystyle{ G\cong H }[/math] אם״ם [math]\displaystyle{ \overline G\cong\overline H }[/math].

גרף הקו

• גרף הקו של גרף פשוט [math]\displaystyle{ G }[/math] מסומן [math]\displaystyle{ L(G) }[/math] ומוגדר כגרף שקודקודיו הם [math]\displaystyle{ E(G) }[/math] וצלעותיו הם זוגות של צלעות שיש להן קודקוד משותף ב־[math]\displaystyle{ G }[/math], כלומר [math]\displaystyle{ E(L(G)):=\Big\{\Big((u_1,v),(u_2,v)\Big):\ (u_1,v),(u_2,v)\in E(G)\Big\} }[/math].
  • [math]\displaystyle{ L(P_n)\cong P_{n-1} }[/math], [math]\displaystyle{ L(C_n)\cong C_n }[/math].

מכפלה קרטזית של גרפים

• המכפלה הקרטזית של הגרפים [math]\displaystyle{ G,H }[/math] היא גרף המסומן כ־[math]\displaystyle{ G\times H }[/math]. קודקודיו הם [math]\displaystyle{ V(G)\times V(H) }[/math] וצלעותיו [math]\displaystyle{ \Big\{\Big((u_1,v),(u_2,v)\Big):\ \forall \{F_1,F_2\}=\{G,H\}:\ v\in V(F_1)\ \and\ (u_1,u_2)\in E(F_2)\Big\} }[/math].
• קובייה n־מימדית היא [math]\displaystyle{ K_2^{\times n}:=\prod_{i=1}^n K_2 }[/math]. היא איזומורפית ל־[math]\displaystyle{ B_n:=(\mathcal P([n]),\{(I,J):\ I\subset J\subseteq[n]\ \and\ |I|=|J|-1\}) }[/math] ול־[math]\displaystyle{ H_n:=(\mathbb Z_2^n,\{(u,v):\ u,v\in\mathbb Z_2^n\ \and\ |u-v|=1\}) }[/math].

שיכון

• שיכון של גרף [math]\displaystyle{ G }[/math] ב־[math]\displaystyle{ \mathbb R^n }[/math] הוא העתקה חח״ע [math]\displaystyle{ \varphi:V(G)\to\mathbb R^n }[/math]. כל צלע [math]\displaystyle{ (u,v)\in E(G) }[/math] מועתקת למסילה רציפה ופשוטה (כלומר, שאינה חותכת את עצמה) מ־[math]\displaystyle{ \varphi(u) }[/math] ל־[math]\displaystyle{ \varphi(v) }[/math].
• שיכון נאות הוא שיכון אם אין חיתוך צלעות לא טריוויאלי, כלומר התמונות של הצלעות ב־[math]\displaystyle{ \mathbb R^n }[/math] חותכות זו את זו רק בתמונות של קודקודי הגרף.
• לכל גרף עם מספר בן מנייה של קודקודים קיים שיכון נאות ב־[math]\displaystyle{ \mathbb R^3 }[/math] כך שהתמונות של הצלעות הן קטעים ישרים. אם הגרף הוא סופי ופשוט אז שיכון נאות מתאים הוא, לדוגמה, [math]\displaystyle{ \forall i:\ \varphi(v_i)=(i,i^2,i^3) }[/math] כאשר [math]\displaystyle{ V=\{v_i\}_{i=1}^n }[/math].
• גרף מישורי הוא גרף שניתן לשיכון נאות ב־[math]\displaystyle{ \mathbb R^2 }[/math].
• פאה של שיכון נאות ב־[math]\displaystyle{ \mathbb R^2 }[/math] היא רכיב קשירות ב־[math]\displaystyle{ \mathbb R^2 }[/math] לאחר שהוציאו ממנו את התמונה של השיכון.
• משפט הפאון של אוילר: לכל גרף מישורי סופי קשיר מסדר [math]\displaystyle{ n }[/math] וממידה [math]\displaystyle{ m }[/math] מספר הפאות [math]\displaystyle{ f }[/math] לא תלוי בשיכון הנאות ומקיים [math]\displaystyle{ n-m+f=2 }[/math].
• יהי [math]\displaystyle{ G }[/math] גרף פשוט וקשיר מסדר [math]\displaystyle{ n\ge3 }[/math]. אם [math]\displaystyle{ G }[/math] מישורי אז [math]\displaystyle{ |E(G)|\le3n-6 }[/math].
• יהי [math]\displaystyle{ G }[/math] פשוט וקשיר מסדר [math]\displaystyle{ n }[/math] ומותן [math]\displaystyle{ g\lt \infty }[/math]. אם [math]\displaystyle{ G }[/math] מישורי אז [math]\displaystyle{ |E(G)|\le g\frac{n-2}{g-2} }[/math].
• משפט קורטובסקי: גרף אינו מישורי אם״ם יש לו תת־גרף שאיזומורפי לחלוקה של [math]\displaystyle{ K_5 }[/math] או של [math]\displaystyle{ K_{3,3} }[/math].
• משפט וגנר: גרף אינו מישורי אם״ם יש לו מינור שאיזומורפי ל־[math]\displaystyle{ K_5 }[/math] או ל־[math]\displaystyle{ K_{3,3} }[/math].
• גרף חוץ־מישורי הוא גרף שניתן לשכן באופן נאות במישור כך שקודקודיו על מעגל וצלעותיו קטעים ישרים.
• גרף הוא חוץ־מישורי אם״ם אין לו מינור שאיזומורפי ל־[math]\displaystyle{ K_4 }[/math] או ל־[math]\displaystyle{ K_{2,3} }[/math].

חלוקות =

• חלוקה אלמנטרית של צלע [math]\displaystyle{ e=(u,v) }[/math] בגרף [math]\displaystyle{ G }[/math] היא [math]\displaystyle{ G\setminus\{e\}\cup\Big(\{e\},\{(u,e),(v,e)\}\Big) }[/math].
• חלוקה של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות.

כיווץ

• כיווץ של גרף [math]\displaystyle{ G }[/math] בצלע [math]\displaystyle{ e=(u,v) }[/math] הוא [math]\displaystyle{ G/e:=G\setminus\{u,v\}\cup\Big(\{e\},\{e\}\times(N_G(u)\cup N_G(v))\Big) }[/math].
• מינור של גרף פשוט הוא גרף המתקבל ממנו ע״י סדרה של השמטות קודקודים, השמטות צלעות וכיווצי צלעות.
• תכונה מונוטונית של גרף היא תכונה הסגורה תחת מינור, כלומר אם גרף מקיים אותה אז כל מינור שלו מקיים אותה.
• השערת וגנר: כל תכונה היא מונוטונית אם״ם היא מוגדרת ע״י קבוצה סופית של מינורים אסורים, כלומר קיים מספר סופי של גרפים שאיזומורפים למינור כלשהו של [math]\displaystyle{ G }[/math] אם״ם הוא אינו מקיים את התכונה.
• משפט רוברטסון–סימור: השערת וגנר נכונה.

• 

  טטרהדרון

• 

  הקסהדרון

• 

  אוקטהדרון

• 

  דודקהדרון

• 

  איקוסהדרון

גופים אפלטוניים

• גוף אפלטוני הוא פאון תלת־מימדי שכל פאותיו מצולעים משוכללים חופפים.
• הגופים האפלטונים הם הטטרהדרון ([math]\displaystyle{ K_4 }[/math]), ההקסהדרון (קובייה, [math]\displaystyle{ K_2^{\times3} }[/math]), האוקטהדרון ([math]\displaystyle{ K_{2,4} }[/math]), הדודקהדרון והאיקוסהדרון.
• הגרף של כל גוף אפלטוני הוא מישורי.
• פאון דואלי של גוף אפלטוני הוא הפאון המתקבל לאחר שלכל פאה בגוף האפלטוני שמים קודקוד במרכז ומחברים צלעות בין קודקודים של פאות להן צלע משותפת.