עץ (תורת הגרפים)

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

גרף לא מכוון פשוט G ייקרא עץ אם מתקיים בו אחד מהתנאים הבאים (ולכן מתקיימים כל התנאים):

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

אם ל-G יש מספר סופי (שנסמנו n) של צמתים, אז התנאים דלעיל שקולים גם לתנאים:

• G הוא גרף קשיר ויש בו n-1 קשתות.
• ב-G אין מעגל פשוט, ויש בו n-1 קשתות.

גרף שהוא חסר מעגלים נקרא יער. ניתן לראות יער בתור אוסף של עצים (ומכאן שמו).

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

אם לכל צומת בעץ יש לא יותר משני צאצאים (צמתים שיש קשת ממנו אליהם), העץ קרוי עץ בינארי.

דוגמה: בעץ שבדוגמה יש 6 צמתים, ולכן 5=6-1 קשתות. המסלול הפשוט היחיד שמחבר את צמתים 2 ו-6 הוא 2-4-5-6.

לכל גרף קשיר G יש עץ פורש, שהוא עץ המכיל את כל הצמתים של G, וכל הקשתות שלו הן קשתות של G.