עץ (תורת הגרפים) – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Yoavd (שיחה | תרומות)
צומת זה זכר
שורה 18:
== מושגים ==
 
{{עוגן|שורש|'''שורש'''}} - צומת אחתאחד מיוחסת בעץ (צומת אחת בעץ שהוחלט להתייחס אליה בתור "שורש").
 
{{עוגן|עץ מושרש|'''עץ מושרש'''}} - עץ שקיים בו שורש.
שורה 24:
{{עוגן|עומק|'''עומק''' של צומת}} - מספר הקשתות במסלול בין השורש לצומת.
 
{{עוגן|אב|'''אב'''}} '''ו'''{{עוגן|בן|'''בן'''}} - צומת <math>v</math> הוא האב של <math>w</math> וw הוא הבן של <math>v</math> [[אם ורק אם]], ישנה קשת ביניהם ומספר הקשתות [[מסלול (תורת הגרפים)|במסלול]] בין <math>v</math> לשורש הוא קטן יותר (באחד), מהעומק של <math>w</math>.
 
{{עוגן|עלה|'''עלה'''}} - צומת שאין להלו בנים. הגדרה מקבילה: צומת שה[[דרגה (תורת הגרפים)|דרגה]] שלו היא 1.
 
{{עוגן|קודקוד פנימי|'''קודקוד פנימי'''}} - צומת שיש לו בנים.
 
{{עוגן|אב קדמון|'''אב קדמון'''}} '''ו'''{{עוגן|צאצא|'''צאצא'''}} - צומת <math>v</math> הוא האב הקדמון של <math>w</math> ו-<math>w</math> הוא הצאצא של <math>v</math> אם ורק אם, <math>w</math> הוא הבן של <math>v</math> או ש-<math>w</math> הוא בן של צאצא קדמון של <math>v</math>.
 
{{עוגן|גובה|'''גובה''' של צומת}} - המספר הגבוה ביותר של קשתות במסלול מבין המסלולים שעוברים בין הצומת לכל אחד מהצאצאים שלהשלו.
 
{{עוגן|גובה עץ|'''גובה''' העץ}} - הגובה של השורש.