گراف جهت دار غیرمدور

گراف جهت دار غیرمدور (به انگلیسی: Directed Acyclic Graph) یا DAG، در دانش رایانه و ریاضیات، یک گراف جهت دار است که هیچ گرافِ دوری ای ندارد؛ یعنی هیچ مسیر جهت داری که رأس ابتدا و انتهای آن یکی باشد، وجود ندارد. به خاطر ویژگی های این نوع گراف می توان از آن در مدل کردن سیستم های علت و معلولی استفاده کرد.
تا وقتی که رأس v با درجهٔ n>1 وجود دارد؛
n کپی از رأس v با یال های خروجی یکسان و بدون یال ورودی بساز.
یکی از یال های ورودی v را به هر رأس وصل کن.
رأس v را پاک کن.
یک دور (به انگلیسی: Cycle) مسیر ساده ای است که راس شروع و پایانی آن یکی باشد. گراف ساده جهت داری را که دارای دور نیست، غیر مدور (به انگلیسی: Acyclic) می نامند.
یک دور در گراف ساده بدون جهت حداقل شامل سه یال متفاوت است که به جز راس ابتدایی و انتهایی، هیچ راسی در آن تکراری نیست.
خواص گراف جهت دار غیرمدور اجازه می دهد که ترتیب جزئی کوچکتر مساوی بین رأس های گراف به صورت روبرو تعریف شود: برای هر دو رأس دلخواه u , v {\displaystyle u,v}   گراف می گوییم u <= v {\displaystyle u<=v}   اگر و فقط اگر یک مسیر جهت دار از u {\displaystyle u}   به v {\displaystyle v}   وجود داشته باشد.