הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11"
אחיה בר-און (שיחה | תרומות) (←הגדרות בסיסיות) |
אחיה בר-און (שיחה | תרומות) (←הגדרות בסיסיות) |
||
שורה 48: | שורה 48: | ||
'''הגדרה''' | '''הגדרה''' | ||
− | המרחק בין <math>v,u\in V</math> הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון <math>d(u,v)</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>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> |
גרסה מ־08:51, 14 באוגוסט 2014
הגדרות בסיסיות
הגדרה יהיה קבוצה לא ריקה. יהא קבוצה המכילה זוגות לא סדורים מאיברי אזי נקרא גרף לא מכוון.
חושבים על כקודקודים של הגרף ועל כקשתות/צלעות של הגרף. את האיברים ב נהוג לרשום כקבוצה (בגלל שזה זוגות לא סדורים)
דוגמא: מייצג משולש.
הגדרה הסדר של גרף הוא . גרף יקרא סופי אם הסדר שלו סופי (וגם סופית)
אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים
הגדרה יהיה נאמר כי שכנים אם .
במקרה זה נאמר כי הצלע חלה ב (או חלה ב )
את קבוצת השכנים של מסמנים כ
הדרגה של (סימון: )היא מספר הצלעות החלות ב או לחילופין
בדוגמא של המשולש - כל 2 קודקודים שכנים. כל קודקוד מדרגה 2. השכנים של קודקוד מספר 1 הוא קודקוד 2 + קודקוד 3.
משפט (לחיצת הידיים) יהי גרף לא מכוון. אזי .
עוד הגדרות:
יהי גרף לא מכוון. סדרת קודקודים (סדורה) נקראת מסלול אם
מסלול יקרא פשוט אם כל הקודקודים שונים זה מזה
מעגל הוא מסלול המקיים
מעגל פשוט מסלול שכל קודקודיו שונים פרט לקודקוד הראשון והאחרון ששווים (כלומר )
אורך המסלול הוא
הגדרה
המרחק בין הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון או ).
אם אין מסלול בין נסמן
הקוטר של גרף מוגדר כמרחק המקסימאלי בין 2 קודקודים . כלומר