שינויים

'''הגדרה''' יהיה : '''גרף''' <math>VG</math> מעל קבוצה לא ריקה. יהא <math>V</math> הוא זוג סדור <math>G=(V,E)</math> קבוצה המכילה זוגות לא סדורים מאיברי כאשר <math>E \subseteq V\times V</math>אזי - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>G=(V,E)</math> נקרא גרף לא מכוון.

חושבים על הקבוצה <math>V</math> כקודקודים היא קבוצת ה'''קדקודים''' של הגרף ועל , והקבוצה <math>E</math> כקשתותהיא קבוצת הקשתות/צלעות של הגרף. את האיברים ב <math>E</math> נהוג לרשום כקבוצה <math>\{v,w\}\in E</math> (בגלל שזה זוגות לא סדורים)

דוגמא'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>V=\{1,2,3\}, E=\Big\{\{1</math> הוא סימטרי,2\}כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון,\{2אין משמעות לכיוון הצלע,3\}ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{1u,3\}\Bigv\}</math> מייצג משולש.

'''הגדרהדוגמא''' הסדר של גרף : נביט בקבוצה <math>G=(V,E)\mathbb{Z}\times\mathbb{Z}</math> הוא , ובגרף <math>|V|G</math>מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף יקרא סופי אם הסדר שלו סופי (וגם <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)u</math> נאמר כי מסמנים <math>\Gamma(u)=\{v,w\in V</math> שכנים אם <math>\; :\; \{v,wu\}\in E\}</math>.

במקרה זה נאמר כי הצלע ה'''דרגה''' של <math>\{vu</math>,wהמסומנת <math>\text{degree}\in E(u)</math> חלה , היא מספר הצלעות החלות ב <math>wu</math> (או חלה ב , כלומר <math>v|\Gamma(u)|</math>).

הדרגה של <math>u</math> (סימון'''דוגמא: <math>\text{degree}(u)</math>)היא מספר הצלעות החלות ב <math>u</math> או לחילופין <math>|\Gamma(u)|</math>''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.

בדוגמא של המשולש - כל 2 קודקודים שכנים. כל קודקוד מדרגה 2==משפט (לחיצת הידיים)==יהי <math>G=(V,E)</math> גרף לא מכוון. השכנים של קודקוד מספר 1 הוא קודקוד אזי <math>\sum_{v\in V}\text{degree}(v)=2 + קודקוד 3|E|</math>.

'''משפט''' (לחיצת הידיים)יהי הוכח כי אם <math>G=(Vk,E)n</math> גרף אי-זוגיים, לא מכוון. אזי קיים גרף <math>k</math>-רגולרי מסדר <math>\sum_{v\in V}\text{degree}(v)=2|E|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>\forall i : \{v_i, פרט אולי ל v_{i+1}\}\in E</math>v_0=v_nוגם כל הצלעות שונות - כלומר לכל <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_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.

אורך המסלול '''הגדרה''': המרחק בין <math>(v_0,v_1v,u\dotsin V</math> הוא המסלול עם אורך מינימלי בין <math>v,v_nu\in V</math> . אם אין מסלול בין הנקודות, אומרים שהמרחק הוא אינסוף. מסמנים את המרחק <math>nd(u,v)</math>, ואם יש צורך להדגיש את הגרפים אז מסמנים <math>d_G(u,v)</math>.

ה'''קוטר''' של גרף <math>G=(v_0V,v_1,\dots,v_nE)</math> הינו מסלול מ מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>v_0</math> ל <math>v_n\operatorname{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>

המרחק בין <math>v,u\in V</math> הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון <math>d(u,v)</math> או <math>d_G(u,v)</math> )'''תרגיל''': הוכח כי זהו יחס שקילות.

'''פתרון''':# ''רפלקסיבי'' - לכל קדקוד <math>v</math>, המסלול <math>(v)</math> עושה את העבודה.# ''סימטרי'' - אם אין <math> u\to v</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>u</math> ל-<math>v</math>. נביט במסלול ההפוך - <math> (v_n,uv_{n-1}\in Vdots ,v_1,v_0)</math> נסמן - זהו מסלול בין <math>v</math> ל-<math>d(u</math>,ולכן <math>v\to u</math>.# ''טרנזיטיבי'' - אם <math> u\to v</math> וגם <math> v\to w</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> u\inftyto w</math>.

הקוטר '''הגדרה''' מחלקות השקילות של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין 2 קודקודים יחס זה נקראים רכיבי קשירות. כלומר <math>\max_{u,v\in V}d(v,u)</math>

הגדרה: G יקרא קשיר אם בין כל שני קודקודים יש מסלול. זה שקול לכך שיש רכיב קשירות או באופן שקול <math>\forall v\in V:[v]_{\to}==בניה==V</math>

עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math> כך'''דוגמא''':ציור חביב לפי דעת המתרגל.

לכל =תרגילים נוספים===תרגיל==נניח כ בגרף מתקיים <math> \forall v,u\in V</math> מתקיים <math> v: \to u</math> אמ"מ קיים מסלול מ<math>v</math> ל <math>u</math> (כלומר <math>doperatorname{degre}(v,u)<\infty geq 2</math>)אז בגרף יש מעגל.

תרגיל'''פתרון''': הוכח נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי זהו יחס שקילותכל קדקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קדקודים נקבל חזרה על קדקוד כלשהו בשלב כלשהו. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!

'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות==תרגיל==יהי <math>G=(V,E)</math> גרף, ונסמן <math>\delta_G=\underset{v\in V}{\min}\{deg(V)\}</math> את הדרגה המינימלית בגרף.נניח <math>\delta_G\geq 1</math>. הוכיחו:

=תרגילים=תרגיל: יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קודקודיםא.אם יש בגרף מסלול פשוט מאורך לפחות <math>n\leq m delta_G</math> צלעות אזי בגרף יש מעגל.

הוכחה: באינדוקציהב. יש בגרף מעגל פשוט מאורך לפחות <math>\delta_G+1</math>.

עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודים) ואכן מתקיים כי יש מעגל.==פתרון===

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>א.יהי יהי גרף לא מכוון <math>G=(Vv_1,Ev_2,\dots ,v_k)</math> בעל מסלול פשוט מאורך מקסימלי. מתקיים: <math>3< n+1\deg(v_1)\geq \delta_G</math> קודקודים ו- . טענה: כל שכניו נמצאים במסלול. הוכחה: אחרת אפשר להוסיף שכן שלא במסלול לתחילת המסלול ולקבל מסלול פשוט ארוך יותר בסתירה למקסימליות. לכן אורך המסלול לפחות כמו <math>n+1\leq m delta_G</math> צלעות.

אפשרות 1: קיים ב. יהי <math>v(v_1,v_2,\in Vdots ,v_k)</math> מדרגה 1מסלול פשוט מאורך מקסימלי. נוריד ראינו שכל שכני הראשון במסלול, ולכן מספיק לקחת את הקודקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם המסלול עד שמגיעים לאחרון השכנים, ואז לחזור חזרה ל <math>nv_1</math> קודקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. ולקבל מעגל זה קיים גם בגרף בו התחלנופשוט מהאורך המתאים.

אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר ==תרגיל==יהי <math>v_0\in G=(V,E)</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ גרף בעל <math>vn\to uge 3</math> הצעד הבא לא יהיה קדקודים. ו-<math>um \to vge n </math> (זה אפשרי כי כל קודקוד צלעות. אזי בגרף יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב)מעגל. כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!

נניח כי הטענה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>. יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם בעל <math>n+1>3</math> קדקודים ו- <math> m\forall v\in V : \text{degree}(v)\geq 2ge n+1</math> אז בגרף יש מעגלצלעות.

הוכחה: בגרף יש יותר מ 2 קודקודים (אחרת לא יהיה להם 2 ''אפשרות 0'' - קיים קדקוד מדרגה 0 - כלומר אין לו שכנים).לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>ולכן מספר הצלעות גדול שווה ממספר הקודקודים. לפי משפט קודם קיים אז נביט בגרף בלי הקדקוד הזה, ומהנחת האינדוקציה נקבל שיש בו מעגל; זהו מעגל גם בגרףהמקורי.

תרגיל''אפשרות 2'':לכל קדקוד דרגה גדולה שווה 2. ולפי תרגיל קודם יש מעגל

==תרגיל==יהי גרף לא מכוון <math>G=(V,E)</math> ללא מעגלים עם גרף מסדר <math>|V|\geq 2n>1</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1שקיימים 2 קדקודים בעלי אותה דרגה.

הוכחה'''פתרון: לפי תרגיל קודם קיים ''' נביט בפונקציית הדרגה <math>v\in operatorname{deg}:V\to \{0,1,\dots,n-1\}</math> כך שדרגתו לכל היותר השולחת כל איבר אל הדרגה שלו: <math>v\mapsto \operatorname{deg}(v)</math>; כדי להבין את התמונה של הפונקציה, נשים לב שיש שני מקרים:#אם קיים קדקוד מדרגה <math>n-1 </math>, אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה מתקיים <math>\operatorname{Im}(אחרת לכל הקודקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודםf) \subseteq \{1,\dots n-1\} </math>. סתירה!#אם אין קדקוד מדרגה <math>n-1</math> אז <math>\operatorname{Im}(f)\subseteq \{0,1,\dots n-2\} </math>.

נמשיך באינדוקציה על בשני המקרים קיבלנו כי <math>|\operatorname{dom}(f)|=|V|=n, |\operatorname{Im}(f)|\le 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. הוכח כי <math>G</math> קשיר. '''פתרון''': יהיו <math>v,u\in V</math>. צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).נניח כי הם שונים, אזי ב<math>|[v]|,|[u]|\geq 51</math> ( הקודוקד + לפחות 50 שכנים). אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל הפחות 102 קדקודים, סתירה. '''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <math>G=(V,E)</math> גרף עם <math>|V|=n</math>. הוכיחו שאם דרגת כל קודקוד היא לפחות <math>\frac{n-1}{2}</math> אז <math>diam(G)\leq 2</math>, ובפרט <math>G</math> קשיר. הוכחה: יהיו <math>v,u\in V</math>. אם הם שכנים אז <math>d(v,u)=1</math>. אם לא, אז נניח בשלילה שאין להם שכן משותף ונקבל ש- <math>\Gamma(v)\cap \Gamma(u)=\varnothing</math>, ובנוסף <math>|\Gamma(v)|,|\Gamma(u)|\geq \frac{n-1}{2}</math>, ולכן יש בגרף לפחות <math>|\Gamma(v)\cup \Gamma(u)\cup \{v,u\}|=2\cdot \frac{n-1}{2}+2=n+1</math> קודקודים (נובע מכך שהאיחוד זר) בסתירה. לכן יש להם שכן משותף ולכן <math>d(v,u)=2</math>. בסה"כ נקבל <math>\forall v,u:d(v,u)\leq 2</math> ולכן <math>diam(G)\leq 2</math>. ==תרגיל==יהי <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>n</math>, מספר הקדקודים בגרף. אם <math>n=2</math> אזי או שהגרף הוא 2 נקודות לא ללא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הם הן מדרגה קטנה שווה ל-1.

נבחר את הקודקוד הקדקוד <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_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1. # אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.# אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.  בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר! ==תרגיל==הוכח/הפרך:# אם מתקיים <math>\forall v \in V: \operatorname{deg}(v)\ge2</math>, אז <math>G</math> קשיר.# קיים גרף בן שישה קדקודים 1,2,3,4,4,5.# קיים גרף בן שישה קדקודים 1,2,3,4,5,5. '''פתרון''':# לא נכון, למשל שני משולשים מופרדים.# לא נכון, כי סכום הדרגות אי-זוגי, בסתירה למשפט לחיצת הידיים.# הפעם משפט לחיצת הידיים לא נכשל, אך זה עדיין לא נכון - אילו היו שני קדקודים מדרגה 5, הר שכל הקדקודים היו מחוברים אל שניהם, ולכן אין קדקוד מדרגה 1. ==תרגיל==יהא <math>G=(V,E)</math> גרף פשוט סופי לא מכוון. נניח כי <math>V=V_1\cup V_2</math> איחוד זר (כלומר החיתוך <math>V_1\cap V_2=\emptyset</math>. עוד נניח כי קיים <math>v_i\in V_i</math> כך שקיימת קשת <math>(v_1,v_2)\in E</math> והיא הקשת היחידה בין <math>V_1</math> ל <math>V_2</math>. הוכיחו שקיים קודקוד בעל דרגה אי זוגית. פתרון: נסתכל על תת הגרף <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>G=(V,E)</math> גרף פשוט סופי לא מכוון קשיר בעל מעגל יחיד עם <math>3\leq |V|</math>. הוכיחו כי <math>|E|=|V|</math>  פתרון: נסמן את המעגל היחידי ב G ב <math>C=(v_0,\dots,v_n)</math>. טענה: <math>|V|\leq |E|</math> הוכחה: נסתכל על הגרף <math>G'=(V,E\setminus \{v_{n-1},v_n\})</math> הוא בעל <math>|E|-1</math> קשתות אך עדיין קשיר (כי אם יש מסלול המערב את הקשת שהורדה ניתן להחליף אותה <math>C=(v_0,\dots,v_{n-1})</math>.) לכן לפי הרצאה יש לו לפחות <math>|V|-1</math> קשתות ולכן <math>|V|-1\leq |E|-1</math> ואחרי העברת אגפים נקבל את המבוקש. טענה: <math>|E|\leq |V|</math> הוכחה: נניח בשלילה כי <math>|V|+1\leq |E|</math> נסתכל על הגרף <math>G'=(V,E\setminus \{v_{n-1},v_n\})</math>הוא בעל <math>|V| \leq|E|-1</math> קשתות אך הרסנו את המעגל היחידי שהיה ב G אבל לפי תרגיל ממקודם אם מספר הצלעות גדול שווה ממספר הקודקודים יש בו מעגל. סתירה.

אם <math>v</math> שכן ==תרגיל==א. מהו הקוטר המקסימלי של גרף קשיר עם <math>v_1n</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1. קודקודים?

אם <math>v</math> שכן ב. מהו המספר המינימלי של קשתות בגרף עם <math>v_2n</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1. קודקודים וקוטר 2?

אם א. <math>vn-1</math> . לא שכן של יכול להיות יותר כי הקוטר מוגדר כמרחק המקסימלי בין קודקודים, ומרחק הוא אורך המסלול הקצר, ומסלול קצר לא מכיל מעגלים, ולכן מכיל לכל היותר <math>v_1,v_2n</math> אזי קודקודים, ולכן לכל היותר <math>v,v_1,v_2n-1</math> בעלי דרגה לכל היותר קשתות. גרף קו הוא עם קוטר <math>n-1</math> כי זה המרחק בין הימני ביותר לשמאלי ביותר, לכן זה הקוטר המקסימלי.

בכל מקרה קיבלנו ב. <math>n-1</math>. לא יכול להיות פחות כי קיימים אז הגרף לא יהיה קשיר וקטרו יהיה אינסוף ולא 2 . גרף כוכב (יש קודקוד <math>u</math> המקיים <math>E=\{\{u,v\}:u\neq v\}</math> כלומר, הוא מחובר לכולם ואין עוד קשתות) הוא עם <math>n-1</math> קשתות וקוטר 2, כי המרחק בין שני קודקודים בעלי דרגה שאינם <math>u</math> הוא 2 (ואם אחד מהם הוא <math>u</math> אז 1 לכל היותר!).