הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11"
אחיה בר-און (שיחה | תרומות) |
אחיה בר-און (שיחה | תרומות) (←תרגיל:) |
||
שורה 77: | שורה 77: | ||
=תרגילים= | =תרגילים= | ||
==תרגיל:== | ==תרגיל:== | ||
− | + | יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קודקודים. | |
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל. | אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל. | ||
שורה 91: | שורה 91: | ||
אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קודקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל! | אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קודקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל! | ||
+ | == תרגיל == | ||
+ | יהי G גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <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 \{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> כלומר בעלי דרגה שווה | ||
==תרגיל:== | ==תרגיל:== |
גרסה מ־07:16, 4 באוגוסט 2015
תוכן עניינים
הגדרות בסיסיות
הגדרה יהיה קבוצה לא ריקה. יהא קבוצה המכילה זוגות לא סדורים מאיברי אזי נקרא גרף לא מכוון.
חושבים על כקודקודים של הגרף ועל כקשתות/צלעות של הגרף. את האיברים ב נהוג לרשום כקבוצה (בגלל שזה זוגות לא סדורים)
דוגמא: מייצג משולש.
הגדרה הסדר של גרף הוא . גרף יקרא סופי אם הסדר שלו סופי (וגם סופית)
אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים ובלי צלעות כפולות, כלומר לא מופיע פעמיים ב . בנוסף הגרפים שלנו יהיו סופיים.
הגדרה יהיה נאמר כי שכנים אם .
במקרה זה נאמר כי הצלע חלה ב (או חלה ב )
את קבוצת השכנים של מסמנים כ
הדרגה של (סימון: )היא מספר הצלעות החלות ב או לחילופין
בדוגמא של המשולש - כל 2 קודקודים שכנים. כל קודקוד מדרגה 2. השכנים של קודקוד מספר 1 הוא קודקוד 2 + קודקוד 3.
משפט (לחיצת הידיים)
יהי גרף לא מכוון. אזי .
תרגיל
הגדרה גרף יקרא k-רגולרי אם כל הדרגה של כל קודקוד היא k (בדיוק)
הוכח כי לא קיים גרף k-רגולרי מסדר n אם n,k אי-זוגיים
הוכחה:
אם n,k אי-זוגיים אז לפי משפט לחיצת הידיים .
אבל מכפלה של מספרים אי זוגיים היא אי-זוגית. סתירה
עוד הגדרות:
יהי גרף לא מכוון. סדרת קודקודים (סדורה) נקראת מסלול אם וגם כל הצלעות שונות - כלומר לכל מתקיים כי
מסלול יקרא פשוט אם כל הקודקודים שונים זה מזה, פרט אולי ל
מעגל הוא מסלול פשוט המקיים
אורך המסלול הוא
הינו מסלול מ ל
הגדרה
המרחק בין הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון או ).
אם אין מסלול בין נסמן
הקוטר של גרף מוגדר כמרחק המקסימאלי בין 2 קודקודים . כלומר
בניה
עבור גרף לא מכוון נגדיר יחס שקילות על כך:
לכל מתקיים אמ"מ קיים מסלול מ ל (כלומר )
תרגיל: הוכח כי זהו יחס שקילות
הגדרה מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
תרגילים
תרגיל:
יהי גרף לא מכוון בעל קודקודים. אם בגרף צלעות אזי בגרף יש מעגל.
הוכחה: באינדוקציה.
עבור אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודים) ואכן מתקיים כי יש מעגל.
נניח כי הטכנה נכונה עבור ונוכיח עבור . יהי יהי גרף לא מכוון בעל קודקודים ו- צלעות.
אפשרות 1: קיים מדרגה 1. נוריד את הקודקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם קודקודים ו צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.
אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ הצעד הבא לא יהיה (זה אפשרי כי כל קודקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
תרגיל
יהי G גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר . הוכח שקיימים 2 קודקודים בעל אותה דרגה.
הוכחה:
נבנה פונקציה המוגדרת .
אם קיים קודקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קודקוד מדרגה אפס. במקרה זה נוכל להגדיר .
אם אין קודקוד כזה אז נוכל להגדיר .
בשני המקרים קיבלנו כי עיבוד הנוסחה נכשל (שגיאת לקסינג): #dom(f)=#V=n, #Im(f)=n-1
ולכן אינה חח"ע.
כלומר קיימים כך ש כלומר בעלי דרגה שווה
תרגיל:
יהי גרף לא מכוון . הוכח כי אם אז בגרף יש מעגל.
הוכחה: בגרף יש יותר מ 2 קודקודים (אחרת לא יהיה להם 2 שכנים). לפי משפט לחיצת הידיים מתקיים ולכן מספר הצלעות גדול שווה ממספר הקודקודים. לפי משפט קודם קיים מעגל בגרף.
תרגיל:
יהי גרף לא מכוון ללא מעגלים עם . הוכח כי קיימים כך שדרגתם לכל היותר 1.
הוכחה: לפי תרגיל קודם קיים כך שדרגתו לכל היותר 1 (אחרת לכל הקודקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם. סתירה!).
נמשיך באינדוקציה על מספר הקודקודים בגרף.
אם אזי או שהגרף הוא 2 נקודות לא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הם מדרגה קטנה שווה ל-1.
כעת נניח כי הטענה נכונה עבור . נוכיח את הטענה עבור .
נבחר את הקודקוד שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם קודקודים. לפי הנחת האינדוקציה יש בו 2 קודקודים בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את שהשמטנו).
אם שכן של אזי בעלי דרגה לכל היותר 1.
אם שכן של אזי בעלי דרגה לכל היותר 1.
אם שכן של - סתירה כי הדרגה של היא 1 לכל היותר.
אם לא שכן של אזי בעלי דרגה לכל היותר 1.
בכל מקרה קיבלנו כי קיימים 2 קודקודים בעלי דרגה 1 לכל היותר!.