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

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

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

הגדרה יהיה $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$)