نمایش مبدأ برای گراف جهت‌دار غیرمدور

[[پرونده:Directed acyclic graph.png|چپ|150px|بندانگشتی|مثال ساده‌ای از یک گراف جهت‌دار غیرمدور]]

'''گراف جهت‌دار غیرمدور''' {{انگلیسی|Directed Acyclic Graph}} یا '''گراف سودار<ref>{{یادکرد فرهنگستان|مصوب=گراف سودار|بیگانه=directed graph|بیگانه در فارسی=|حوزه=ریاضی|دفتر=هفتم|بخش=فارسی|سرواژه=گراف سودار}}</ref> بی‌دور'''<ref>{{یادکرد فرهنگستان|مصوب=گراف بی‌دور|بیگانه=acyclic graph|بیگانه در فارسی=|حوزه=ریاضی|دفتر=سوم|بخش=فارسی|سرواژه=گراف بی‌دور}}</ref> با کوته‌نوشت '''DAG'''، در [[دانش رایانه]] و [[ریاضیات]]، یک [[گراف جهت‌دار]] است که هیچ [[گراف دوری|گرافِ دوری]]<nowiki/>ای ندارد؛ یعنی هیچ مسیر جهت‌داری که رأس ابتدا و انتهای آن یکی باشد، وجود ندارد. به خاطر ویژگی‌های این نوع گراف می‌توان از آن در مدل کردن سیستم‌های علت و معلولی استفاده کرد.

== تعریف دور و نداشتن آن ==
یک دور {{انگلیسی|Cycle}} مسیر ساده‌ای است که راس شروع و پایانی آن یکی باشد. گراف ساده جهت‌داری را که دارای دور نیست، غیر مدور {{انگلیسی|Acyclic}} می‌نامند.
[[پرونده:DC8.png|100px|بندانگشتی|چپ|نمونه‌ای از یک دور جهت‌دار. یک گراف جهت دار غیرمدور هیچ دور جهت‌داری ندارد]]

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

== ترتیب جزئی ==
خواص گراف جهت‌دار غیرمدور اجازه می‌دهد که ترتیب جزئی کوچکتر مساوی بین رأس‌های گراف به صورت روبرو تعریف شود: برای هر دو رأس دلخواه <math>u, v</math> گراف می‌گوییم <math>u<=v</math> اگر و فقط اگر یک مسیر جهت‌دار از <math>u</math> به <math>v</math> وجود داشته باشد.

ممکن است گراف‌های جهت‌دار غیرمدور مختلف منجر به ترتیب جزئی یکسانی بشوند: برای مثال دو گراف
{{وسط‌چین}}
''a'' → ''b'' → ''c''
{{پایان}}
و
{{وسط‌چین}}
(''a'' → ''b'' → ''c,'' ''a'' → ''c'')
{{پایان}}
[[ترتیب جزئی]] یکسانی در مورد ارتباط بین رأس‌ها را اعمال می‌کنند اما گراف جهت‌دار غیرمدور دوم یک یال اضافه‌تر دارد. از بین تمام گراف‌های جهت‌دار غیرمدورِ این چنینی، آن که کمترین تعداد یال را دارد [[Transitive Reduction|ساده‌سازی ترایا]] {{انگلیسی|Transitive Reduction}} و آن که بیشترین تعداد یال را دارد [[بستار تعدی|بستار ترایا]] {{انگلیسی|Transitive Closure}} نامیده می‌شود.

== ویژگی‌ها ==
هر گراف جهت‌دار غیرمدوری یک [[مرتب‌سازی توپولوژیکی|مرتب‌سازی موضعی]] (توپولوژیک) دارد. به این صورت که هر رأس قبل از تمام رأس‌هایی می‌آید که به آن‌ها یالی دارد. در حالت کلی این مرتب‌سازی یکتا نیست. مرتب‌سازی موضعیِ هر دو گرافی که یک ترتیب جزئی دارند، یکسان است. DAGها را می‌توان مفهوم گسترده شده‌ای از [[درخت (نظریه گراف)|درخت‌ها]] در نظر گرفت. درخت‌هایی که در آنها، دسته‌ای از زیردرخت‌ها وجود دارد که می‌توانند در قسمت‌های مختلف درخت سهیم شوند؛ یعنی از هر رأس به بیش از یک زیردرخت می‌توان دسترسی داشت. در درخت‌هایی که تعداد زیادی زیردرختِ یکسان دارند، این ویژگی می‌تواند فضای مورد یاز برای ذخیره کردنِ این ساختار را تا اندازهٔ زیادی کاهش دهد. به بیانی ساده‌تر، DAG می‌تواند با استفاده از الگوریتم زیر، مانند جنگلی از [[درخت‌های ریشه‌دار|درختان ریشه‌دار]] عمل کند:
* تا وقتی که رأس v با درجهٔ n>1 وجود دارد؛
** n کپی از رأس v با یال‌های خروجی یکسان و بدون یال ورودی بساز.
** یکی از یال‌های ورودی v را به هر رأس وصل کن.
** رأس v را [[پاک کن]].

اگر ما گرافی را بدون تغییر یا مقایسهٔ برابری رأس‌ها پیمایش کنیم، این جنگل با DAG اولیه یکسان خواهد بود.

بعضی از الگوریتم‌ها روی DAGها نسبت به گراف‌های معمولی پیاده‌سازی ساده‌تری دارند. برای مثال الگوریتم جستجویی مانند [[الگوریتم جستجوی عمق اول|جستجوی اول عمق]] (DFS) بدونِ [[جستجوی عمق اول عمیق‌کننده تکراری|عمیق‌کنندهٔ تکراری]] (Iterative Deepening)، به صورت معمول باید رأس‌هایی را که بررسیده نشانه‌گذاری کند تا از بررسی دوباره‌شان بپرهیزد، و اگر این روند را به درستی انجام ندهد، بررسی رأس‌ها هیچ وقت تمام نمی‌شود. چون همیشه در یک دور بی‌پایان از یال‌ها می‌افتد. اما چنین دوری در DAGها وجود ندارد. روش نشانه‌گذاری رأس‌ها در DAG، بدترین زمانِ اجرا را از [[تابع نمایی|نمایی]] (که به خاطر وجودِ مسیرهای چندگانه است) به [[تابع خطی|خطی]] می‌کاهد.

یک [[Multitree|درخت چندگانه]] {{به انگلیسی|Multitree}} یکی از انواع ویژه و کارای DAG است که بسیاری از ویژگی‌های درخت را دارد. بازدهی و کارایی این نوع درخت زیاد است؛ برای مثال در [[انتشار باور|الگوریتم انتشار باور]].

[[اریک ویستاین]] {{به انگلیسی|Eric W. Weisstein}} حدس زد<ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref> و {{harvtxt|McKay|Royle|Wanless|Oggier|2004}} اثبات کرد که تعداد DAGهای برچسب‌دار با n رأس، برابر است با ماتریس‌های <math>n</math>×<math>n</math> با درایه‌های ۰ و ۱ (مثل [[ماتریس همسایگی]]) که تنها یک مقدار ویژهٔ حقیقی مثبت دارند.<ref>{{citation|last1=McKay|first1=B. D.|author1-link=Brendan McKay|last2=Royle|first2=G. F.|author2-link=Gordon Royle|last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E.|last5=Sloane|first5=N. J. A.|author5-link= Neil Sloane|last6=Wilf|first6=H.|author6-link=Herbert Wilf|title=Acyclic digraphs and eigenvalues of (0,1)-matrices|journal=[[Journal of Integer Sequences]]|volume=7|year=2004|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html}}, Article 04.3.3.</ref>

== اصطلاحات علمی ==
'''ریشه''' رأسی است که هیچ یال ورودی ندارد، و '''برگ''' رأسی است که هیچ یال خروجی ندارد. یک DAG متناهی حداقل باید یک ریشه و یک برگ داشته باشد.

عمق هر رأس در گراف جهت‌دار غیرمدور متناهی برابر است با طول طولانی‌ترین مسیر از ریشه تا آن رأس. ارتفاع هر رأس نیز برابر است با طول طولانی‌ترین مسیر بین آن رأس و برگ.

طول یک DAG متناهی برابر است با طول (یا تعداد یال‌های) طولانی‌ترین مسیرِ جهت‌دار، که این مقدار مساوی با بیشینه ارتفاعِ تمام ریشه‌ها و بیشینه عمقِ تمام برگ‌ها می‌باشد.

== کاربردها ==
استفاده از گراف جهت‌دارِ غیرمدور، برخی الگوریتم‌ها را ساده‌تر و چابک‌تر می‌کند. DAG در الگوریتم‌های مسیریابی، شبکه‌های [[پردازش داده]]، [[شبکه‌های بیزی]]، [[تبارنامه]]‌ها<nowiki/>، روش‌های [[فشرده‌سازی داده‌ها|فشرده‌سازی داده]] و بسیاری موارد دیگر کاربرد دارد.

== منابع ==
{{پانویس}}
  {{نشان زبان|en}}{{چپ‌چین}} Eric W. Weisstein, Weisstein's Conjecture at MathWorld.
  {{نشان زبان|en}}{{چپ‌چین}} McKay, B. D. ; Royle, G. F. ; Wanless, I. M. ; Oggier, F. E. ; Sloane, N. J. A. ; and Wilf, H. "Acyclic Digraphs and Eigenvalues of (0,1)-Matrices." J. Integer Sequences 7, Article 04.3.3, 1-5, 2004. http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf or http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html
  {{نشان زبان|en}}{{چپ‌چین}} Ward Cunningham: Tips For Writing Pattern Languages*
  {{نشان زبان|en}}{{چپ‌چین}} M. Crochemore and R. Verin, Direct Construction of Compact Directed Acyclic Word Graphs, 8th Annual Symposium, CPM 97, Aarhus, Denmark, 116-129, 1997.
{{پانویس-نظریه گراف}}
{{ساختمان داده‌ها}}
[[رده:پایگاه داده‌ها]]
[[رده:گراف‌های جهت‌دار]]
[[رده:مدل‌های آماری]]
[[رده:مدل‌های گرافیکی]]
[[رده:نظریه گراف]]
[[رده:ویکی‌سازی رباتیک]]
[[رده:ساختمان داده و الگوریتم]]