הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11"
מתוך Math-Wiki
אחיה בר-און (שיחה | תרומות) (←הגדרות בסיסיות) |
אחיה בר-און (שיחה | תרומות) (←הגדרות בסיסיות) |
||
שורה 10: | שורה 10: | ||
דוגמא: <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. | דוגמא: <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math> מייצג משולש. | ||
+ | |||
'''הגדרה''' הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי (וגם <math>E</math> סופית) | '''הגדרה''' הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי (וגם <math>E</math> סופית) | ||
+ | |||
אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים <math>\forall v\in V : \{v,v\}\not\in E</math> | אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים <math>\forall v\in V : \{v,v\}\not\in E</math> | ||
+ | |||
'''הגדרה''' יהיה <math>G=(V,E)</math> נאמר כי <math>v,w\in V</math> שכנים אם <math>\{v,w\}\in E</math>. | '''הגדרה''' יהיה <math>G=(V,E)</math> נאמר כי <math>v,w\in V</math> שכנים אם <math>\{v,w\}\in E</math>. | ||
במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>) | במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</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> |
גרסה מ־08:29, 14 באוגוסט 2014
הגדרות בסיסיות
הגדרה יהיה קבוצה לא ריקה. יהא קבוצה המכילה זוגות לא סדורים מאיברי אזי נקרא גרף לא מכוון.
חושבים על כקודקודים של הגרף ועל כקשתות/צלעות של הגרף. את האיברים ב נהוג לרשום כקבוצה (בגלל שזה זוגות לא סדורים)
דוגמא: מייצג משולש.
הגדרה הסדר של גרף הוא . גרף יקרא סופי אם הסדר שלו סופי (וגם סופית)
אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים
הגדרה יהיה נאמר כי שכנים אם .
במקרה זה נאמר כי הצלע חלה ב (או חלה ב )
את קבוצת השכנים של מסמנים כ עיבוד הנוסחה נכשל (שגיאת לקסינג): \Gamma(u)=\{v\in V \: :\; \{v,u\}\in E\}
הדרגה של היא מספר הצלעות החלות ב או לחילופין