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