הגדרות בסיסיות
הגדרה: גרף מעל קבוצה
הוא זוג סדור
כאשר
- כלומר קבוצה המכילה זוגות סדורים מאיברי
.
הקבוצה היא קבוצת הקדקודים של הגרף, והקבוצה
היא קבוצת הקשתות/צלעות של הגרף.
הגדרה: הסדר של גרף הוא
. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות
סופית.
הגדרה: גרף ייקרא לא מכוון אם היחס
הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים
בתור
.
דוגמא: מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.
דוגמא: נביט בקבוצה , ובגרף
מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.
הערה: שימו לב שמהניסוח לעיל נובע-
- בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל-
.
הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות.
הגדרה יהיה . נאמר כי
שכנים אם
. במקרה זה נאמר כי הצלע
חלה ב
(או חלה ב
)
את קבוצת השכנים של מסמנים
.
הדרגה של , המסומנת
, היא מספר הצלעות החלות ב
, כלומר
.
דוגמא: במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.
משפט (לחיצת הידיים)
יהי גרף לא מכוון. אזי
.
תרגיל
נאמר כי גרף הוא
-רגולרי אם הדרגה של כל קדקוד שווה ל-
. למשל, משולש הוא גרף 2-רגולרי.
הוכח כי אם אי-זוגיים, לא קיים גרף
-רגולרי מסדר
.
הוכחה:
לפי משפט לחיצת הידיים . לכן
זוגי, ולכן
זוגי או
זוגי.
הגדרות נוספות
יהי גרף לא מכוון. סדרת קדקודים (סדורה)
נקראת מסלול אם
וגם כל הצלעות שונות - כלומר לכל
מתקיים
.
- מסלול יקרא פשוט אם כל הקדקודים
שונים זה מזה, פרט אולי ל
.
- מסלול יקרא מעגל אם
ובנוסף,
.
- מסלול יקרא מעגל פשוט אם הוא מעגל וגם מסלול פשוט.
אורך המסלול הוא
, והנקודות
ו-
נקראות נקודות ההתחלה והסיום של המסלול.
הגדרה: המרחק בין הוא המסלול עם אורך מינימלי בין
. אם אין מסלול בין הנקודות, אומרים שהמרחק הוא אינסוף. מסמנים את המרחק
, ואם יש צורך להדגיש את הגרפים אז מסמנים
.
הקוטר של גרף מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר
רכיבי קשירות
עבור גרף לא מכוון נגדיר יחס שקילות
על
, כך: לכל
מתקיים
אמ"מ קיים מסלול מ
ל-
(כלומר
).
תרגיל: הוכח כי זהו יחס שקילות.
פתרון:
- רפלקסיבי - לכל קדקוד
, המסלול
עושה את העבודה.
- סימטרי - אם
, אז יש מסלול
בין
ל-
. נביט במסלול ההפוך -
- זהו מסלול בין
ל-
, ולכן
.
- טרנזיטיבי - אם
וגם
, אז יש מסלולים
ו-
. היות ש-
, נביט במסלול
- זהו מסלול המעיד על כך ש-
.
הגדרה מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
הגדרה: G יקרא קשיר אם בין כל שני קודקודים יש מסלול. זה שקול לכך שיש רכיב קשירות או באופן שקול
דוגמא: ציור חביב לפי דעת המתרגל.
תרגילים נוספים
תרגיל
נניח כ בגרף מתקיים אז בגרף יש מעגל.
פתרון: נבחר ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ
הצעד הבא לא יהיה
(זה אפשרי כי כל קדקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קדקודים נקבל חזרה על קדקוד כלשהו בשלב כלשהו. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
תרגיל
יהי גרף בעל
קדקודים. ו-
צלעות. אזי בגרף יש מעגל.
פתרון: באינדוקציה.
עבור הגרף הוא בהכרח משולש (לא יכולות להיות יותר מ-4 צלעות עבור 3 קדקודים) ואכן יש מעגל.
נניח כי הטענה נכונה עבור ונוכיח עבור
. יהי
בעל
קדקודים ו-
צלעות.
אפשרות 0 - קיים קדקוד מדרגה 0 - כלומר אין לו שכנים. אז נביט בגרף בלי הקדקוד הזה, ומהנחת האינדוקציה נקבל שיש בו מעגל; זהו מעגל גם בגרף המקורי.
אפשרות 1: קיים מדרגה 1. נוריד את הקדקוד הזה (ואת הצלע שחלה בו) ונקבל גרף חדש עם
קדקודים ו
צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.
אפשרות 2: לכל קדקוד דרגה גדולה שווה 2. ולפי תרגיל קודם יש מעגל
תרגיל
יהי גרף מסדר
. הוכח שקיימים 2 קדקודים בעלי אותה דרגה.
פתרון: נביט בפונקציית הדרגה השולחת כל איבר אל הדרגה שלו:
; כדי להבין את התמונה של הפונקציה, נשים לב שיש שני מקרים:
- אם קיים קדקוד מדרגה
, אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה מתקיים
.
- אם אין קדקוד מדרגה
אז
.
בשני המקרים קיבלנו כי ולכן
אינה חח"ע.
כלומר קיימים
כך ש
כלומר בעלי דרגה שווה.
תרגיל
יהיה גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי
קשיר.
פתרון: יהיו . צריך להוכיח כי
(כך נסמן את רכיב הקשירות).
נניח כי הם שונים, אזי ב
( הקודוקד + לפחות 50 שכנים). אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל הפחות 102 קדקודים, סתירה.
תרגיל
יהי גרף ללא מעגלים עם
. הוכח כי קיימים
כך שדרגתם לכל היותר 1.
פתרון: לפי תרגיל קודם קיים כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם).
נמשיך באינדוקציה על מספר הקדקודים בגרף.
אם אזי או שהגרף הוא 2 נקודות ללא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הן מדרגה קטנה שווה ל-1.
כעת נניח כי הטענה נכונה עבור . נוכיח את הטענה עבור
.
נבחר את הקדקוד שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו (אם קיימת), ונקבל גרף עם
קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים
בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את
שהשמטנו). יש מספר מקרים:
- אם
שכן של
אזי
בעלי דרגה לכל היותר 1.
- אם
שכן של
אזי
בעלי דרגה לכל היותר 1.
- אם
שכן של
- סתירה כי הדרגה של
היא 1 לכל היותר.
- אם
לא שכן של
אזי
בעלי דרגה לכל היותר 1.
בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!
תרגיל
הוכח/הפרך:
- אם מתקיים
, אז
קשיר.
- קיים גרף בין שישה קדקודים 1,2,3,4,4,5.
- קיים גרף בין שישה קדקודים 1,2,3,4,5,5.
פתרון:
- לא נכון, למשל שני משולשים מופרדים.
- לא נכון, כי סכום הדרגות אי-זוגי, בסתירה למשפט לחיצת הידיים.
- הפעם משפט לחיצת הידיים לא נכשל, אך זה עדיין לא נכון - אילו היו שני קדקודים מדרגה 5, הר שכל הקדקודים היו מחוברים אל שניהם, ולכן אין קדקוד מדרגה 1.
תרגיל
יהא גרף פשוט סופי לא מכוון. נניח כי
איחוד זר (כלומר החיתוך
. עוד נניח כי קיים
כך שקיימת קשת
והיא הקשת היחידה בין
ל
.
הוכיחו שקיים קודקוד בעל דרגה אי זוגית.
פתרון: נסתכל על תת הגרף אם
בעל דרגה זוגית בו אז הוא יהיה בעל דרגה אי זוגית ב V. אחרת דרגתו ב V1 אי זוגית ולכן לפי משפט לחיצת היחדים שסכום הדרגות זוגיות, קיים עוד קודוד בעל דרגה אי זוגית ב V1. כיון שהקשת היחידה בין
ל
היא
נקבל כי קודקוד זה בעל דרגה אי זוגית גם ב G.
תרגיל
יהא גרף פשוט סופי לא מכוון בעל מעגל יחיד עם
. הוכיחו כי
פתרון: נסמן את המעגל היחידי ב G ב .
טענה:
הוכחה: נסתכל על הגרף הוא בעל
קשתות אך עדיין קשיר (כי אם יש מסלול המערב את הקשת שהורדה ניתן להחליף אותה
.) לכן לפי הרצאה יש לו לפחות
קשתות ולכן
ואחרי העברת אגפים נקבל את המבוקש.
טענה:
הוכחה: נניח בשלילה כי
נסתכל על הגרף
הוא בעל
קשתות אך הרסנו את המעגל היחידי שהיה ב G אבל לפי תרגיל ממקודם אם מספר הצלעות גדול שווה ממספר הקודקודים יש בו מעגל. סתירה.