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

הגדרות

• גרף הוא זוג [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{ 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}):i\in[1,n-1]\cap\mathbb 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}):i\in[1,n-1]\cap\mathbb 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] אי־זוגי אזי הגרף מסדר זוגי.
• יער הוא גרף פשוט ללא מעגלים.
  • עץ הוא יער קשיר.

הילוכים

• הילוך בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה [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{ 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].