גרף מכוון חסר מעגלים
מראה
![]() |
ערך מחפש מקורות
| |
ערך מחפש מקורות | |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Tred-G.svg/220px-Tred-G.svg.png)
גרף מכוון חסר מעגלים (גמ"ל[דרוש מקור]; באנגלית: DAG, Directed acyclic graph) הוא מסלול פשוט או גרף שמכיל בתוכו מסלולים פשוטים בלבד, שלכולם קודקוד התחלה וסוף.
לגרף זה כמה תכונות:
- גרף הוא מכוון אם ורק אם הוא מניב צלעות אחורה בתוצאת אלגוריתם חיפוש לעומק שמופעל עליו.
- הגרף מקיים יחס טרנזטיביות: אם היחס של v קטן משל u, והיחס של u קטן משל w, אז היחס של v בהכרח קטן משל w.
- הרצת מיון טופולוגי אליו תפלוט רשימה ליניארית של כל הקודקודים ב-V, הממוינת לפי יחס סדר מלא.
- אם הצלע (u,v) קיימת, הצלע (v,u) אינה קיימת.
- הרצת שיחלוף על הגרף תשאיר אותו מכוון וללא מעגלים, כאשר כל הכיוונים השתנו. קודקודי ההתחלה הם קודקודי הסוף, וקודקודי הסוף הם קודקודי ההתחלה.
קבוצת רכיבים קשירים היטב של כל גרף G הוא DAG.
קישורים חיצוניים[עריכת קוד מקור | עריכה]
- גרף מכוון חסר מעגלים, באתר MathWorld (באנגלית)