|
[[پرونده:Directed acyclic graph.png|چپ|150px|بندانگشتی|مثال ساده‌ای از يک گراف جهت‌دار غیرمدور]]
درعلوم کامپیوتر و ریاضیات، '''گراف جهت‌دار غیرمدور''' ({{انگلیسی|Directed acyclicAcyclic graphGraph}} یا بهDAG، صورتدر خلاصه[[دانش DAG)رایانه]] و [[ریاضیات]]، یک [[گراف جهت‌دار]] است که هیچ [[دورگراف جهت‌داردوری|گرافِ دوری]]ی<nowiki/>ای نداردندارد؛ (یعنی هیچ مسیر جهت‌داری که رأس ابتدا و انتهای آن یکی باشد، وجود ندارد). به خاطر ویژگی‌های این نوع گراف می‌توان از آن در مدل کردن سیستم‌های علت و معلولی استفاده کرد.
== تعریف دور و نداشتن آن ==
یک دور {{انگلیسی|cycleCycle}} مسیر ساده‌ای است که راس شروع و پایانی آن یکی باشد. گراف ساده جهت‌داری را که دارای دور نیست رانیست، غیر مدور {{انگلیسی|acyclicAcyclic}} می‌نامند.
[[پرونده:DC8.png|100px|بندانگشتی|چپ|نمونه‌ای از يک دور جهت‌دار. يک گراف جهت دار غیرمدور هيچ دور جهت‌داری ندارد]]
یک دور در گراف ساده بدون جهت حداقل شامل سه یال متفاوت است که به جز راس ابتدایی و انتهایی، هیچ راسی در آن تکراری نیست بجز راس ابتدایی و انتهایی.
== ترتیب جزئی ==
(''a'' → ''b'' → ''c,'' ''a'' → ''c'')
</center>
ترتیب جزئی یکسانی در مورد ارتباط بین رئوسرأس‌ها را اعمال می‌کنند اما گراف جهت‌دار غیرمدور دوم یک یال اضافه تراضافه‌تر دارد. از بین تمام گراف‌های جهت‌دار غیرمدورغیرمدورِ این چنینیچنینی، آنکهآن که کمترین تعداد یال را دارد [[Transitive Reduction|ساده‌سازی ترایا]] {{انگلیسی|transitiveTransitive reductionReduction}} نامیده شده و آنکهآن که بیشترین تعداد یال را دارد [[بستار تعدی|بستار ترایا]] {{انگلیسی|transitiveTransitive closureClosure}} نامیده شده‌استمی‌شود.
== ویژگی‌ها ==
هر گراف جهت دارجهت‌دار غیرمدوری یک [[مرتب‌سازی توپولوژیکی|مرتب‌سازی مکانموضعی]] شناسی(Topologicalتوپولوژیک) دارد،دارد. به این صورت که هر رأس قبل از تمام رأس‌هایی می‌آید که به آنها یالی دارد. در حالت کلی این مرتب‌سازی یکتا و منحصربه‌فرد نیست. مرتب‌سازی مکان شناسیِموضعیِ هر دو گرافی که یک ترتیب جزئی دارند، یکسان است. DAGها را می‌توان مفهوم گسترده شده‌ای از [[درخت (نظریه گراف)|درخت‌ها]] در نظر گرفت. درخت‌هایی که در آنها، دسته‌ای از زیردرخت‌ها وجود دارد که می‌توانند در قسمت‌های مختلف درخت سهیم شوند؛ یعنی از هر رأس به بیش از یک زیردرخت می‌توان دسترسی داشت. در درخت‌هایی که تعداد زیادی زیردرختِ یکسان دارند، این ویژگیمی‌تواند فضای مورد یاز برای ذخیره کردن ِاین یسختار را تا حاندازه‌ٔکزیادی اهش دهد. به بیانی ساده‌تر، DAG می‌تواند با استفاده از الگوریتم زیر، مانند جنگلی از [[درخت‌های ریشه‌دار|درختان ریشه‌دار]] عمل کند:
DAGها را می‌توان به عنوان تعمیم یافتهٔ مفهوم درخت‌ها در نظر گرفت. درخت‌هایی که در آنها، دستهٔ از زیردرخت‌ها که می‌توانند در قسمت‌های مختلف درخت سهیم شوند (یعنی از هر رأس به بیش از یک دیردرخت می‌توان دسترسی داشت). در یک درخت با تعداد زیادی زیردرخت یکسان، این می‌تواند فضای مورد نیاز برای ذخیره کردن این یاختار را تا حد خوبی کاهش دهد. در بیان ساده‌تر،DAG می‌تواند با استفاده از الگوریتم زیر مانند جنگلی از درختان ریشه دار عمل کند:
* تا وقتی که رأس v با درجهٔ n>1 وجود دارد؛
** nکپیn کپی از رأس v با یال‌های خروجی یکسان و بدون یال ورودی بساز.
** یکی از یال‌های ورودی v را به هر رأس وصل کن.
** رأس v را پاک کن.
اگر ما گرافی را بدون تغییر یا مقایسهٔ برابری رأس‌ها پیمایش کنیم، این جنگل با DAG اولیه یکسان خواهد بود.
بعضی از الگوریتم‌ها روی DAGها نسبت به گراف‌های معمولی پیاده‌سازی ساده‌تری دارند. برای مثال الگوریتم جستجویی مثلمانند جستجو[[الگوریتم ازجستجوی عمق (depth-firstاول|جستجوی searchاول عمق]] (DFS) بدونبدونِ [[جستجوی عمق اول تکرارکنندهٔعمیق‌کننده گودتکراری|عمیق‌کنندهٔ کردنتکراری]] (itrativeIterative deepeningDeepening)، به صورت معمول باید رئوسیرأس‌هایی را که بررسیبررسیده کرده علامت‌گذارینشانه‌گذاری کند وتا دوبارهاز آن‌هابررسی رادوباره‌شان چک نکند.بپرهیزد، و اگر این روند را به درستی انجام ندهد، اینبررسی چک کردن‌هارأس‌ها هیچ وقت تمام نمی‌شود. چون همیشه در یک دوریدور بی‌پایان از یال‌ها می افتدمی‌افتد. اما چنین دوری در DAGها وجود ندارد.( در DAG روش علامت‌گذاری کردننشانه‌گذاری رأس‌ها در DAG، بدترین زمانزمانِ اجرا را از [[تابع نمایی|نمایی]] (که به خاطر وجودِ مسیرهای چندگانه است) به [[تابع خطی|خطی]] کاهش می‌دهدمی‌کاهد.)
یک [[Multitree|درخت چندچندگانه]] گانه{{به انگلیسی|Multitree}} یکی از انواع ویژه و کارای DAG است که بسیاری از ویژگی‌های درخت را دارد. بازدهی و کارایی این نوع درخت زیاد استاست؛ برای مثال در الگئریتم ترویج[[انتشار باور |الگوریتم (belief propagation)انتشار باور]]. ▼
تعداد DAGهای ناهم‌ریخت، توسط [[Eric W. Weisstein|اریک وستاین]] {{به انگلیسی|Eric W. Weisstein}} حدس زد
▲یک درخت چند گانه یکی از انواع ویژه و کارای DAG است که بسیاری از ویژگی‌های درخت را دارد. بازدهی و کارایی این نوع درخت زیاد است برای مثال در الگئریتم ترویج باور (belief propagation) .
تعداد DAGهای غیرهمریخت توسط وستین کانجکتور( Weisstein's conjecture) محاسبه شد وکه تعداد DAGهای برچسب داربرچسب‌دار با nرأسn رأس، برابر است با ماتریس‌های <math>n</math>×<math>n</math> با درایه‌های 0 و 1 ( مثل [[ماتریس مجاورتهمسایگی]]) که تنها یک مقدار ویژهٔ حقیقی مثبت دارند.
== اصطلاحات علمی ==
رأس مبدأ ('''ریشه)''' رأسی است که هیچ یال ورودی ندارد، و یک رأس حفره ('''برگ)''' رأسی است که هیچ یال خروجی ندارد. یک DAG متناهی حداقل باید یک رأس مبدأریشه و یک رأس حفرهبرگ داشته باشد.
عمق هر رأس در گراف جهتجهت‌دار دار غیر مدورغیرمدور متناهی برابر است با طول طولانی‌ترین مسیر از رأس مبدأریشه تا آن رأس . ارتفاع هر رأس نیز برابر است با طول طولانی‌ترین مسیر بین آن رأس و رأس حفرهبرگ.
طول یک DAG متناهی برابر است با طول (تعدادیا یالتعداد هاییال‌های) طولانی‌ترین مسیرمسیرِ جهت دار،جهت‌دار، که این مقدار مساوی با ماکزیممبیشینه ارتفاعارتفاعِ تمام رأس‌های مبدأریشه‌ها و ماکزیممبیشینه عمقعمقِ تمام رأس‌های حفرهبرگ‌ها می‌باشد.
== کاربردها ==
استفاده از گراف جهتجهت‌دارِ دارِ غیر مدورغیرمدور، برخی الگوریتم‌ها را ساده‌تر و چابک ترچابک‌تر می‌کند. DAG در الگوریتم‌های مسیریابی، شبکه‌های پردازش داده، شجره[[شبکه‌های نامهبیزی]]، ها،[[تبارنامه|تبارنامه‌ها]]<nowiki/>، روش‌های [[فشرده‌سازی داده‌ها|فشرده‌سازی داده]] و بسیاری موارد دیگر کاربرد دارنددارد.{{سخ}}
{{ساختمان داده‌ها}}
| 