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