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

הגדרות

• גרף הוא זוג [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{ G,H }[/math] הוא [math]\displaystyle{ G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big) }[/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{ 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{ d }[/math]־רגולרי הוא גרף שבו דרגת כל קודקוד היא [math]\displaystyle{ d }[/math].
  • גרף הוא ריק אם״ם הוא 0־רגולרי.
  • גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
  • גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
  • אם גרף סופי ופשוט הוא [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{ 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{ 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{ 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].