עץ (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←מושגים: הגהה |
←מושגים: עריכה |
||
שורה 17:
== מושגים ==
* {{עוגן|שורש|'''שורש'''}} - בגרפים מכוונים, שורש הוא צומת שקיים מסלול ממנו לכל צומת אחר בגרף.
* '''עץ''' - [[גרף מכוון]]
* {{עוגן|עץ מושרש|'''עץ מושרש'''}} - עץ שקיים בו שורש.
* {{עוגן|עומק|'''עומק''' של צומת}} - מספר הקשתות במסלול בין השורש לצומת.
* {{עוגן|אב|'''אב'''}} '''ו'''{{עוגן|בן|'''בן'''}} - צומת <math>v</math> הוא האב של <math>w</math> ו-<math>w</math> הוא הבן של <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>.▼
* {{עוגן|גובה|'''גובה''' של צומת}} - מספר הקשתות במסלול הארוך ביותר בין הצומת לאחד הצאצאים שלו.▼
▲{{עוגן|עלה|'''עלה'''}} - צומת שאין לו בנים. הגדרה מקבילה: צומת שה[[דרגה (תורת הגרפים)|דרגה]] שלו קטנה או שווה 1.
* {{עוגן|גובה עץ|'''גובה''' העץ}} - מספר הקשתות בין השורש לבין העלה שנמצא במסלול הארוך ביותר.▼
* {{עוגן|תת עץ|'''תת עץ'''}} - בהינתן עץ <math>T</math>, תת-עץ שלו הוא עץ שצמתיו הם צומת <math>v</math> וצאצאי <math>v</math> מהעץ <math>T</math> כאשר <math>v</math> הוא שורשו. הקשתות של תת-העץ הם הקשתות מהעץ <math>T</math> שעוברות בין הצאצאים והקשתות בין הצאצאים ל<math>v</math>.▼
▲{{עוגן|קודקוד פנימי|'''קודקוד פנימי'''}} - צומת שיש לו בנים.
* '''יער''' - גרף חסר מעגלים. ניתן לראות יער בתור [[איחוד זר]] של עצים (ומכאן שמו).▼
* '''[[עץ פורש]]''' עץ המוכל בגרף <math>G</math> וכולל את כל הצמתים שלו
▲{{עוגן|אב קדמון|'''אב קדמון'''}} '''ו'''{{עוגן|צאצא|'''צאצא'''}} - צומת <math>v</math> הוא האב הקדמון של <math>w</math> ו-<math>w</math> הוא הצאצא של <math>v</math> אם ורק אם <math>w</math> הוא הבן של <math>v</math> או ש-<math>w</math> הוא בן של צאצא של <math>v</math>.
▲{{עוגן|גובה|'''גובה''' של צומת}} - מספר הקשתות במסלול הארוך ביותר בין הצומת לאחד הצאצאים שלו.
▲{{עוגן|גובה עץ|'''גובה''' העץ}} - מספר הקשתות בין השורש לבין העלה שנמצא במסלול הארוך ביותר.
▲{{עוגן|תת עץ|'''תת עץ'''}} - בהינתן עץ <math>T</math>, תת-עץ שלו הוא עץ שצמתיו הם צומת <math>v</math> וצאצאי <math>v</math> מהעץ <math>T</math> כאשר <math>v</math> הוא שורשו. הקשתות של תת-העץ הם הקשתות מהעץ <math>T</math> שעוברות בין הצאצאים והקשתות בין הצאצאים ל<math>v</math>.
▲'''יער''' - גרף חסר מעגלים. ניתן לראות יער בתור [[איחוד זר]] של עצים (ומכאן שמו).
▲[[גרף מכוון]] ייקרא עץ אם [[גרף תשתית|גרף התשתית]] שלו הוא עץ וניתן לסמן אחד מהצמתים של העץ כ'''שורש העץ''', כך שיש מסלול מהשורש לכל [[צומת (תורת הגרפים)|צומת]] בעץ. בהינתן עץ לא מכוון, ניתן להפוך אותו לעץ מכוון על ידי בחירה שרירותית של אחד הצמתים בתור שורש, ובחירת הכיוון שעל הקשתות בצורה שתאפשר מעבר מהשורש לכל צומת בעץ.
▲עץ המוכל בגרף <math>G</math> וכולל את כל הצמתים שלו נקרא '''[[עץ פורש]]''' של <math>G</math>.
=== עץ בינארי ===
| |||