'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
= הגדרות בסיסיות =
'''הגדרה''' יהיה <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>)