1. מהו עץ ויער?

עֵץ

• בתורת הגרפים, א עֵץ הוא גרף לא מכוון, מחובר ואציקלי . במילים אחרות, גרף מחובר שאינו מכיל אפילו מחזור אחד נקרא עץ.
• עץ מייצג מבנה היררכי בצורה גרפית.
• האלמנטים של העצים נקראים צמתים שלהם וקצוות העץ נקראים ענפים.
• לעץ עם n קודקודים יש (n-1) קצוות.
• עצים מספקים יישומים שימושיים רבים, פשוטים כמו עץ ​​משפחה ועד מורכבים כמו עצים במבני נתונים של מדעי המחשב.
• א עלה בעץ נמצא קודקוד מדרגה 1 או כל קודקוד שאין לו ילדים נקרא עלה.

דוגמא

בדוגמה לעיל, כולם עצים עם פחות מ-6 קודקודים.

יַעַר

בתורת הגרפים, א יַעַר הוא גרף לא מכוון, מנותק, אציקלי . במילים אחרות, אוסף מנותק של עצים ידוע בשם יער. כל מרכיב ביער הוא עץ.

דוגמא

הגרף שלמעלה נראה כמו שני גרפים משנה אבל הוא גרף בודד מנותק. אין מחזורים בגרף לעיל. לכן זה יער.

2. מאפיינים של עצים

1. לכל עץ שיש לו לפחות שני קודקודים צריכים להיות לפחות שני עלים.
2. לעצים יש איפיונים רבים:
   תן T להיות גרף עם n קודקודים, אז ההצהרות הבאות שוות ערך:
   • T הוא עץ.
   • T אינו מכיל מחזורים ויש לו n-1 קצוות.
   • T מחובר ויש לו (n -1) קצה.
   • T הוא גרף מחובר, וכל קצה הוא קצה חתוך.
   • כל שני קודקודים של גרף T מחוברים בנתיב אחד בדיוק.
   • T אינו מכיל מחזורים, ולכל קצה חדש e, לגרף T+e יש מחזור אחד בדיוק.
3. כל קצה של עץ חתוך.
4. הוספת קצה אחד לעץ מגדירה בדיוק מחזור אחד.
5. כל גרף מחובר מכיל עץ פורש.
6. לכל עץ יש לפחות שני קודקודים בדרגה שתיים.

3. עץ משתרע

א עץ פורש בגרף מחובר G הוא תת-גרף H של G הכולל את כל הקודקודים של G והוא גם עץ.

דוגמא

שקול את הגרף הבא G:

מהגרף G לעיל נוכל ליישם את שלושת העצים המשתרעים H:

שיטות למצוא את העץ המתפרש

אנו יכולים למצוא את העץ הפורש באופן שיטתי באמצעות אחת משתי השיטות:

1. שיטת חיתוך
2. שיטת הבנייה

1. שיטת חיתוך

• התחל לבחור כל מחזור בגרף G.
• הסר אחד מקצוות המחזור.
• חזור על תהליך זה עד שלא נותרו מחזורים.

דוגמא

• שקול גרף G,

• אם נסיר את הקצה ac שהורס את המחזור a-d-c-a בגרף למעלה, נקבל את הגרף הבא:

• הסר את הקצה cb, שהורס את המחזור a-d-c-b-a מהגרף שלמעלה ואז נקבל את הגרף הבא:

• אם נסיר את הקצה ec, אשר הורסים את המחזור d-e-c-d מהגרף שלמעלה, נקבל את העץ המתפרש הבא:

2. שיטת בנייה

• בחר קצוות של גרף G אחד בכל פעם. בצורה כזו שאין מחזורים נוצרים.
• חזור על תהליך זה עד שכל הקודקודים כלולים.

דוגמא

שקול את הגרף הבא G,

אורך מחרוזת java

• בחר את הקצה אב ,

• בחר את הקצה שֶׁל ,

• לאחר מכן, בחר את הקצה ec ,

• לאחר מכן, בחר את הקצה cb , ואז לבסוף נקבל את העץ המתפרש הבא:

דירוג מעגל

מספר הקצוות שעלינו למחוק מ-G כדי לקבל עץ פורש.

עץ משתרע G = m- (n-1) , אשר נקרא ה דירוג מעגל של G.

 Where, m = No. of edges. n = No. of vertices. 

דוגמא

בגרף שלמעלה, קצוות m = 7 וקודקודים n = 5

אז דרגת המעגל היא,

 G = m - (n - 1) = 7 - (5 - 1) = 3