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

מתוך Math-Wiki
גרסה מ־08:56, 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_0,v_1,\dots,v_n הינו מסלול מ v_0 ל v_n

הגדרה

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

אם אין מסלול בין v,u\in V נסמן d(u,v)= \infty

הקוטר של גרף G=(V,E) מוגדר כמרחק המקסימאלי בין 2 קודקודים . כלומר \max_{u,v\in V}(d(v,u))

בניה

עבור גרף לא מכוון G=(V,E) נגדיר יחס שקילות \to על V כך:

לכל  v,u\in V מתקיים  v\to u אמ"מ קיים מסלול מv ל u (כלומר d(v,u)<\infty )