גרסה מ־08:31, 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)|$

גרסה מ־08:31, 14 באוגוסט 2014 (הצגת מקור) אחיה בר-און (שיחה \| תרומות) (←‏הגדרות בסיסיות) → מעבר להשוואת הגרסאות הקודמת		גרסה מ־08:31, 14 באוגוסט 2014 (הצגת מקור) אחיה בר-און (שיחה \| תרומות) (←‏הגדרות בסיסיות) מעבר להשוואת הגרסאות הבאה ←
שורה 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>\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>