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