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

مثال ساده‌ای از یک گراف جهت‌دار غیرمدور

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

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

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

نمونه‌ای از یک دور جهت‌دار. یک گراف جهت دار غیرمدور هیچ دور جهت‌داری ندارد

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

ترتیب جزئی

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

ممکن است گراف‌های جهت‌دار غیرمدور مختلف منجر به ترتیب جزئی یکسانی بشوند: برای مثال دو گراف الگو:وسط‌چین 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 است که بسیاری از ویژگی‌های درخت را دارد. بازدهی و کارایی این نوع درخت زیاد است؛ برای مثال در الگوریتم انتشار باور.

اریک ویستاین الگو:به انگلیسی حدس زد و الگو:Harvtxt اثبات کرد که تعداد DAGهای برچسب‌دار با n رأس، برابر است با ماتریس‌های $n$×$n$ با درایه‌های ۰ و ۱ (مثل ماتریس همسایگی) که تنها یک مقدار ویژهٔ حقیقی مثبت دارند.

اصطلاحات علمی

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

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

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

کاربردها

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

منابع

 الگو:نشان زبانالگو:چپ‌چین Eric W. Weisstein, Weisstein's Conjecture at MathWorld.
 الگو:نشان زبانالگو:چپ‌چین 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
 الگو:نشان زبانالگو:چپ‌چین Ward Cunningham: Tips For Writing Pattern Languages*
 الگو:نشان زبانالگو:چپ‌چین M. Crochemore and R. Verin, Direct Construction of Compact Directed Acyclic Word Graphs, 8th Annual Symposium, CPM 97, Aarhus, Denmark, 116-129, 1997.