הגדרה : גרף G ייקרא עץ אם הוא גרף קשיר וח 0 ר מעגלים . דוגמאות לגרפים של עצים : הגדרה : גרף G ייקרא יער אם הוא גרף לא קשיר וכל רכיב בו הוא עץ . דוגמה 1 בגרף הלא-קשיר הנתון שני רכיבים ו כל אחד מהם הוא עץ . להלן מספר משפטים המכילים את התכונות העיקריות של עצים ( ללא הוכחה שלהם ) י משפט 6 . 2 . 1 בכל עץ , 7 בין כל שני קדקודים U , V קיים מסלול אחד ויחיד . משפט 6 . 2 . 2 נתון העץ הפורש . T = ( V , E ) הגרף G = ( V , E ) שבו , ^ = E - { e ] כאשר e = ( a , b ) קשת כלשהי , השייכת ל- £ 7 י הוא יער המכיל בדיוק שני עצים .
إلى الكتاب