גרסה מ־19:05, 11 באוגוסט 2015

תוכן עניינים

1 הגדרות בסיסיות
- 1.1 משפט (לחיצת הידיים)
  - 1.1.1 תרגיל
- 1.2 הגדרות נוספות
  - 1.2.1 בניה
2 תרגילים נוספים

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

הגדרה: גרף $G$ מעל קבוצה $V$ הוא זוג סדור $G=(V,E)$ כאשר math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי $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, כמספר הצלעות במשולש, ובפרט הוא סופי.

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

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

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

הוכחה:

לפי משפט לחיצת הידיים $2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k$ . אבל מכפלה של מספרים אי זוגיים היא אי-זוגית, ולכן $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)$ מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר $\text{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(v,u)<\infty$ ).

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

פתרון:

רפלקסיבי - לכל קדקוד, המסלול $(v)$ עושה את העבודה.
סימטרי - אם $v\to u$ , אז יש מסלול $(v_0,\dots,v_n)$ בין $v$ ל- $u$ . נביט במסלול ההפוך - $(v_n, v_{n-1}\dots ,v_1,v_0)$ - זהו מסלול בין $u$ ל- $v$ , ולכן $u \to v$ .
טרנזיטיבי - אם $v\to u$ וגם $u\to t$ , אז יש מסלולים $(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')$ - זהו מסלול המעיד על כך ש- $v\to t$ .

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

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

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

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

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

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

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

בשני המקרים קיבלנו כי $|dom(f)|=|V|=n, |Im(f)|=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 50$ והם זרים. לכן $[v]=[u]=50$ אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה

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

@@ שורה 2: / שורה 2: @@
 = הגדרות בסיסיות =
-'''הגדרה''' יהיה <math>V</math> קבוצה לא ריקה. יהא <math>E</math> קבוצה המכילה זוגות לא סדורים מאיברי <math>V</math>
+'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.
-אזי <math>G=(V,E)</math> נקרא גרף לא מכוון.
-חושבים על <math>V</math> כקודקודים של הגרף ועל <math>E</math> כקשתות/צלעות של הגרף. את האיברים ב <math>E</math>
+הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.
-נהוג לרשום כקבוצה <math>\{v,w\}\in E</math> (בגלל שזה זוגות לא סדורים)
+'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.
-דוגמא: <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math>  מייצג משולש.
+'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.
+'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math>  מייצג משולש. הסדר שלו הוא 3, כמספר הצלעות במשולש, ובפרט הוא סופי.
-'''הגדרה''' הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי (וגם <math>E</math> סופית)
+'''הערה''': שימו לב שמהניסוח לעיל נובע-
+# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
+#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.
+'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.
-אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים <math>\forall v\in V : \{v,v\}\not\in E</math> ובלי צלעות כפולות, כלומר לא מופיע פעמיים <math>\{v,w\}</math> ב <math>E</math>. בנוסף הגרפים שלנו יהיו סופיים.
+'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)
+את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.
-'''הגדרה''' יהיה <math>G=(V,E)</math>  נאמר כי <math>v,w\in V</math> שכנים אם <math>\{v,w\}\in E</math>.
+ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.
-במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)
-את קבוצת השכנים של <math>u</math> מסמנים כ <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>
+'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.
-הדרגה של <math>u</math> (סימון: <math>\text{degree}(u)</math>)היא מספר הצלעות החלות ב <math>u</math> או לחילופין <math>|\Gamma(u)|</math>
+==משפט (לחיצת הידיים)==
+יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.
-בדוגמא של המשולש - כל 2 קודקודים שכנים. כל קודקוד מדרגה 2. השכנים של קודקוד מספר 1 הוא קודקוד 2 + קודקוד 3.
-==משפט''' (לחיצת הידיים)==
-יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.
 === תרגיל ===
-הגדרה גרף <math>G=(V,E)</math> יקרא k-רגולרי אם כל הדרגה של כל קודקוד היא k (בדיוק)
+נאמר כי גרף <math>G=(V,E)</math> הוא '''<math>k</math>-רגולרי''' אם כל הדרגה של כל קדקוד שווה ל-<math>k</math>.
-הוכח כי לא קיים גרף k-רגולרי מסדר n אם n,k אי-זוגיים
+הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.
 הוכחה:
-אם n,k אי-זוגיים אז לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>.
+לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. אבל מכפלה של מספרים אי זוגיים היא אי-זוגית, ולכן <math>k</math> זוגי או <math>n</math> זוגי.
-אבל מכפלה של מספרים אי זוגיים היא אי-זוגית. סתירה
+==הגדרות נוספות==
-==עוד הגדרות:==
+יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.
-יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קודקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת מסלול אם
+מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.
-<math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים כי <math>(v_i,v_{i+1} \neq (v_j,v_{j+1}))</math>
-מסלול יקרא פשוט אם כל הקודקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>
+'''הגדרה''': המרחק בין <math>v,u\in V</math> הוא המסלול עם אורך מינימלי בין <math>v,u\in V</math>. אם אין מסלול בין הנקודות, אומרים שהמרחק הוא אינסוף. מסמנים את המרחק <math>d(u,v)</math>, ואם יש צורך להדגיש את הגרפים אז מסמנים <math>d_G(u,v)</math>.
-מעגל הוא מסלול פשוט המקיים <math>v_0=v_n</math>
+ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\text{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>
-אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>
+===בניה===
+עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(v,u)<\infty </math>).
-<math>(v_0,v_1,\dots,v_n)</math> הינו מסלול מ <math>v_0</math> ל <math>v_n</math>
+'''תרגיל''': הוכח כי זהו יחס שקילות.
-'''הגדרה'''
+'''פתרון''':
+# ''רפלקסיבי'' - לכל קדקוד, המסלול <math>(v)</math> עושה את העבודה.
+# ''סימטרי'' - אם <math> v\to u</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>v</math> ל-<math>u</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>u</math> ל-<math>v</math>, ולכן <math>u \to v</math>.
+# ''טרנזיטיבי'' - אם <math> v\to u</math> וגם <math> u\to t</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> v\to t</math>.
-המרחק בין <math>v,u\in V</math> הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון <math>d(u,v)</math> או <math>d_G(u,v)</math> ).
+'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
-אם אין מסלול בין <math>v,u\in V</math> נסמן <math>d(u,v)= \infty</math>
+'''דוגמא''': ציור חביב לפי דעת המתרגל.
-הקוטר של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין 2 קודקודים . כלומר <math>\max_{u,v\in V}d(v,u)</math>
-==בניה==
-עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math> כך:
-לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל <math>u</math> (כלומר <math>d(v,u)<\infty </math>)
-תרגיל: הוכח כי זהו יחס שקילות
-'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
-=תרגילים=
+=תרגילים נוספים=
-==תרגיל:==
+'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.
-יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קודקודים.
 אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.
-הוכחה: באינדוקציה.
+'''פתרון''': באינדוקציה.
-עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודים) ואכן מתקיים כי יש מעגל.
+עבור <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> צלעות.
+יהי יהי גרף לא מכוון <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> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.
+אפשרות 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 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
+אפשרות 2: לכל קדקוד יש דרגה גדולה שווה 2. נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קדקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קדקודים נקבל חזרה על קדקוד בשלב כלשהו. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
-== תרגיל ==
-יהי G גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קודקודים בעל אותה דרגה.
-הוכחה:
+'''תרגיל''': יהי <math>G</math> גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגה.
-נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.
+'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.
-אם קיים קודקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קודקוד מדרגה אפס. במקרה זה נוכל להגדיר
+אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
 <math>f:V\to \{1,\dots n-1\} </math>.
-אם אין קודקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.
+אם אין קדקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.
 בשני המקרים קיבלנו כי <math>|dom(f)|=|V|=n, |Im(f)|=n-1</math> ולכן <math>f</math> אינה חח"ע.
 כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה
-== תרגיל ==
-יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קודקודים כך שדרגת כל קודקוד לפחות 50. הוכח כי G קשיר.
-הוכחה: יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
+'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.
-נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קודקודים דרגת כל קודקוד קטנה שווה ל 49. סתירה
-==תרגיל:==
+'''פתרון''': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
+נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה
-יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.
-הוכחה: בגרף יש יותר מ 2 קודקודים (אחרת לא יהיה להם 2 שכנים).
+'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.
-לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
-ולכן מספר הצלעות גדול שווה ממספר הקודקודים. לפי משפט קודם קיים מעגל בגרף.
+'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
+לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
+ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.
-תרגיל:
-יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.
+'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.
-הוכחה: לפי תרגיל קודם קיים <math>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקודקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם. סתירה!).
+'''פתרון''': לפי תרגיל קודם קיים <math>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם. סתירה!).
-נמשיך באינדוקציה על <math>n</math> מספר הקודקודים בגרף.
+נמשיך באינדוקציה על <math>n</math> מספר הקדקודים בגרף.
 אם <math>n=2</math> אזי או שהגרף הוא 2 נקודות לא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הם מדרגה קטנה שווה ל-1.
@@ שורה 133: / שורה 117: @@
 כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח  את הטענה עבור <math>n+1</math>.
-נבחר את הקודקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קודקודים. לפי הנחת האינדוקציה יש בו 2 קודקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).
+נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).
 אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.
@@ שורה 143: / שורה 127: @@
 אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.
-בכל מקרה קיבלנו כי קיימים 2 קודקודים בעלי דרגה 1 לכל היותר!.
+בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.

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

גרסה מ־19:05, 11 באוגוסט 2015

תוכן עניינים

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

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

תרגיל

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

בניה

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים