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

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

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

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

הגדרות שקולות[עריכת קוד מקור | עריכה]

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

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

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

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

מושגים[עריכת קוד מקור | עריכה]

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

עץ מושרש - עץ שקיים בו שורש.

עומק של צומת - מספר הקשתות במסלול בין השורש לצומת.

אב ובן - צומת הוא האב של ו- הוא הבן של אם ורק אם ישנה קשת ביניהם ועומקו של קטן באחד מעומקו של .

עלה - צומת שאין לו בנים. הגדרה מקבילה: צומת שהדרגה שלו היא 1.

קודקוד פנימי - צומת שיש לו בנים.

אב קדמון וצאצא - צומת הוא האב הקדמון של ו- הוא הצאצא של אם ורק אם הוא הבן של או ש- הוא בן של צאצא של .

גובה של צומת - מספר הקשתות במסלול הארוך ביותר בין הצומת לאחד הצאצאים שלו.

גובה העץ - הגובה של השורש.

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

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

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

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

עץ בינארי[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – עץ בינארי

עץ ייקרא עץ בינארי אם הוא מקיים את כל התכונות הבאות:

  • העץ מכוון.
  • דרגת היציאה של כל קודקוד בעץ היא לכל היותר 2 (במילים אחרות: לכל צומת יש לא יותר משני צאצאים - צמתים שיש קשת ממנו אליהם).
  • קיים קודקוד אחד ויחיד שדרגת הכניסה שלו היא 0 (קודקוד זה ייקרא שורש העץ).

עצים פילוגנטיים[עריכת קוד מקור | עריכה]

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

הבעיה המרכזית בנושא היא שחזור העץ ממידע על העלים שלו. ארכי הקשתות של העץ מגדירים מטריקה על קבוצת העלים שלו. בהנתן מטריקה על העלים, תנאי ארבעת הקודקודים (Buneman, 1974) הוא תנאי הכרחי ומספיק לכך שהמטריקה ניתנת למימוש על ידי עץ פילוגנטי: נדרש כי לכל ארבעה עלים i,j,k,l, מבין שלושת הסכומים , ו-, המקסימום מתקבל לפחות פעמיים.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא עץ בוויקישיתוף

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ הבחירה שרירותית. אפשר לבחור כל אחד מהקודקודים כשורש.