גרף מכוון חסר מעגלים
קפיצה לניווט
קפיצה לחיפוש
 |
ערך מחפש מקורות
| |
| ערך מחפש מקורות |
גרף מכוון חסר מעגלים (גמ"ל; באנגלית: DAG, Directed acyclic graph) הוא מסלול פשוט או גרף שמכיל בתוכו מסלולים פשוטים בלבד, שלכולם קודקוד התחלה וסוף.
לגרף זה כמה תכונות:
- גרף הוא מכוון אם ורק אם הוא מניב צלעות אחורה בתוצאת אלגוריתם חיפוש לעומק שמופעל עליו.
- הגרף מקיים יחס טרנזטיביות: אם היחס של v קטן משל u, והיחס של u קטן משל w, אז היחס של v בהכרח קטן משל w.
- הרצת מיון טופולוגי אליו תפלוט רשימה ליניארית של כל הקודקודים ב-V, הממוינת לפי יחס סדר מלא.
- אם הצלע (u,v) קיימת, הצלע (v,u) אינה קיימת.
- הרצת שיחלוף על הגרף תשאיר אותו מכוון וללא מעגלים, כאשר כל הכיוונים השתנו. קודקודי ההתחלה הם קודקודי הסוף, וקודקודי הסוף הינם קודקודי ההתחלה.
קבוצת רכיבים קשירים חזק של כל גרף G הוא DAG.
קישורים חיצוניים
- גרף מכוון חסר מעגלים, באתר MathWorld (באנגלית)
