|
|
עמוד:156
באיור שלהלן מוצגת דוגמה נוספת של גרף מכוון ו איור 4 . 5 דוגמה נוספת לגרף מכוון באיור הזה , הדרגה של הקדקוד D היא , 2 דרגת הכניסה שלו היא 2 ודרגת היציאה היא אפס . הדרגה של הקדקוד C היא , 3 דרגת הכניסה שלו היא , 2 ודרגת היציאה שלו היא . 1 משפט 4 . 2 . 1 בכל גרף פשוט G- ( V , E ) מתק"ם £ d ( v ) = 2 \ \ כאשר d ( v ) מצ"ן את דרגתו של הצומת vsV / v בגרף . כלומר , סכום הדרגות של הקדקודים בגרף שווה למספר הקשתות באותו גרף מוכפל פי שניים , כיוון שכל קשת נכנסת לקדקוד אחד ויוצאת מקדקוד ארוד . לולאה - קיימים גרפים שבהם יותר מקשת אחת מחברת בין שני צמתים , או קיימת לולאה - קשת המחברת צומת מסוים לעצמו . איור 4 . 6 גרף עם שני צמתים המחוברים על-ידי יותר מקשת אחת ולולאה
|
|