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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש

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

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

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

הקבוצה V היא קבוצת הקדקודים של הגרף, והקבוצה E היא קבוצת הקשתות/צלעות של הגרף.

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

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

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

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

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

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


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

יהי G=(V,E) גרף לא מכוון. אזי \sum_{v\in V}\text{degree}(v)=2|E|.

תרגיל

נאמר כי גרף G=(V,E) הוא k-רגולרי אם הדרגה של כל קדקוד שווה ל-k. למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם k,n אי-זוגיים, לא קיים גרף k-רגולרי מסדר n.

הוכחה:

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

הגדרות נוספות

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

מסלול יקרא פשוט אם כל הקדקודים (v_0,v_1,\dots,v_n) שונים זה מזה, פרט אולי ל v_0=v_n, ובמקרה זה המסלול נקרא מעגל. אורך המסלול (v_0,v_1,\dots,v_n) הוא n, והנקודות v_0 ו-v_n נקראות נקודות ההתחלה והסיום של המסלול.

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

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

בניה

עבור גרף לא מכוון G=(V,E) נגדיר יחס שקילות \to על V, כך: לכל  v,u\in V מתקיים  v\to u אמ"מ קיים מסלול מv ל-u (כלומר u \to v \iff d(u,v)<\infty ).

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

פתרון:

  1. רפלקסיבי - לכל קדקוד v, המסלול (v) עושה את העבודה.
  2. סימטרי - אם  u\to v, אז יש מסלול  (v_0,\dots,v_n) בין u ל-v. נביט במסלול ההפוך -  (v_n, v_{n-1}\dots ,v_1,v_0) - זהו מסלול בין v ל-u, ולכן v \to u.
  3. טרנזיטיבי - אם  u\to v וגם  v\to w, אז יש מסלולים  (v_1,\dots,v_n) ו- (v_1',\dots,v_n'). היות ש- v_n=v=v_1', נביט במסלול  (v_1,\dots,v_n=v_1',\dots,v_n') - זהו מסלול המעיד על כך ש- u\to w.

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

הגדרה: G יקרא קשיר אם בין כל שני קודקודים יש מסלול. זה שקול לכך שיש רכיב קשירות או באופן שקול \forall v\in V:[v]_{\to}=V

דוגמא: ציור חביב לפי דעת המתרגל.

תרגילים נוספים

תרגיל

נניח כ בגרף מתקיים \forall v\in V : \operatorname{degre}(v)\geq 2 אז בגרף יש מעגל.

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

תרגיל

יהי G=(V,E) גרף, ונסמן \delta_G=\underset{v\in V}{\min}\{deg(V)\} את הדרגה המינימלית בגרף. נניח \delta_G\geq 1. הוכיחו:

א. יש בגרף מסלול פשוט מאורך לפחות \delta_G.

ב. יש בגרף מעגל פשוט מאורך לפחות \delta_G+1.

פתרון

א. יהי (v_1,v_2,\dots ,v_k) מסלול פשוט מאורך מקסימלי. מתקיים: \deg(v_1)\geq \delta_G. טענה: כל שכניו נמצאים במסלול. הוכחה: אחרת אפשר להוסיף שכן שלא במסלול לתחילת המסלול ולקבל מסלול פשוט ארוך יותר בסתירה למקסימליות. לכן אורך המסלול לפחות כמו \delta_G.

ב. יהי (v_1,v_2,\dots ,v_k) מסלול פשוט מאורך מקסימלי. ראינו שכל שכני הראשון במסלול, ולכן מספיק לקחת את המסלול עד שמגיעים לאחרון השכנים, ואז לחזור חזרה ל v_1 ולקבל מעגל פשוט מהאורך המתאים.

תרגיל

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

פתרון: באינדוקציה.

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

נניח כי הטענה נכונה עבור n ונוכיח עבור n+1. יהי G בעל n+1>3 קדקודים ו-  m\ge n+1 צלעות.

אפשרות 0 - קיים קדקוד מדרגה 0 - כלומר אין לו שכנים. אז נביט בגרף בלי הקדקוד הזה, ומהנחת האינדוקציה נקבל שיש בו מעגל; זהו מעגל גם בגרף המקורי.

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

אפשרות 2: לכל קדקוד דרגה גדולה שווה 2. ולפי תרגיל קודם יש מעגל

תרגיל

יהי G גרף מסדר n>1. הוכח שקיימים 2 קדקודים בעלי אותה דרגה.

פתרון: נביט בפונקציית הדרגה \operatorname{deg}:V \to \{0,1,\dots,n-1\} השולחת כל איבר אל הדרגה שלו: v\mapsto \operatorname{deg}(v); כדי להבין את התמונה של הפונקציה, נשים לב שיש שני מקרים:

  1. אם קיים קדקוד מדרגה n-1, אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה מתקיים

\operatorname{Im}(f) \subseteq \{1,\dots n-1\} .

  1. אם אין קדקוד מדרגה n-1 אז \operatorname{Im}(f) \subseteq \{0,1,\dots n-2\} .

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


תרגיל

יהיה G=(V,E) גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי G קשיר.

פתרון: יהיו v,u\in V. צריך להוכיח כי [v]=[u] (כך נסמן את רכיב הקשירות). נניח כי הם שונים, אזי ב|[v]|,|[u]|\geq 51 ( הקודוקד + לפחות 50 שכנים). אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל הפחות 102 קדקודים, סתירה.

הערה: אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי G=(V,E) גרף עם |V|=n. הוכיחו שאם דרגת כל קודקוד היא לפחות \frac{n-1}{2} אז diam(G)\leq 2, ובפרט G קשיר.

הוכחה: יהיו v,u\in V. אם הם שכנים אז d(v,u)=1. אם לא, אז נניח בשלילה שאין להם שכן משותף ונקבל ש- \Gamma(v)\cap \Gamma(u)=\varnothing, ובנוסף |\Gamma(v)|,|\Gamma(u)|\geq \frac{n-1}{2}, ולכן יש בגרף לפחות |\Gamma(v)\cup \Gamma(u)\cup \{v,u\}|=2\cdot \frac{n-1}{2}+2=n+1 קודקודים (נובע מכך שהאיחוד זר) בסתירה. לכן יש להם שכן משותף ולכן d(v,u)=2. בסה"כ נקבל \forall v,u:d(v,u)\leq 2 ולכן diam(G)\leq 2.

תרגיל

יהי 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 שהשמטנו). יש מספר מקרים:

  1. אם v שכן של v_1 אזי v,v_2 בעלי דרגה לכל היותר 1.
  2. אם v שכן של v_2 אזי v,v_1 בעלי דרגה לכל היותר 1.
  3. אם v שכן של v_1,v_2 - סתירה כי הדרגה של v היא 1 לכל היותר.
  4. אם v לא שכן של v_1,v_2 אזי v,v_1,v_2 בעלי דרגה לכל היותר 1.

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

תרגיל

הוכח/הפרך:

  1. אם מתקיים \forall v \in V: \operatorname{deg}(v)\ge2, אז G קשיר.
  2. קיים גרף בן שישה קדקודים 1,2,3,4,4,5.
  3. קיים גרף בן שישה קדקודים 1,2,3,4,5,5.

פתרון:

  1. לא נכון, למשל שני משולשים מופרדים.
  2. לא נכון, כי סכום הדרגות אי-זוגי, בסתירה למשפט לחיצת הידיים.
  3. הפעם משפט לחיצת הידיים לא נכשל, אך זה עדיין לא נכון - אילו היו שני קדקודים מדרגה 5, הר שכל הקדקודים היו מחוברים אל שניהם, ולכן אין קדקוד מדרגה 1.

תרגיל

יהא G=(V,E) גרף פשוט סופי לא מכוון. נניח כי V=V_1\cup V_2 איחוד זר (כלומר החיתוך V_1\cap V_2=\emptyset. עוד נניח כי קיים v_i\in V_i כך שקיימת קשת (v_1,v_2)\in E והיא הקשת היחידה בין V_1 ל V_2.

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

פתרון: נסתכל על תת הגרף V_1 אם v_1 בעל דרגה זוגית בו אז הוא יהיה בעל דרגה אי זוגית ב V. אחרת דרגתו ב V1 אי זוגית ולכן לפי משפט לחיצת היחדים שסכום הדרגות זוגיות, קיים עוד קודוד בעל דרגה אי זוגית ב V1. כיון שהקשת היחידה בין V_1 ל V_2 היא (v_1,v_2)\in E נקבל כי קודקוד זה בעל דרגה אי זוגית גם ב G.

תרגיל

יהא G=(V,E) גרף פשוט סופי לא מכוון קשיר בעל מעגל יחיד עם 3\leq |V|. הוכיחו כי |E|=|V|

פתרון: נסמן את המעגל היחידי ב G ב C=(v_0,\dots,v_n).

טענה: |V|\leq |E|

הוכחה: נסתכל על הגרף G'=(V,E\setminus \{v_{n-1},v_n\}) הוא בעל |E|-1 קשתות אך עדיין קשיר (כי אם יש מסלול המערב את הקשת שהורדה ניתן להחליף אותה C=(v_0,\dots,v_{n-1}).) לכן לפי הרצאה יש לו לפחות |V|-1 קשתות ולכן |V|-1\leq |E|-1 ואחרי העברת אגפים נקבל את המבוקש.

טענה: |E|\leq |V|

הוכחה: נניח בשלילה כי |V|+1\leq |E|

נסתכל על הגרף G'=(V,E\setminus \{v_{n-1},v_n\}) הוא בעל |V| \leq|E|-1 קשתות אך הרסנו את המעגל היחידי שהיה ב G אבל לפי תרגיל ממקודם אם מספר הצלעות גדול שווה ממספר הקודקודים יש בו מעגל. סתירה.

תרגיל

א. מהו הקוטר המקסימלי של גרף קשיר עם n קודקודים?

ב. מהו המספר המינימלי של קשתות בגרף עם n קודקודים וקוטר 2?

פתרון:

א. n-1. לא יכול להיות יותר כי הקוטר מוגדר כמרחק המקסימלי בין קודקודים, ומרחק הוא אורך המסלול הקצר, ומסלול קצר לא מכיל מעגלים, ולכן מכיל לכל היותר n קודקודים, ולכן לכל היותר n-1 קשתות. גרף קו הוא עם קוטר n-1 כי זה המרחק בין הימני ביותר לשמאלי ביותר, לכן זה הקוטר המקסימלי.

ב. n-1. לא יכול להיות פחות כי אז הגרף לא יהיה קשיר וקטרו יהיה אינסוף ולא 2. גרף כוכב (יש קודקוד u המקיים E=\{\{u,v\}:u\neq v\} כלומר, הוא מחובר לכולם ואין עוד קשתות) הוא עם n-1 קשתות וקוטר 2, כי המרחק בין שני קודקודים שאינם u הוא 2 (ואם אחד מהם הוא u אז 1).