שינויים

'''הגדרה''' יהיה : '''גרף''' <math>VG</math> מעל קבוצה לא ריקה. יהא <math>EV</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=\exists (Vv,Ev)</math> הוא <math>|V|\in E</math>. גרף יקרא סופי אם הסדר שלו סופי #צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (וגם כי <math>E</math> סופיתקבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

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

הגדרה נאמר כי גרף <math>G=(V,E)</math> יקרא הוא '''<math>k</math>-רגולרי ''' אם כל הדרגה של כל קודקוד היא קדקוד שווה ל-<math>k (בדיוק)</math>.

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

אם n,k אי-זוגיים אז לפי משפט לחיצת הידיים <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=(Vv_0,Ev_1,\dots,v_n)</math> גרף לא מכווןשונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. סדרת קודקודים (סדורה) אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> נקראת מסלול אםהוא <math>\forall i : \{v_i,v_{i+1}\}\in En</math> וגם כל הצלעות שונות - כלומר לכל , והנקודות <math>i\neq jv_0</math> מתקיים כי ו-<math>(v_i,v_{i+1} \neq (v_j,v_{j+1}))v_n</math>נקראות '''נקודות ההתחלה והסיום''' של המסלול.

מסלול יקרא פשוט אם כל הקודקודים '''הגדרה''': המרחק בין <math>(v_0v,v_1u\in V</math> הוא המסלול עם אורך מינימלי בין <math>v,u\dotsin V</math>. אם אין מסלול בין הנקודות,v_nאומרים שהמרחק הוא אינסוף. מסמנים את המרחק <math>d(u,v)</math> שונים זה מזה, פרט אולי ל ואם יש צורך להדגיש את הגרפים אז מסמנים <math>v_0=v_nd_G(u,v)</math>.

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

אורך המסלול ===בניה===עבור גרף לא מכוון <math>G=(v_0,v_1V,E)</math> נגדיר יחס שקילות <math>\dotsto </math> על <math>V</math>,v_n)כך: לכל <math> v,u\in V</math> הוא מתקיים <math>nv\to u</math>אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(v,u)<\infty </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>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודיםקדקודים) ואכן מתקיים כי יש מעגל.

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

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

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

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

הוכחה'''תרגיל''': יהיו יהיה <math>vG=(V,u\in VE)</math> צריך להוכיח כי <math>[v]=[u]</math> (גרף פשוט עם 100 קדקודים כך נסמן את רכיב הקשירות)שדרגת כל קדקוד לפחות 50.נניח הוכח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50G</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. סתירה

הוכחה'''תרגיל''': בגרף יש יותר מ 2 קודקודים יהי גרף לא מכוון <math>G=(אחרת לא יהיה להם 2 שכניםV,E)</math>.לפי משפט לחיצת הידיים מתקיים הוכח כי אם <math>2|E|= \sum_{forall 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>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקודקודים הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם. סתירה!).

נמשיך באינדוקציה על <math>n</math> מספר הקודקודים הקדקודים בגרף.

נבחר את הקודקוד הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קודקודיםקדקודים. לפי הנחת האינדוקציה יש בו 2 קודקודיםקדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).

בכל מקרה קיבלנו כי קיימים 2 קודקודים קדקודים בעלי דרגה 1 לכל היותר!.