הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11"
אחיה בר-און (שיחה | תרומות) |
אחיה בר-און (שיחה | תרומות) (←הגדרות בסיסיות) |
||
שורה 37: | שורה 37: | ||
יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קודקודים (סדורה) <math>(v_0,v_1,\dots,v_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>\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_0,v_1,\dots,v_n)</math> שונים זה מזה | + | מסלול יקרא פשוט אם כל הקודקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math> |
− | מעגל הוא מסלול המקיים <math>v_0=v_n</math> | + | מעגל הוא מסלול פשוט המקיים <math>v_0=v_n</math> |
− | + | ||
− | + | ||
אורך המסלול <math>(v_0,v_1,\dots,v_n</math> הוא <math>n</math> | אורך המסלול <math>(v_0,v_1,\dots,v_n</math> הוא <math>n</math> |
גרסה מ־06:48, 18 באוגוסט 2014
הגדרות בסיסיות
הגדרה יהיה קבוצה לא ריקה. יהא
קבוצה המכילה זוגות לא סדורים מאיברי
אזי
נקרא גרף לא מכוון.
חושבים על כקודקודים של הגרף ועל
כקשתות/צלעות של הגרף. את האיברים ב
נהוג לרשום כקבוצה
(בגלל שזה זוגות לא סדורים)
דוגמא: מייצג משולש.
הגדרה הסדר של גרף הוא
. גרף יקרא סופי אם הסדר שלו סופי (וגם
סופית)
אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים ובלי צלעות כפולות, כלומר לא מופיע פעמיים
ב
. בנוסף הגרפים שלנו יהיו סופיים.
הגדרה יהיה נאמר כי
שכנים אם
.
במקרה זה נאמר כי הצלע חלה ב
(או חלה ב
)
את קבוצת השכנים של מסמנים כ
הדרגה של (סימון:
)היא מספר הצלעות החלות ב
או לחילופין
בדוגמא של המשולש - כל 2 קודקודים שכנים. כל קודקוד מדרגה 2. השכנים של קודקוד מספר 1 הוא קודקוד 2 + קודקוד 3.
משפט (לחיצת הידיים)
יהי גרף לא מכוון. אזי
.
עוד הגדרות:
יהי גרף לא מכוון. סדרת קודקודים (סדורה)
נקראת מסלול אם
וגם כל הצלעות שונות - כלומר לכל
מתקיים כי
מסלול יקרא פשוט אם כל הקודקודים שונים זה מזה, פרט אולי ל
מעגל הוא מסלול פשוט המקיים
אורך המסלול הוא
הינו מסלול מ
ל
הגדרה
המרחק בין הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון
או
).
אם אין מסלול בין נסמן
הקוטר של גרף מוגדר כמרחק המקסימאלי בין 2 קודקודים . כלומר
בניה
עבור גרף לא מכוון נגדיר יחס שקילות
על
כך:
לכל מתקיים
אמ"מ קיים מסלול מ
ל
(כלומר
)
תרגיל: הוכח כי זהו יחס שקילות
הגדרה מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
תרגילים
תרגיל: יהי גרף לא מכוון בעל
קודקודים.
אם בגרף
צלעות אזי בגרף יש מעגל.
הוכחה: באינדוקציה.
עבור אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודים) ואכן מתקיים כי יש מעגל.
נניח כי הטכנה נכונה עבור ונוכיח עבור
.
יהי יהי גרף לא מכוון
בעל
קודקודים ו-
צלעות.
אפשרות 1: קיים מדרגה 1. נוריד את הקודקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם
קודקודים ו
צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.
אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ
הצעד הבא לא יהיה
(זה אפשרי כי כל קודקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
תרגיל:
יהי גרף לא מכוון . הוכח כי אם
אז בגרף יש מעגל.
הוכחה: בגרף יש יותר מ 2 קודקודים (אחרת לא יהיה להם 2 שכנים).
לפי משפט לחיצת הידיים מתקיים
ולכן מספר הצלעות גדול שווה ממספר הקודקודים. לפי משפט קודם קיים מעגל בגרף.
תרגיל:
יהי גרף לא מכוון ללא מעגלים עם
. הוכח כי קיימים
כך שדרגתם לכל היותר 1.
הוכחה: לפי תרגיל קודם קיים כך שדרגתו לכל היותר 1 (אחרת לכל הקודקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם. סתירה!).
נמשיך באינדוקציה על מספר הקודקודים בגרף.
אם אזי או שהגרף הוא 2 נקודות לא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הם מדרגה קטנה שווה ל-1.
כעת נניח כי הטענה נכונה עבור . נוכיח את הטענה עבור
.
נבחר את הקודקוד שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם
קודקודים. לפי הנחת האינדוקציה יש בו 2 קודקודים
בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את
שהשמטנו).
אם שכן של
אזי
בעלי דרגה לכל היותר 1.
אם שכן של
אזי
בעלי דרגה לכל היותר 1.
אם שכן של
- סתירה כי הדרגה של
היא 1 לכל היותר.
אם לא שכן של
אזי
בעלי דרגה לכל היותר 1.
בכל מקרה קיבלנו כי קיימים 2 קודקודים בעלי דרגה 1 לכל היותר!.