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

مثال ساده‌ای از یک گراف جهت‌دار غیرمدور
گراف جهت‌دار غیرمدور یا DAG، در دانش رایانه و ریاضیات، یک گراف جهت‌دار است که هیچ گراف دوری‌ای ندارد؛ یعنی هیچ مسیر جهت‌داری که راس ابتدا و انتهای آن یکی باشد، وجود ندارد. به خاطر ویژگی‌های این نوع گراف می‌توان از آن در مدل کردن سیستم‌های علت و معلولی استفاده کرد.
تعریف دور و نداشتن آن
یک دور مسیر ساده‌ای است که راس شروع و پایانی آن یکی باشد. گراف ساده جهت‌داری را که دارای دور نیست، غیر مدور می‌نامند.
نمونه‌ای از یک دور جهت‌دار. یک گراف جهت دار غیرمدور هیچ دور جهت‌داری ندارد
یک دور در گراف ساده بدون جهت حداقل شامل سه یال متفاوت است که به جز راس ابتدایی و انتهایی، هیچ راسی در آن تکراری نیست.
ترتیب جزئی
خواص گراف جهت‌دار غیرمدور اجازه می‌دهد که ترتیب جزئی کوچکتر مساوی بین راس‌های گراف به صورت روبرو تعریف شود: برای هر دو راس دلخواه گراف می‌گوییم اگر و فقط اگر یک مسیر جهت‌دار از به وجود داشته باشد.
ممکن است گراف‌های جهت‌دار غیرمدور مختلف منجر به ترتیب جزئی یکسانی بشوند: برای مثال دو گراف
a → b → c
و
(a → b → c, a → c)
ترتیب جزئی یکسانی در مورد ارتباط بین راس‌ها را اعمال می‌کنند اما گراف جهت‌دار غیرمدور دوم یک یال اضافه‌تر دارد. از بین تمام گراف‌های جهت‌دار غیرمدور این چنینی، آن که کمترین تعداد یال را دارد ساده‌سازی ترایا و آن که بیشترین تعداد یال را دارد بستار ترایا نامیده می‌شود.
ویژگی‌ها
هر گراف جهت‌دار غیرمدوری یک مرتب‌سازی موضعی (توپولوژیک) دارد. به این صورت که هر راس قبل از تمام راس‌هایی می‌آید که به آن‌ها یالی دارد. در حالت کلی این مرتب‌سازی یکتا نیست. مرتب‌سازی موضعی هر دو گرافی که یک ترتیب جزئی دارند، یکسان است. DAGها را می‌توان مفهوم گسترده شده‌ای از درخت‌ها در نظر گرفت. درخت‌هایی که در آنها، دسته‌ای از زیردرخت‌ها وجود دارد که می‌توانند در قسمت‌های مختلف درخت سهیم شوند؛ یعنی از هر راس به بیش از یک زیردرخت می‌توان دسترسی داشت. در درخت‌هایی که تعداد زیادی زیردرخت یکسان دارند، این ویژگی می‌تواند فضای مورد یاز برای ذخیره کردن این ساختار را تا اندازه زیادی کاهش دهد. به بیانی ساده‌تر، DAG می‌تواند با استفاده از الگوریتم زیر، مانند جنگلی از درختان ریشه‌دار عمل کند:
تا وقتی که راس v با درجه n>1 وجود دارد؛
n کپی از راس v با یال‌های خروجی یکسان و بدون یال ورودی بساز.
یکی از یال‌های ورودی v را به هر راس وصل کن.
راس v را پاک کن.
اگر ما گرافی را بدون تغییر یا مقایسه برابری راس‌ها پیمایش کنیم، این جنگل با DAG اولیه یکسان خواهد بود.
بعضی از الگوریتم‌ها روی DAGها نسبت به گراف‌های معمولی پیاده‌سازی ساده‌تری دارند. برای مثال الگوریتم جستجویی مانند جستجوی اول عمق (DFS) بدون عمیق‌کننده تکراری (Iterative Deepening)، به صورت معمول باید راس‌هایی را که بررسیده نشانه‌گذاری کند تا از بررسی دوباره‌شان بپرهیزد، و اگر این روند را به درستی انجام ندهد، بررسی راس‌ها هیچ وقت تمام نمی‌شود. چون همیشه در یک دور بی‌پایان از یال‌ها می‌افتد. اما چنین دوری در DAGها وجود ندارد. روش نشانه‌گذاری راس‌ها در DAG، بدترین زمان اجرا را از نمایی (که به خاطر وجود مسیرهای چندگانه است) به خطی می‌کاهد.
یک درخت چندگانه یکی از انواع ویژه و کارای DAG است که بسیاری از ویژگی‌های درخت را دارد. بازدهی و کارایی این نوع درخت زیاد است؛ برای مثال در الگوریتم انتشار باور.
اریک وستاین حدس زد و اثبات کرد که تعداد DAGهای برچسب‌دار با n راس، برابر است با ماتریس‌های × با درایه‌های ۰ و ۱ (مثل ماتریس همسایگی) که تنها یک مقدار ویژه حقیقی مثبت دارند.
اصطلاحات علمی
ریشه راسی است که هیچ یال ورودی ندارد، و برگ راسی است که هیچ یال خروجی ندارد. یک DAG متناهی حداقل باید یک ریشه و یک برگ داشته باشد.
عمق هر راس در گراف جهت‌دار غیرمدور متناهی برابر است با طول طولانی‌ترین مسیر از ریشه تا آن راس. ارتفاع هر راس نیز برابر است با طول طولانی‌ترین مسیر بین آن راس و برگ.
طول یک DAG متناهی برابر است با طول (یا تعداد یال‌های) طولانی‌ترین مسیر جهت‌دار، که این مقدار مساوی با بیشینه ارتفاع تمام ریشه‌ها و بیشینه عمق تمام برگ‌ها می‌باشد.
کاربردها
استفاده از گراف جهت‌دار غیرمدور، برخی الگوریتم‌ها را ساده‌تر و چابک‌تر می‌کند. DAG در الگوریتم‌های مسیریابی، شبکه‌های پردازش داده، شبکه‌های بیزی، تبارنامه‌ها ، روش‌های فشرده‌سازی داده و بسیاری موارد دیگر کاربرد دارد.