גרסה אחרונה מ־07:11, 19 באוגוסט 2019

תוכן עניינים

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

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

הגדרה: גרף $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 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

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

בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- $\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$ . למשל, משולש הוא גרף 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$ ).

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

פתרון:

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

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

$\operatorname{Im}(f) \subseteq \{1,\dots n-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$ שהשמטנו). יש מספר מקרים:

אם $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 לכל היותר!

תרגיל

הוכח/הפרך:

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

פתרון:

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

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

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

גרסה אחרונה מ־07:11, 19 באוגוסט 2019

תוכן עניינים

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

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

תרגיל

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

בניה

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

תרגיל

תרגיל

פתרון

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים