תקציר תורת הגרפים, סמסטר א תשע״ג
מתוך Math-Wiki
תוכן עניינים
הגדרות
- גרף הוא זוג כך ש־ קבוצת קודקודים (נקראים גם "צמתים") ו־ רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
- לולאה היא צלע כאשר .
- גרף פשוט הוא גרף ללא לולאות וללא ריבוי צלעות (כלומר, אף צלע לא מופיע פעמיים ב־).
- גרף מכוון הוא גרף בו הצלעות הן זוגות סדורים.
- גרף סופי הוא גרף בו .
- סדר של גרף הוא מספר הקודקודים בו, כלומר . לעתים מסומן .
- מידה של גרף היא מספר הצלעות – . לעתים מסומנת או .
- דרגה של קודקוד היא מספר הצלעות העוברות בו. מסומנת או .
- מתקיים .
- איחוד של גרפים פשוטים הוא . באותו אופן מוגדר איחוד זר.
סוגים נפוצים
- גרף ריק מסדר מסומן הוא הגרף שסדרו ומידתו 0.
- גרף מלא/שלם מסדר () הוא הגרף שסדרו ובין כל שני קודקודים יש צלע אחת בדיוק.
- מסילה מסדר () הוא הגרף שסדרו ושניתן לסדר את קודקודיו כ־ ואז .
- מעגל מסדר () הוא הגרף שסדרו ושניתן לסדר את קודקודיו כ־ ואז .
- גרף ־רגולרי הוא גרף שבו דרגת כל קודקוד היא .
- גרף הוא ריק אם״ם הוא 0־רגולרי.
- גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
- גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
- אם גרף סופי ופשוט הוא ־רגולרי כך ש־ אי־זוגי אזי הגרף מסדר זוגי.
- יער הוא גרף פשוט ללא מעגלים.
- עץ הוא יער קשיר.
הילוכים
- הילוך בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה כך ש־.
- אורך ההילוך הוא – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
- ההילוך סגור אם .
- מסלול הוא הילוך שבו אין צלעות חוזרות.
- מסילה היא הילוך שבו אין קודקודים חוזרים, למעט אם הקודקוד הראשון שווה לקודקוד האחרון.
- כל מסילה היא מסלול.
- קיים הילוך בין שני קודקודים אם״ם קיימת מסילה בינהם.
- רכיב קשירות בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות המקיים אם״ם יש מסילה בין .
- מספר רכיבי הקשירות בגרף יסומן .
- גרף קשיר הוא גרף שבו יש מחלקת שקילות אחת.
- גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.
תתי גרפים
- השמטת צלע מגרף היא הפיכת הגרף ל־.
- השמטת קודקוד מגרף היא הפיכת הגרף ל־.
- תת־גרף הוא הגרף המתקבל מסדרה של השמטות קודקודים ו/או צלעות.
- תת־גרף פורש הוא תת־גרף המתקבל מסדרה של השמטות צלעות בלבד.
- תת־גרף מושרה הוא תת־גרף המתקבל מסדרה של השמטות קודקודים בלבד.
- אם תת־גרף מושרה של אזי . כלומר, כל שני קודקודים שכנים ב־ הם שכנים ב־.