גרסה מ־09:09, 14 באוגוסט 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\}$

מסלול יקרא פשוט אם כל הקודקודים $(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 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!

תרגיל:

@@ שורה 15: / שורה 15: @@
-אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים <math>\forall v\in V : \{v,v\}\not\in E</math>
+אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים <math>\forall v\in V : \{v,v\}\not\in E</math> ובלי צלעות כפולות, כלומר לא מופיע פעמיים <math>\{v,w\}</math> ב <math>E</math>. בנוסף הגרפים שלנו יהיו סופיים.
@@ שורה 65: / שורה 65: @@
 '''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
+=תרגילים=
+תרגיל: יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קודקודים.
+אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.
+הוכחה: באינדוקציה.
+עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודים) ואכן מתקיים כי יש מעגל.
+נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.
+יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קודקודים ו- <math>n+1\leq m </math> צלעות.
+אפשרות 1: קיים <math>v\in V</math> מדרגה 1. נוריד את הקודקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קודקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.
+אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קודקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
+תרגיל:

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

גרסה מ־09:09, 14 באוגוסט 2014

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

בניה

תרגילים

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים