הבדלים בין גרסאות בדף "תקציר תורת הגרפים, סמסטר א תשע״ג"

גרסה מ־12:42, 11 בנובמבר 2012

גרף הוא זוג $G=(V,E)$ כך ש־ $V$ קבוצת קודקודים (נקראים גם "צמתים") ו־ $E$ רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
לולאה היא צלע $(v,v)$ כאשר $v\in V$ .
גרף פשוט הוא גרף ללא לולאות וללא ריבוי צלעות (כלומר, אף צלע לא מופיע פעמיים ב־ $E$ ).
גרף מכוון הוא גרף בו הצלעות הן זוגות סדורים.
גרף סופי הוא גרף בו $|V|,|E|<\infty$ .
סדר של גרף הוא מספר הקודקודים בו, כלומר $|V|$ . לעתים מסומן $n(G)$ .
מידה של גרף היא מספר הצלעות – $|E|$ . לעתים מסומנת $e(G)$ או $m(G)$ .
דרגה של קודקוד היא מספר הצלעות העוברות בו. מסומנת או .
- מתקיים $\sum_{v\in V}d_G(v)=2|E|$ .
איחוד של גרפים פשוטים $G,H$ הוא $G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big)$ . באותו אופן מוגדר איחוד זר.

גרף ריק מסדר $n$ מסומן $N_n$ הוא הגרף שסדרו $n$ ומידתו 0.
גרף מלא/שלם מסדר $n$ ( $K_n$ ) הוא הגרף שסדרו $n$ ובין כל שני קודקודים יש צלע אחת בדיוק.
מסילה מסדר $n$ ( $P_n$ ) הוא הגרף שסדרו $n$ ושניתן לסדר את קודקודיו כ־ $v_1,\dots,v_n$ ואז $E=\{(v_i,v_{i+1}):i\in[1,n-1]\cap\mathbb N\}$ .
מעגל מסדר $n>2$ ( $C_n$ ) הוא הגרף שסדרו $n$ ושניתן לסדר את קודקודיו כ־ $v_1,\dots,v_n$ ואז $E=\{(v_i,v_{i+1}):i\in[1,n-1]\cap\mathbb N\}\cup\{(v_n,v_1)\}$ .
גרף $d$ ־רגולרי הוא גרף שבו דרגת כל קודקוד היא .
- גרף הוא ריק אם״ם הוא 0־רגולרי.
- גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
- גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
- אם גרף סופי ופשוט הוא $d$ ־רגולרי כך ש־ $d$ אי־זוגי אזי הגרף מסדר זוגי.
יער הוא גרף פשוט ללא מעגלים.
- עץ הוא יער קשיר.

הילוך בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה כך ש־.
- אורך ההילוך הוא $n$ – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
- ההילוך סגור אם $v_0=v_n$ .
מסלול הוא הילוך שבו אין צלעות חוזרות.
מסילה היא הילוך שבו אין קודקודים חוזרים, למעט אם הקודקוד הראשון שווה לקודקוד האחרון.
- כל מסילה היא מסלול.
קיים הילוך בין שני קודקודים אם״ם קיימת מסילה בינהם.
רכיב קשירות בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות המקיים אם״ם יש מסילה בין .
- מספר רכיבי הקשירות בגרף $G$ יסומן $K(G)$ .
- גרף קשיר הוא גרף שבו יש מחלקת שקילות אחת.
  - גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.

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