גרסה מ־08:26, 14 באוגוסט 2014

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

הגדרה יהיה $V$ קבוצה לא ריקה. יהא $E$ קבוצה המכילה זוגות לא סדורים מאיברי $V$ אזי $G=(V,E)$ נקרא גרף לא מכוון.

חושבים על $V$ כקודקודים של הגרף ועל $E$ כקשתות/צלעות של הגרף. את האיברים ב $E$ נהוג לרשום כקבוצה $\{v,w\}\in E$ (בגלל שזה זוגות לא סדורים)

דוגמא: $V=\{1,2,3\}, E=\big\{ \big\}$ $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$ )

@@ שורה 9: / שורה 9: @@
-דוגמא: <math>V=\{1,2,3\}, E=\big{\{1,2\},\{2,3\},\{1,3\}\big}</math> מייצג משולש.
+דוגמא: <math>V=\{1,2,3\}, E=\big\{ \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> סופית)
@@ שורה 15: / שורה 17: @@
 אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים <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>)