עץ (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←מושגים |
|||
שורה 49:
* [[דרגת יציאה|דרגת היציאה]] של כל קודקוד בעץ היא לכל היותר 2 (במילים אחרות: לכל צומת יש לא יותר משני צאצאים - צמתים שיש קשת ממנו אליהם).
* קיים קודקוד אחד ויחיד ש[[דרגת כניסה|דרגת הכניסה]] שלו היא 0 (קודקוד זה ייקרא '''שורש העץ''').
== עצים פילוגנטיים ==
'''עץ פילוגנטי''' (מופשט) הוא עץ בינארי בעל שורש, שהקשתות שלו ממושקלות. עצים כאלה משמשים למידול תהליכים אבולוציוניים, כגון ההתפצלות ה[[פילוגנטיקה|פילוגנטית]] של בעלי החיים, מיקרו-אבולוציה של נגיפי שפעת, כתבי יד המותעקים זה מזה עם שגיאות, וכדומה.
הבעיה המרכזית בנושא היא שחזור העץ הסביר ביותר ממידע על העלים שלו. בהנתן [[מטריקה]] על הקודקודים, '''תנאי ארבעת הקודקודים''' ([http://homepages.inf.ed.ac.uk/opb/homepagefiles/phylogeny-scans/metricproperties.pdf Buneman, 1974]) נותן תנאי הכרחי ומספיק לכך שהמטריקה ניתנת למימוש על ידי עץ פילוגנטי: נדרש כי לכל ארבעה קודקודים i,j,k,l, מבין שלושת הסכומים <math>d(i,j)+d(k,l)</math>, <math>d(i,k)+d(j,l)</math> ו-<math>d(i,l)+d(j,k)</math>, המקסימום מתקבל לפחות פעמיים.
==ראו גם==
| |||