עץ (תורת הגרפים)
בתורת הגרפים, עץ הוא גרף קשיר ללא מעגלים. מלבד התפקיד של עצים בתורת הגרפים, כגרפים הקשירים המינימליים, ובטופולוגיה כמודל למרחב היפרבולי, עצים הנושאים מידע נוסף מהווים משפחה חשובה של מבני נתונים.
לעץ יש "ענפים" – קשתות הגרף, ו"עלים" – הצמתים הקיצוניים. עץ שבו בוחרים ומסמנים את אחד הקודקודים נקרא עץ עם שורשתבנית:הערה, ואז אפשר לראות אותו כצומח ועולה מן השורש הזה, כמו אילן יוחסין – לכל קודקוד פרט לשורש יש "הורה" (הקודקוד שבא מיד לפניו בדרך מן השורש) ו"בנים" (הקודקודים שבאים מיד אחריו כשמתרחקים מן השורש). בתמונה מוצג עץ שהשורש שלו הוא צומת 6, והעלים שלו הם הצמתים 1, 2 ו־3.
הגדרות שקולות
יהי גרף לא מכוון פשוט (ללא קשת מקודקוד לעצמו). כל התנאים הבאים יכולים לשמש כהגדרות לעץ:
- הוא גרף קשיר ואין בו מעגל פשוט.
- ב- אין מעגל פשוט, אך אם נוסיף לו קשת אחת, ייווצר בו מעגל פשוט.
- הוא גרף קשיר, אך אם נגרע ממנו קשת אחת, יפסיק להיות קשיר.
- בין כל שני צמתים ב- מקשר מסלול פשוט יחיד.
אם ל- יש מספר סופי (שנסמנו ) של צמתים, אז התנאים דלעיל שקולים גם לתנאים:
- הוא גרף קשיר ויש בו קשתות.
- ב- אין מעגל פשוט, ויש בו קשתות.
מושגים
- תבנית:עוגן – בגרפים מכוונים, שורש הוא צומת שקיים מסלול ממנו לכל צומת אחר בגרף.
- תבנית:עוגן – או עץ מכוון – גרף מכוון שגרף התשתית שלו הוא עץ, ושאת אחד מצמתיו ניתן לסמן כשורש העץ, כך שיש מסלול מהשורש לכל צומת בעץ. בהינתן עץ לא מכוון, ניתן להפוך אותו לעץ מכוון על ידי בחירה שרירותית של אחד הצמתים בתור שורש, ובחירת הכיוון שעל הקשתות בצורה שתאפשר מעבר מהשורש לכל צומת בעץ.
- תבנית:עוגן – עץ שקיים בו שורש.
- תבנית:עוגן – מספר הקשתות במסלול בין השורש לצומת.
- תבנית:עוגן ותבנית:עוגן – צומת הוא האב של ו- הוא הבן של אם ורק אם ישנה קשת ביניהם ועומקו של קטן באחד מעומקו של .
- תבנית:עוגן – בגרף מכוון, צומת שאין לו בנים. בגרף לא-מכוון, צומת שהדרגה שלו קטנה או שווה 1.
- תבנית:עוגן – צומת שיש לו בנים.
- תבנית:עוגן ותבנית:עוגן – צומת הוא האב הקדמון של ו- הוא הצאצא של אם ורק אם הוא הבן של או ש- הוא בן של צאצא של .
- תבנית:עוגן – מספר הקשתות במסלול הארוך ביותר בין הצומת לאחד הצאצאים שלו.
- תבנית:עוגן – מספר הקשתות בין השורש לבין העלה שנמצא במסלול הארוך ביותר.
- תבנית:עוגן – בהינתן עץ , תת-עץ שלו הוא עץ שצמתיו הם צומת וצאצאי מהעץ כאשר הוא שורשו. הקשתות של תת-העץ הם הקשתות מהעץ שעוברות בין הצאצאים והקשתות בין הצאצאים ל.
- יער – גרף חסר מעגלים. ניתן לראות יער בתור איחוד זר של עצים (ומכאן שמו).
- עץ פורש – עץ המוכל בגרף וכולל את כל הצמתים שלו.
עץ בינארי
תבנית:ערך מורחב עץ ייקרא עץ בינארי אם הוא מקיים את כל התכונות הבאות:
- דרגת היציאה של כל קודקוד בעץ היא לכל היותר 2 (במילים אחרות: לכל צומת יש לא יותר משני צאצאים – צמתים שיש קשת ממנו אליהם).
- קיים קודקוד אחד ויחיד שדרגת הכניסה שלו היא 0 (קודקוד זה ייקרא שורש העץ).
עצים פילוגנטיים
עץ פילוגנטי (מופשט) הוא עץ בינארי עם קשתות במשקל אי שלילי, המייצגות יחידות שעוברות שינויים יחד. עצים כאלה משמשים למידול תהליכים אבולוציוניים, כגון ההתפצלות הפילוגנטית של בעלי החיים, מיקרו-אבולוציה של נגיפי שפעת, כתבי יד המועתקים זה מזה עם שגיאות, וכדומה. עצים יכולים להיות מושרשים, במקרה שבו מניחים המצאות של ״אב קדמון״ משותף, או לא מושרשים. עץ מושרש שבו המרחק מהשורש לכלל העלים זהה נקרא עץ אולטרמטרי.
הבעיה המרכזית בתחום הפילוגנטיקה היא שחזור העץ ממידע על העלים שלו. קבוצת אלגוריתמים מרכזית מחפשת למצוא עץ בהסתמך על מרחק בין זוגות של עלים, וקבוצה נוספת מחפשת להביא למינימום את החלפת התכונות לאורך הענפים (היוריסטיקה פרסימונית).
ארכי הקשתות של העץ מגדירים מטריקה על קבוצת העלים שלו. בהינתן מטריקה על קבוצת קודקודים, תנאי האדטיביות (תנאי ארבעת הקודקודים Buneman, 1974) הוא תנאי הכרחי ומספיק לכך שהמטריקה ניתנת למימוש על ידי עץ פילוגנטי שאלו הם עליו: נדרש כי לכל ארבעה קודקודים i,j,k,l, מבין שלושת הסכומים , ו-, המקסימום מתקבל לפחות פעמיים.
אלגוריתמים לשחזור עצים פילוגנטיים יכולים לשמש גם לקלאסטרינג, כאשר האשכולות נבחרים מתוך הפיצולים הראשיים בעץ.