ⓘ گراف جهت‌دار غیرمدور یا DAG، در دانش رایانه و ریاضیات، یک گراف جهت‌دار است که هیچ گرافِ دوریای ندارد؛ یعنی هیچ مسیر جهت‌داری که رأس ابتدا و انتهای آن یکی باشد، ..

                                     

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

گراف جهت‌دار غیرمدور یا DAG، در دانش رایانه و ریاضیات، یک گراف جهت‌دار است که هیچ گرافِ دوریای ندارد؛ یعنی هیچ مسیر جهت‌داری که رأس ابتدا و انتهای آن یکی باشد، وجود ندارد. به خاطر ویژگی‌های این نوع گراف می‌توان از آن در مدل کردن سیستم‌های علت و معلولی استفاده کرد.

                                     

1. تعریف دور و نداشتن آن

یک دور به انگلیسی: Cycle مسیر ساده‌ای است که راس شروع و پایانی آن یکی باشد. گراف ساده جهت‌داری را که دارای دور نیست، غیر مدور به انگلیسی: Acyclic می‌نامند.

یک دور در گراف ساده بدون جهت حداقل شامل سه یال متفاوت است که به جز راس ابتدایی و انتهایی، هیچ راسی در آن تکراری نیست.

                                     

2. ترتیب جزئی

خواص گراف جهت‌دار غیرمدور اجازه می‌دهد که ترتیب جزئی کوچکتر مساوی بین رأس‌های گراف به صورت روبرو تعریف شود: برای هر دو رأس دلخواه u, v {\displaystyle u,v} گراف می‌گوییم u

                                     
  • گراف جهت دار غیر مدور مقصدگرا که به اختصار DODAG نامید می شود یک گراف جهت دار غیرمدور است که فقط یک ریشه دارد. به عبارت دیگر تمامی مسیرها فقط به یک گره
  • مبنای گرووی زبان برنامه نویسی را به جای XML معرفی می کند. گریدل از گراف جهت دار غیرمدور برای تعیین وظیفه قابل اجرا بهره می گیرد. مشارکت کنندگان ویکی پدیا
  • وقتی جهت دار در نظر گرفته شود یک گراف جهت دار غیرمدور است و در عین حال یک گراف کامل و یک گراف بی یال است. اگر چه تعریف ها برای ویژگی های این گراف متفاوت
  • ساختاری بشمار می آید. نمودار فعالیت Control flow diagram جریان داده گراف جهت دار غیرمدور مدل تابع خط لوله تکنیک طراحی و تحلیل ساختاری نقشه برداری جریان ارزش
  • تبدیل قبلی استفاده نمی کند و پیچیدگی زمانی بهتری هم دارد. اگر G گراف جهت دار غیرمدور باشد مسئله یافتن بلندترین مسیر را می توان در زمان خطی با استفاده
  • شبکه های فیلوژنتیکی ریشه دار یک گراف جهت دار غیرمدور و ریشه داری است که معمولا برگ های آن را با آرایه ها برچسب گذاری می کنند. گراف میانه شاخه بندی سامانه شناسی