88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11

חזרה למערכי התרגול

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

הגדרה יהיה $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 שכנים). לפי משפט לחיצת הידיים מתקיים