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

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

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

הגדרה יהיה [math]\displaystyle{ V }[/math] קבוצה לא ריקה. יהא [math]\displaystyle{ E }[/math] קבוצה המכילה זוגות לא סדורים מאיברי [math]\displaystyle{ V }[/math] אזי [math]\displaystyle{ G=(V,E) }[/math] נקרא גרף לא מכוון.

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

דוגמא: [math]\displaystyle{ V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\} }[/math] מייצג משולש.

הגדרה הסדר של גרף [math]\displaystyle{ G=(V,E) }[/math] הוא [math]\displaystyle{ |V| }[/math]. גרף יקרא סופי אם הסדר שלו סופי (וגם [math]\displaystyle{ E }[/math] סופית)

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

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

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

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

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

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

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

עוד הגדרות:

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

מסלול יקרא פשוט אם כל הקודקודים [math]\displaystyle{ (v_0,v_1,\dots,v_n) }[/math] שונים זה מזה

מעגל הוא מסלול המקיים [math]\displaystyle{ v_0=v_n }[/math]

מעגל פשוט מסלול שכל קודקודיו שונים פרט לקודקוד הראשון והאחרון ששווים (כלומר [math]\displaystyle{ v_0=v_n }[/math] )

אורך המסלול [math]\displaystyle{ (v_0,v_1,\dots,v_n }[/math] הוא [math]\displaystyle{ n }[/math]

[math]\displaystyle{ (v_0,v_1,\dots,v_n) }[/math] הינו מסלול מ [math]\displaystyle{ v_0 }[/math] ל [math]\displaystyle{ v_n }[/math]

הגדרה

המרחק בין [math]\displaystyle{ v,u\in V }[/math] הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון [math]\displaystyle{ d(u,v) }[/math] או [math]\displaystyle{ d_G(u,v) }[/math] ).

אם אין מסלול בין [math]\displaystyle{ v,u\in V }[/math] נסמן [math]\displaystyle{ d(u,v)= \infty }[/math]

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

בניה

עבור גרף לא מכוון [math]\displaystyle{ G=(V,E) }[/math] נגדיר יחס שקילות [math]\displaystyle{ \to }[/math] על [math]\displaystyle{ V }[/math] כך:

לכל [math]\displaystyle{ v,u\in V }[/math] מתקיים [math]\displaystyle{ v\to u }[/math] אמ"מ קיים מסלול מ[math]\displaystyle{ v }[/math] ל [math]\displaystyle{ u }[/math] (כלומר [math]\displaystyle{ d(v,u)\lt \infty }[/math])

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

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

תרגילים

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

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

עבור [math]\displaystyle{ n=3 }[/math] אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודים) ואכן מתקיים כי יש מעגל.

נניח כי הטכנה נכונה עבור [math]\displaystyle{ n }[/math] ונוכיח עבור [math]\displaystyle{ n+1 }[/math]. יהי יהי גרף לא מכוון [math]\displaystyle{ G=(V,E) }[/math] בעל [math]\displaystyle{ 3\lt n+1 }[/math] קודקודים ו- [math]\displaystyle{ n+1\leq m }[/math] צלעות.

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

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

תרגיל:

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

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

תרגיל:

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

הוכחה: לפי תרגיל קודם קיים [math]\displaystyle{ v\in V }[/math] כך שדרגתו לכל היותר 1 (אחרת לכל הקודקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם. סתירה!).

נמשיך באינדוקציה על [math]\displaystyle{ n }[/math] מספר הקודקודים בגרף.

אם [math]\displaystyle{ n=2 }[/math] אזי או שהגרף הוא 2 נקודות לא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הם מדרגה קטנה שווה ל-1.

כעת נניח כי הטענה נכונה עבור [math]\displaystyle{ n\geq 2 }[/math]. נוכיח את הטענה עבור [math]\displaystyle{ n+1 }[/math].

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

אם [math]\displaystyle{ v }[/math] שכן של [math]\displaystyle{ v_1 }[/math] אזי [math]\displaystyle{ v,v_2 }[/math] בעלי דרגה לכל היותר 1.

אם [math]\displaystyle{ v }[/math] שכן של [math]\displaystyle{ v_2 }[/math] אזי [math]\displaystyle{ v,v_1 }[/math] בעלי דרגה לכל היותר 1.

אם [math]\displaystyle{ v }[/math] שכן של [math]\displaystyle{ v_1,v_2 }[/math] - סתירה כי הדרגה של [math]\displaystyle{ v }[/math] היא 1 לכל היותר.

אם [math]\displaystyle{ v }[/math] לא שכן של [math]\displaystyle{ v_1,v_2 }[/math] אזי [math]\displaystyle{ v,v_1,v_2 }[/math] בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קודקודים בעלי דרגה 1 לכל היותר!.