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

מתוך Math-Wiki
הגרסה להדפסה אינה נתמכת עוד וייתכן שיש בה שגיאות תיצוג. נא לעדכן את הסימניות בדפדפן שלך ולהשתמש בפעולת ההדפסה הרגילה של הדפדפן במקום זה.

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

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

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

הקבוצה [math]\displaystyle{ V }[/math] היא קבוצת הקדקודים של הגרף, והקבוצה [math]\displaystyle{ E }[/math] היא קבוצת הקשתות/צלעות של הגרף.

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

הגדרה: גרף [math]\displaystyle{ G }[/math] ייקרא לא מכוון אם היחס [math]\displaystyle{ E }[/math] הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים [math]\displaystyle{ (u,v) }[/math] בתור [math]\displaystyle{ \{u,v\} }[/math].

דוגמא: [math]\displaystyle{ V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\} }[/math] מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.

דוגמא: נביט בקבוצה [math]\displaystyle{ \mathbb{Z}\times\mathbb{Z} }[/math], ובגרף [math]\displaystyle{ G }[/math] מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

הערה: שימו לב שמהניסוח לעיל נובע-

  1. בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- [math]\displaystyle{ \exists (v,v) \in E }[/math].
  2. צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי [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: השכנים של כל קדקוד הם שני הקדקודים האחרים.


משפט (לחיצת הידיים)

יהי [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{ k }[/math]-רגולרי אם הדרגה של כל קדקוד שווה ל-[math]\displaystyle{ k }[/math]. למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם [math]\displaystyle{ k,n }[/math] אי-זוגיים, לא קיים גרף [math]\displaystyle{ k }[/math]-רגולרי מסדר [math]\displaystyle{ n }[/math].

הוכחה:

לפי משפט לחיצת הידיים [math]\displaystyle{ 2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k }[/math]. אבל מכפלה של מספרים אי זוגיים היא אי-זוגית, ולכן [math]\displaystyle{ k }[/math] זוגי או [math]\displaystyle{ n }[/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{ i\neq j }[/math] מתקיים [math]\displaystyle{ (v_i,v_{i+1}) \neq (v_j,v_{j+1}) }[/math].

מסלול יקרא פשוט אם כל הקדקודים [math]\displaystyle{ (v_0,v_1,\dots,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 }[/math] ו-[math]\displaystyle{ v_n }[/math] נקראות נקודות ההתחלה והסיום של המסלול.

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

הקוטר של גרף [math]\displaystyle{ G=(V,E) }[/math] מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר [math]\displaystyle{ \text{diam}(G)=\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{ u \to v \iff d(v,u)\lt \infty }[/math]).

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

פתרון:

  1. רפלקסיבי - לכל קדקוד, המסלול [math]\displaystyle{ (v) }[/math] עושה את העבודה.
  2. סימטרי - אם [math]\displaystyle{ v\to u }[/math], אז יש מסלול [math]\displaystyle{ (v_0,\dots,v_n) }[/math] בין [math]\displaystyle{ v }[/math] ל-[math]\displaystyle{ u }[/math]. נביט במסלול ההפוך - [math]\displaystyle{ (v_n, v_{n-1}\dots ,v_1,v_0) }[/math] - זהו מסלול בין [math]\displaystyle{ u }[/math] ל-[math]\displaystyle{ v }[/math], ולכן [math]\displaystyle{ u \to v }[/math].
  3. טרנזיטיבי - אם [math]\displaystyle{ v\to u }[/math] וגם [math]\displaystyle{ u\to t }[/math], אז יש מסלולים [math]\displaystyle{ (v_1,\dots,v_n) }[/math] ו-[math]\displaystyle{ (v_1',\dots,v_n') }[/math]. היות ש-[math]\displaystyle{ v_n=v=v_1' }[/math], נביט במסלול [math]\displaystyle{ (v_1,\dots,v_n=v_1',\dots,v_n') }[/math] - זהו מסלול המעיד על כך ש-[math]\displaystyle{ v\to t }[/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 }[/math] גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר [math]\displaystyle{ 1\lt n }[/math]. הוכח שקיימים 2 קדקודים בעל אותה דרגה.

פתרון: נבנה פונקציה [math]\displaystyle{ f:V\to \{0,1,\dots n-1\} }[/math] המוגדרת [math]\displaystyle{ v\mapsto deg(v) }[/math].

אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר [math]\displaystyle{ f:V\to \{1,\dots n-1\} }[/math].

אם אין קדקוד כזה אז נוכל להגדיר [math]\displaystyle{ f:V\to \{0,1,\dots n-2\} }[/math].

בשני המקרים קיבלנו כי [math]\displaystyle{ |dom(f)|=|V|=n, |Im(f)|=n-1 }[/math] ולכן [math]\displaystyle{ f }[/math] אינה חח"ע. כלומר קיימים [math]\displaystyle{ v_1\neq v_2 }[/math] כך ש [math]\displaystyle{ f(v_1)=f(v_2) }[/math] כלומר בעלי דרגה שווה


תרגיל: יהיה [math]\displaystyle{ G=(V,E) }[/math] גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי [math]\displaystyle{ G }[/math] קשיר.

פתרון: יהיו [math]\displaystyle{ v,u\in V }[/math] צריך להוכיח כי [math]\displaystyle{ [v]=[u] }[/math] (כך נסמן את רכיב הקשירות). נניח כי הם שונים אזי ב[math]\displaystyle{ |[v]|,|[u]|\geq 50 }[/math] והם זרים. לכן [math]\displaystyle{ [v]=[u]=50 }[/math] אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה


תרגיל: יהי גרף לא מכוון [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 לכל היותר!.