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

گراف جهت‌دار غیرمدور (به انگلیسی: Directed Acyclic Graph) یا گراف سودار^[1] بی‌دور^[2] با کوته‌نوشت DAG، در دانش رایانه و ریاضیات، یک گراف جهت‌دار است که هیچ گرافِ دوریای ندارد؛ یعنی هیچ مسیر جهت‌داری که رأس ابتدا و انتهای آن یکی باشد، وجود ندارد. به خاطر ویژگی‌های این نوع گراف می‌توان از آن در مدل کردن سیستم‌های علت و معلولی استفاده کرد.

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

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

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

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

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

ترتیب جزئی

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

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

a → b → c

و

(a → b → c, a → c)

ترتیب جزئی یکسانی در مورد ارتباط بین رأس‌ها را اعمال می‌کنند اما گراف جهت‌دار غیرمدور دوم یک یال اضافه‌تر دارد. از بین تمام گراف‌های جهت‌دار غیرمدورِ این چنینی، آن که کمترین تعداد یال را دارد ساده‌سازی ترایا (به انگلیسی: Transitive Reduction) و آن که بیشترین تعداد یال را دارد بستار ترایا (به انگلیسی: Transitive Closure) نامیده می‌شود.

ویژگی‌ها

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

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

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

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

یک درخت چندگانه (به انگلیسی: Multitree) یکی از انواع ویژه و کارای DAG است که بسیاری از ویژگی‌های درخت را دارد. بازدهی و کارایی این نوع درخت زیاد است؛ برای مثال در الگوریتم انتشار باور.

اریک ویستاین (به انگلیسی: Eric W. Weisstein) حدس زد^[3] و (McKay و دیگران 2004) اثبات کرد که تعداد DAGهای برچسب‌دار با n رأس، برابر است با ماتریس‌های ${\displaystyle n}$×${\displaystyle n}$ با درایه‌های ۰ و ۱ (مثل ماتریس همسایگی) که تنها یک مقدار ویژهٔ حقیقی مثبت دارند.^[4]

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

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

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

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

کاربردها

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

منابع

1. «گراف سودار» [ریاضی] هم‌ارزِ «directed graph»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر هفتم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۷۸-۹۶۴-۷۵۳۱-۹۴-۸ (ذیل سرواژهٔ گراف سودار)
2. «گراف بی‌دور» [ریاضی] هم‌ارزِ «acyclic graph»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر سوم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۵۰-۸ (ذیل سرواژهٔ گراف بی‌دور)
3. Weisstein, Eric W. "Weisstein's Conjecture". MathWorld.
4. McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; Wilf, H. (2004), "Acyclic digraphs and eigenvalues of (0,1)-matrices", Journal of Integer Sequences, 7, Article 04.3.3.

(انگلیسی)

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.