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

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

درعلوم کامپیوتر و ریاضیات، گراف جهت‌دار غیرمدور ((به انگلیسی: Directed acyclic graph)‏ یا بصورت خلاصه DAG) یک گراف جهت‌دار است که هیچ دور جهت‌داری ندارد (یعنی هیچ مسیر جهت‌داری که رأس ابتدا و انتهای آن یکی باشد، وجود ندارد). به خاطر ویژگی‌های این نوع گراف می‌توان از آن در مدل کردن سیستمهای علت و معلولی استفاده کرد.

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

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

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

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

ترتیب جزئی

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

ممکن است گراف‌های جهت‌دار غیرمدور مختلف منجر به ترتیب جزئی یکسانی بشوند: برای مثال دو گراف

a → b → c

و

(a → b → c, a → c)

ترتیب جزئی یکسانی در مورد ارتباط بین رئوس را اعمال می‌کنند اما گراف جهت‌دار غیرمدور دوم یک یال اضافه تر دارد. از بین تمام گراف‌های جهت‌دار غیرمدور این چنینی آنکه کمترین تعداد یال را دارد (به انگلیسی: transitive reduction)‏ نامیده شده و آنکه بیشترین تعداد یال را دارد (به انگلیسی: transitive closure)‏ نامیده شده‌است.

ویژگی‌ها

هر گراف جهت دار غیرمدوری یک مرتب سازی مکان شناسی(Topological) دارد، به این صورت که هر رأس قبل از تمام رأس هایی می‌آید که به آنها یالی دارد. در حالت کلی این مرتب سازی یکتا و منحصر به فرد نیست. مرتب سازی مکان شناسیِ هر دو گرافی که یک ترتیب جزئی دارند، یکسان است. DAG‌ها را می‌توان به عنوان تعمیم یافتهٔ مفهوم درخت‌ها در نظر گرفت. درخت هایی که در آنها، دستهٔ از زیردرخت‌ها که می‌توانند در قسمت‌های مختلف درخت سهیم شوند (یعنی از هر رأس به بیش از یک دیردرخت می‌توان دسترسی داشت). در یک درخت با تعداد زیادی زیردرخت یکسان، این می‌تواند فضای مورد نیاز برای ذخیره کردن این یاختار را تا حد خوبی کاهش دهد. در بیان ساده تر،DAG می‌تواند با استفاده از الگوریتم زیر مانند جنگلی از درختان ریشه دار عمل کند:

• تا وقتی که رأس v با درجهٔ n>1 وجود دارد؛
  • nکپی از رأس v با یال‌های خروجی یکسان و بدون یال ورودی بساز.
  • یکی از یال‌های ورودی v را به هر رأس وصل کن.
  • رأس v را پاک کن.

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

بعضی از الگوریتم‌ها روی DAG‌ها نسبت به گراف‌های معمولی پیاده سازی ساده تری دارند. برای مثال الگوریتم جستجویی مثل جستجو از عمق (depth-first search) بدون تکرارکنندهٔ گود کردن (itrative deepening) به صورت معمول باید رئوسی را که بررسی کرده علامت گذاری کند و دوباره آنها را چک نکند. و اگر این روند را به درستی انجام ندهد، این چک کردن‌ها هیچ وقت تمام نمی‌شود چون همیشه در یک دوری از یال‌ها می افتد. اما چنین دوری در DAG‌ها وجود ندارد.( در DAG روش علامت گذاری کردن رأس‌ها بدترین زمان اجرا را از نمایی (به خاطر مسیرهای چندگانه) به خطی کاهش می‌دهد.)

یک درخت چند گانه یکی از انواع ویژه و کارای DAG است که بسیاری از ویژگی‌های درخت را دارد. بازدهی و کارایی این نوع درخت زیاد است برای مثال در الگئریتم ترویج باور (belief propagation) .

تعداد DAG‌های غیرهمریخت توسط وستین کانجکتور( Weisstein's conjecture) محاسبه شد و تعداد DAG‌های برچسب دار با nرأس برابر است با ماتریس‌های $n$×$n$ با درایه‌های 0 و 1 ( مثل ماتریس مجاورت) که تنها یک مقدار ویژهٔ حقیقی مثبت دارند.

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

رأس مبدأ (ریشه) رأسی است که هیچ یال ورودی ندارد، و یک رأس حفره (برگ) رأسی است که هیچ یال خروجی ندارد. یک 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.