גרסה מ־20:47, 11 באוגוסט 2015

תוכן עניינים

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$ .

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

@@ שורה 10: / שורה 10: @@
 '''הגדרה''': גרף <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>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math>  מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.
+'''דוגמא''': נביט בקבוצה <math>\mathbb{Z}\times\mathbb{Z}</math>, ובגרף <math>G</math> מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.
 '''הערה''': שימו לב שמהניסוח לעיל נובע-

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

גרסה מ־20:47, 11 באוגוסט 2015

תוכן עניינים

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

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

תרגיל

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

בניה

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים