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

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

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

לעץ יש ענפים, הקשתות, ועלים, הקודקודים הקיצוניים ללא שכנים נוספים. בעץ מושרש (עם שורש) מסמנים קודקוד אחד כשורש. אז לכל קודקוד יש הורה (הקודקוד שמולו בדרך מהשורש) ו/או בנים.

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

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

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

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

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

לעץ יש קווים ונקודות. אין בו קווים שמסביבים לעצמם.

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

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

עץ יכול להיות מושרש או לא. אם בכל העלים המרחק מהשורש זהה, קוראים לו אולטרמטרי. מרחק הוא כמה קווים עוברים בין שתי נקודות.

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