הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏הגדרות בסיסיות)
(←‏הגדרות בסיסיות)
שורה 25: שורה 25:
  
 
הדרגה של <math>u</math> (סימון: <math>\text{degree}(u)</math>)היא מספר הצלעות החלות ב <math>u</math> או לחילופין <math>|\Gamma(u)|</math>
 
הדרגה של <math>u</math> (סימון: <math>\text{degree}(u)</math>)היא מספר הצלעות החלות ב <math>u</math> או לחילופין <math>|\Gamma(u)|</math>
 +
 +
 +
בדוגמא של המשולש - כל 2 קודקודים שכנים. כל קודקוד מדרגה 2. השכנים של קודקוד מספר 1 הוא קודקוד 2 + קודקוד 3.
 +
 +
'''משפט''' (לחיצת הידיים)
 +
יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}(\text{degree}(v)=2|E|)</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>(v_0,v_1,\dots,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,u\in V</math> הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון <math>d(u,v)</math>).
 +
 +
אם אין מסלול בין <math>v,u\in V</math> נסמן <math>d(u,v)= \infity</math>

גרסה מ־08:48, 14 באוגוסט 2014

חזרה למערכי התרגול

הגדרות בסיסיות

הגדרה יהיה V קבוצה לא ריקה. יהא E קבוצה המכילה זוגות לא סדורים מאיברי V אזי G=(V,E) נקרא גרף לא מכוון.

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


דוגמא: V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\} מייצג משולש.


הגדרה הסדר של גרף G=(V,E) הוא |V|. גרף יקרא סופי אם הסדר שלו סופי (וגם E סופית)


אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים \forall v\in V : \{v,v\}\not\in E


הגדרה יהיה G=(V,E) נאמר כי v,w\in V שכנים אם \{v,w\}\in E.

במקרה זה נאמר כי הצלע \{v,w\}\in E חלה ב w (או חלה ב v)

את קבוצת השכנים של u מסמנים כ \Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}

הדרגה של u (סימון: \text{degree}(u))היא מספר הצלעות החלות ב u או לחילופין |\Gamma(u)|


בדוגמא של המשולש - כל 2 קודקודים שכנים. כל קודקוד מדרגה 2. השכנים של קודקוד מספר 1 הוא קודקוד 2 + קודקוד 3.

משפט (לחיצת הידיים) יהי G=(V,E) גרף לא מכוון. אזי \sum_{v\in V}(\text{degree}(v)=2|E|).


עוד הגדרות:

יהי G=(V,E) גרף לא מכוון. סדרת קודקודים (סדורה) (v_0,v_1,\dots,v_n נקראת מסלול אם \forall i : \{v_i,v_{i+1}\in E\}

מסלול יקרא פשוט אם כל הקודקודים (v_0,v_1,\dots,v_n שונים זה מזה

מעגל הוא מסלול המקיים v_0=v_n

מעגל פשוט מסלול שכל קודקודיו שונים פרט לקודקוד הראשון והאחרון ששווים (כלומר v_0=v_n )

אורך המסלול (v_0,v_1,\dots,v_n הוא n

הגדרה

המרחק בין v,u\in V הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון d(u,v)).

אם אין מסלול בין v,u\in V נסמן עיבוד הנוסחה נכשל (פונקציה \infity לא מוכרת): d(u,v)= \infity

מקור: https://math-wiki.com/index.php?title=88-195_בדידה_לתיכוניסטים_תשעא/מערך_שיעור/שיעור_11&oldid=44208