עץ (תורת הגרפים)
בתורת הגרפים, עץ הוא גרף קשיר ללא מעגלים. מלבד התפקיד של עצים בתורת הגרפים, כגרפים הקשירים המינימליים, ובטופולוגיה כמודל למרחב היפרבולי, עצים הנושאים מידע נוסף מהווים משפחה חשובה של מבני נתונים.
תוכן עניינים |
הגדרות שקולות [עריכה]
יהי G גרף לא מכוון פשוט (ללא קשת מקודקוד לעצמו). ההגדרות הבאות שקולות:
- G הוא עץ.
- G הוא גרף קשיר ואין בו מעגל פשוט.
- ב-G אין מעגל פשוט, אך אם נוסיף לו קשת אחת, יווצר בו מעגל פשוט.
- G הוא גרף קשיר, אך אם נגרע ממנו קשת אחת, יפסיק להיות קשיר.
- בין כל שני צמתים ב-G מקשר מסלול פשוט יחיד.
אם ל-G יש מספר סופי (שנסמנו n) של צמתים, אז התנאים דלעיל שקולים גם לתנאים:
- G הוא גרף קשיר ויש בו n-1 קשתות.
- ב-G אין מעגל פשוט, ויש בו n-1 קשתות.
הכללות ומקרים פרטיים [עריכה]
כל גרף חסר מעגלים נקרא יער. ניתן לראות יער בתור איחוד זר של עצים (ומכאן שמו).
גרף מכוון ייקרא עץ אם גרף התשתית שלו הוא עץ וניתן לסמן אחד מהצמתים של העץ כשורש העץ, כך שיש מסלול מהשורש לכל צומת בעץ. בהינתן עץ לא מכוון, ניתן להפוך אותו לעץ מכוון על ידי בחירה שרירותית של אחד הצמתים בתור שורש, ובחירת הכיוון שעל הקשתות בצורה שתאפשר מעבר מהשורש לכל צומת בעץ.
עץ בינארי [עריכה]
 |
ערך מורחב – עץ בינארי |
עץ ייקרא עץ בינארי אם הוא מקיים את כל התכונות הבאות:
- העץ מכוון.
- דרגת היציאה של כל קודקוד בעץ היא לכל היותר 2 (במילים אחרות: לכל צומת יש לא יותר משני צאצאים - צמתים שיש קשת ממנו אליהם).
- קיים קודקוד אחד ויחיד שדרגת הכניסה שלו היא 0 (קודקוד זה ייקרא שורש העץ).
עצים פורשים [עריכה]
עץ המוכל בגרף G וכולל את כל הצמתים שלו נקרא עץ פורש של G.
