|
|
עמוד:330
הגדרה : גרף G ייקרא יער אם הוא גרף לא קשיר וכל רכיב בו הוא עץ . דוגמה 1 בגרף הלא-קשיר הנתון שני רכיבים ו כל אחד מהם הוא עץ . להלן מספר משפטים המכילים את התכונות העיקריות של עצים ( ללא הוכחה שלהם ) י משפט 6 . 2 . 1 בכל עץ , 7 בין כל שני קדקודים U , V קיים מסלול אחד ויחיד . משפט 6 . 2 . 2 נתון העץ הפורש . T = ( V , E ) הגרף G = ( V , E ) שבו , ^ = E - { e ] כאשר e = ( a , b ) קשת כלשהי , השייכת ל- £ 7 י הוא יער המכיל בדיוק שני עצים . משפט 6 . 2 . 3 נתון הגרף . G- ( V , E ) עבור העץ הפורש T = ( V , E ) של הגרף G מתק"ם : T \ ET \ = |\/| - 1 כלומר מספר הקשתות בעץ T קטן ממספר קדקודיו . 1-ב משפט 6 . 2 . 4
|
|