שינויים
עריכה
= הגדרות בסיסיות =
'''הגדרה''' יהיה : '''גרף''' <math>VG</math> מעל קבוצה לא ריקה. יהא <math>EV</math> קבוצה המכילה זוגות לא סדורים מאיברי הוא זוג סדור <math>G=(V,E)</math>אזי כאשר math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>G=(V,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> מייצג משולש. הסדר שלו הוא 3, כמספר הצלעות במשולש, ובפרט הוא סופי.
'''הגדרההערה''' הסדר של גרף : שימו לב שמהניסוח לעיל נובע-# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>G=\exists (Vv,Ev)</math> הוא <math>|V|\in E</math>. גרף יקרא סופי אם הסדר שלו סופי #צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (וגם כי <math>E</math> סופיתקבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.
'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.
את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.
ה'''הגדרהדרגה''' יהיה של <math>G=(Vu</math>,Eהמסומנת <math>\text{degree}(u)</math> נאמר כי , היא מספר הצלעות החלות ב <math>v,w\in Vu</math> שכנים אם , כלומר <math>|\{v,w\}\in EGamma(u)|</math>.
==משפט (לחיצת הידיים)==
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.
=== תרגיל ===
הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n אם n,k אי-זוגיים</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>(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>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 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים קדקודים נקבל חזרה על קודקוד קדקוד בשלב כלשהואכלשהו. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.
אם קיים קודקוד קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קודקוד קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
<math>f:V\to \{1,\dots n-1\} </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>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=תרגיל:=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה
'''פתרון''': בגרף יש יותר מ 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>n</math> מספר הקודקודים הקדקודים בגרף.
אם <math>n=2</math> אזי או שהגרף הוא 2 נקודות לא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הם מדרגה קטנה שווה ל-1.
כעת נניח כי הטענה נכונה עבור <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</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1.
אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.
בכל מקרה קיבלנו כי קיימים 2 קודקודים קדקודים בעלי דרגה 1 לכל היותר!.