הגדרות בסיסיות

הגדרה יהיה $V$ קבוצה לא ריקה. יהא $E$ קבוצה המכילה זוגות לא סדורים מאיברי $V$ אזי $G=(V,E)$ נקרא גרף לא מכוון.

חושבים על $V$ כקודקודים של הגרף ועל $E$ כקשתות/צלעות של הגרף. את האיברים ב $E$ נהוג לרשום כקבוצה $\{v,w\}\in E$ (בגלל שזה זוגות לא סדורים)

דוגמא: $V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}$ מייצג משולש.

הגדרה הסדר של גרף $G=(V,E)$ הוא $|V|$ . גרף יקרא סופי אם הסדר שלו סופי (וגם $E$ סופית)

אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים $\forall v\in V : \{v,v\}\not\in E$ ובלי צלעות כפולות, כלומר לא מופיע פעמיים $\{v,w\}$ ב $E$ . בנוסף הגרפים שלנו יהיו סופיים.

הגדרה יהיה $G=(V,E)$ נאמר כי $v,w\in V$ שכנים אם $\{v,w\}\in E$ .

במקרה זה נאמר כי הצלע $\{v,w\}\in E$ חלה ב $w$ (או חלה ב $v$ )

את קבוצת השכנים של $u$ מסמנים כ $\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}$

הדרגה של $u$ (סימון: $\text{degree}(u)$ )היא מספר הצלעות החלות ב $u$ או לחילופין $|\Gamma(u)|$

בדוגמא של המשולש - כל 2 קודקודים שכנים. כל קודקוד מדרגה 2. השכנים של קודקוד מספר 1 הוא קודקוד 2 + קודקוד 3.

משפט (לחיצת הידיים) יהי $G=(V,E)$ גרף לא מכוון. אזי $\sum_{v\in V}(\text{degree}(v)=2|E|)$ .

עוד הגדרות:

יהי $G=(V,E)$ גרף לא מכוון. סדרת קודקודים (סדורה) $(v_0,v_1,\dots,v_n$ נקראת מסלול אם $\forall i : \{v_i,v_{i+1}\in E\}$

מסלול יקרא פשוט אם כל הקודקודים $(v_0,v_1,\dots,v_n$ שונים זה מזה

מעגל הוא מסלול המקיים $v_0=v_n$

מעגל פשוט מסלול שכל קודקודיו שונים פרט לקודקוד הראשון והאחרון ששווים (כלומר $v_0=v_n$ )

אורך המסלול $(v_0,v_1,\dots,v_n$ הוא $n$

$(v_0,v_1,\dots,v_n$ הינו מסלול מ $v_0$ ל $v_n$

הגדרה

המרחק בין $v,u\in V$ הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון $d(u,v)$ או $d_G(u,v)$ ).

אם אין מסלול בין $v,u\in V$ נסמן $d(u,v)= \infty$

הקוטר של גרף $G=(V,E)$ מוגדר כמרחק המקסימאלי בין 2 קודקודים . כלומר $\max_{u,v\in V}(d(v,u))$

בניה

עבור גרף לא מכוון $G=(V,E)$ נגדיר יחס שקילות $\to$ על $V$ כך:

לכל $v,u\in V$ מתקיים $v\to u$ אמ"מ קיים מסלול מ $v$ ל $u$ (כלומר $d(v,u)<\infty$ )

תרגיל: הוכח כי זהו יחס שקילות

הגדרה מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

תרגילים

תרגיל: יהי גרף לא מכוון $G=(V,E)$ בעל $3\leq n$ קודקודים. אם בגרף $n\leq m$ צלעות אזי בגרף יש מעגל.

הוכחה: באינדוקציה.

עבור $n=3$ אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודים) ואכן מתקיים כי יש מעגל.

נניח כי הטכנה נכונה עבור $n$ ונוכיח עבור $n+1$ . יהי יהי גרף לא מכוון $G=(V,E)$ בעל $3< n+1$ קודקודים ו- $n+1\leq m$ צלעות.

אפשרות 1: קיים $v\in V$ מדרגה 1. נוריד את הקודקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם $n$ קודקודים ו $n\leq m-1$ צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר $v_0\in V$ ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ $v\to u$ הצעד הבא לא יהיה $u\to v$ (זה אפשרי כי כל קודקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!

תרגיל:

יהי גרף לא מכוון $G=(V,E)$ . הוכח כי אם $\forall v\in V : \text{degree}(v)\geq 2$ אז בגרף יש מעגל.

הוכחה: בגרף יש יותר מ 2 קודקודים (אחרת לא יהיה להם 2 שכנים). לפי משפט לחיצת הידיים מתקיים $2|E|= \sum_{v\in V}(\text{degree}(v)\geq \sum_{v\in V}2 =2|V|)$ ולכן מספר הצלעות גדול שווה ממספר הקודקודים. לפי משפט קודם קיים מעגל בגרף.

תרגיל:

יהי גרף לא מכוון $G=(V,E)$ ללא מעגלים עם $|V|\geq 2$ . הוכח כי קיימים $v_1,v_2\in V$ כך שדרגתם לכל היותר 1.

הוכחה: לפי תרגיל קודם קיים $v\in V$ כך שדרגתו לכל היותר 1 (אחרת לכל הקודקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם. סתירה!).

נמשיך באינדוקציה על $n$ מספר הקודקודים בגרף.

אם $n=2$ אזי או שהגרף הוא 2 נקודות לא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הם מדרגה קטנה שווה ל-1.

כעת נניח כי הטענה נכונה עבור $n\geq 2$ . נוכיח את הטענה עבור $n+1$ .

נבחר את הקודקוד $v\in V$ שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם $n$ קודקודים. לפי הנחת האינדוקציה יש בו 2 קודקודים $v_1,v_2$ בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את $v$ שהשמטנו).