88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11
מתוך Math-Wiki
הגדרות בסיסיות
הגדרה יהיה קבוצה לא ריקה. יהא
קבוצה המכילה זוגות לא סדורים מאיברי
אזי
נקרא גרף לא מכוון.
חושבים על כקודקודים של הגרף ועל
כקשתות/צלעות של הגרף. את האיברים ב
נהוג לרשום כקבוצה
(בגלל שזה זוגות לא סדורים)
דוגמא: מייצג משולש.
הגדרה הסדר של גרף הוא
. גרף יקרא סופי אם הסדר שלו סופי (וגם
סופית)
אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים
הגדרה יהיה נאמר כי
שכנים אם
.
במקרה זה נאמר כי הצלע חלה ב
(או חלה ב
)
את קבוצת השכנים של מסמנים כ
הדרגה של היא מספר הצלעות החלות ב
או לחילופין