88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11: הבדלים בין גרסאות בדף
אחיה בר-און (שיחה | תרומות) |
אחיה בר-און (שיחה | תרומות) |
||
| שורה 24: | שורה 24: | ||
את קבוצת השכנים של <math>u</math> מסמנים כ <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math> | את קבוצת השכנים של <math>u</math> מסמנים כ <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math> | ||
הדרגה של <math>u</math> היא מספר הצלעות החלות ב <math>u</math> או לחילופין <math>|\Gamma(u)|</math> | הדרגה של <math>u</math> (סימון: <math>\text{degree}{u}</math>)היא מספר הצלעות החלות ב <math>u</math> או לחילופין <math>|\Gamma(u)|</math> | ||
גרסה מ־08:31, 14 באוגוסט 2014
הגדרות בסיסיות
הגדרה יהיה [math]\displaystyle{ V }[/math] קבוצה לא ריקה. יהא [math]\displaystyle{ E }[/math] קבוצה המכילה זוגות לא סדורים מאיברי [math]\displaystyle{ V }[/math] אזי [math]\displaystyle{ G=(V,E) }[/math] נקרא גרף לא מכוון.
חושבים על [math]\displaystyle{ V }[/math] כקודקודים של הגרף ועל [math]\displaystyle{ E }[/math] כקשתות/צלעות של הגרף. את האיברים ב [math]\displaystyle{ E }[/math] נהוג לרשום כקבוצה [math]\displaystyle{ \{v,w\}\in E }[/math] (בגלל שזה זוגות לא סדורים)
דוגמא: [math]\displaystyle{ V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\} }[/math] מייצג משולש.
הגדרה הסדר של גרף [math]\displaystyle{ G=(V,E) }[/math] הוא [math]\displaystyle{ |V| }[/math]. גרף יקרא סופי אם הסדר שלו סופי (וגם [math]\displaystyle{ E }[/math] סופית)
אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים [math]\displaystyle{ \forall v\in V : \{v,v\}\not\in E }[/math]
הגדרה יהיה [math]\displaystyle{ G=(V,E) }[/math] נאמר כי [math]\displaystyle{ v,w\in V }[/math] שכנים אם [math]\displaystyle{ \{v,w\}\in E }[/math].
במקרה זה נאמר כי הצלע [math]\displaystyle{ \{v,w\}\in E }[/math] חלה ב [math]\displaystyle{ w }[/math] (או חלה ב [math]\displaystyle{ v }[/math])
את קבוצת השכנים של [math]\displaystyle{ u }[/math] מסמנים כ [math]\displaystyle{ \Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\} }[/math]
הדרגה של [math]\displaystyle{ u }[/math] (סימון: [math]\displaystyle{ \text{degree}{u} }[/math])היא מספר הצלעות החלות ב [math]\displaystyle{ u }[/math] או לחילופין [math]\displaystyle{ |\Gamma(u)| }[/math]