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

@@ שורה 1: / שורה 1: @@
 '''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
+= הגדרות בסיסיות =
+'''הגדרה''' יהיה <math>V</math> קבוצה לא ריקה. יהא <math>E</math> קבוצה המכילה זוגות לא סדורים מאיברי <math>V</math>
+אזי <math>G=(V,E)</math> נקרא גרף לא מכוון.
+חושבים על <math>V</math> כקודקודים של הגרף ועל <math>E</math> כקשתות/צלעות של הגרף. את האיברים ב <math>E</math>
+נהוג לרשום כקבוצה <math>\{v,w\}\in E</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>\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>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)