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

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

לגרף זה כמה תכונות:

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

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

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

מדיה וקבצים בנושא גרף מכוון חסר מעגלים בוויקישיתוף

	ערך מחפש מקורות
	רובו של ערך זה אינו כולל מקורות או הערות שוליים, וככל הנראה, הקיימים אינם מספקים. אנא עזרו לשפר את אמינות הערך באמצעות הבאת מקורות לדברים ושילובם בגוף הערך בצורת קישורים חיצוניים והערות שוליים. אם אתם סבורים כי ניתן להסיר את התבנית, ניתן לציין זאת בדף השיחה.