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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(הגדרות בסיסיות)
(הגדרות בסיסיות)
שורה 43: שורה 43:
 
מעגל הוא מסלול פשוט המקיים <math>v_0=v_n</math>
 
מעגל הוא מסלול פשוט המקיים <math>v_0=v_n</math>
  
אורך המסלול <math>(v_0,v_1,\dots,v_n</math> הוא <math>n</math>
+
אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>
  
 
<math>(v_0,v_1,\dots,v_n)</math> הינו מסלול מ <math>v_0</math> ל <math>v_n</math>
 
<math>(v_0,v_1,\dots,v_n)</math> הינו מסלול מ <math>v_0</math> ל <math>v_n</math>

גרסה מ־06:49, 18 באוגוסט 2014

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

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

הגדרה יהיה 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 וגם כל הצלעות שונות - כלומר לכל 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_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 שהשמטנו).

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

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

אם v שכן של v_1,v_2 - סתירה כי הדרגה של v היא 1 לכל היותר.

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

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