גרף מכוון חסר מעגלים

גרף מכוון חסר מעגלים (גמ"ל; באנגלית: DAG, Directed acyclic graph) הוא מסלול פשוט או גרף שמכיל בתוכו מסלולים פשוטים בלבד, שלכולם קודקוד התחלה וסוף.

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

מטבע מבוזר כספא מבוסס על שיטה זו.

קישורים חיצוניים



קטגוריה:תורת הגרפים