گراف جهت دار غیرمدور ( به انگلیسی: Directed Acyclic Graph ) یا گراف سودار[ ۱] بی دور[ ۲] با کوته نوشت DAG، در دانش رایانه و ریاضیات، یک گراف جهت دار است که هیچ گرافِ دوریای ندارد؛ یعنی هیچ مسیر جهت داری که رأس ابتدا و انتهای آن یکی باشد، وجود ندارد. به خاطر ویژگی های این نوع گراف می توان از آن در مدل کردن سیستم های علت و معلولی استفاده کرد.
یک دور ( به انگلیسی: Cycle ) مسیر ساده ای است که راس شروع و پایانی آن یکی باشد. گراف ساده جهت داری را که دارای دور نیست، غیر مدور ( به انگلیسی: Acyclic ) می نامند.
یک دور در گراف ساده بدون جهت حداقل شامل سه یال متفاوت است که به جز راس ابتدایی و انتهایی، هیچ راسی در آن تکراری نیست.
خواص گراف جهت دار غیرمدور اجازه می دهد که ترتیب جزئی کوچکتر مساوی بین رأس های گراف به صورت روبرو تعریف شود: برای هر دو رأس دلخواه u , v گراف می گوییم u < = v اگر و فقط اگر یک مسیر جهت دار از u به v وجود داشته باشد.
ممکن است گراف های جهت دار غیرمدور مختلف منجر به ترتیب جزئی یکسانی بشوند: برای مثال دو گراف
a → b → c
و
( a → b → c, a → c )
ترتیب جزئی یکسانی در مورد ارتباط بین رأس ها را اعمال می کنند اما گراف جهت دار غیرمدور دوم یک یال اضافه تر دارد. از بین تمام گراف های جهت دار غیرمدورِ این چنینی، آن که کمترین تعداد یال را دارد ساده سازی ترایا ( به انگلیسی: Transitive Reduction ) و آن که بیشترین تعداد یال را دارد بستار ترایا ( به انگلیسی: Transitive Closure ) نامیده می شود.
هر گراف جهت دار غیرمدوری یک مرتب سازی موضعی ( توپولوژیک ) دارد. به این صورت که هر رأس قبل از تمام رأس هایی می آید که به آن ها یالی دارد. در حالت کلی این مرتب سازی یکتا نیست. مرتب سازی موضعیِ هر دو گرافی که یک ترتیب جزئی دارند، یکسان است. DAGها را می توان مفهوم گسترده شده ای از درخت ها در نظر گرفت. درخت هایی که در آنها، دسته ای از زیردرخت ها وجود دارد که می توانند در قسمت های مختلف درخت سهیم شوند؛ یعنی از هر رأس به بیش از یک زیردرخت می توان دسترسی داشت. در درخت هایی که تعداد زیادی زیردرختِ یکسان دارند، این ویژگی می تواند فضای مورد یاز برای ذخیره کردنِ این ساختار را تا اندازهٔ زیادی کاهش دهد. به بیانی ساده تر، DAG می تواند با استفاده از الگوریتم زیر، مانند جنگلی از درختان ریشه دار عمل کند:
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفیک دور ( به انگلیسی: Cycle ) مسیر ساده ای است که راس شروع و پایانی آن یکی باشد. گراف ساده جهت داری را که دارای دور نیست، غیر مدور ( به انگلیسی: Acyclic ) می نامند.
یک دور در گراف ساده بدون جهت حداقل شامل سه یال متفاوت است که به جز راس ابتدایی و انتهایی، هیچ راسی در آن تکراری نیست.
خواص گراف جهت دار غیرمدور اجازه می دهد که ترتیب جزئی کوچکتر مساوی بین رأس های گراف به صورت روبرو تعریف شود: برای هر دو رأس دلخواه u , v گراف می گوییم u < = v اگر و فقط اگر یک مسیر جهت دار از u به v وجود داشته باشد.
ممکن است گراف های جهت دار غیرمدور مختلف منجر به ترتیب جزئی یکسانی بشوند: برای مثال دو گراف
a → b → c
و
( a → b → c, a → c )
ترتیب جزئی یکسانی در مورد ارتباط بین رأس ها را اعمال می کنند اما گراف جهت دار غیرمدور دوم یک یال اضافه تر دارد. از بین تمام گراف های جهت دار غیرمدورِ این چنینی، آن که کمترین تعداد یال را دارد ساده سازی ترایا ( به انگلیسی: Transitive Reduction ) و آن که بیشترین تعداد یال را دارد بستار ترایا ( به انگلیسی: Transitive Closure ) نامیده می شود.
هر گراف جهت دار غیرمدوری یک مرتب سازی موضعی ( توپولوژیک ) دارد. به این صورت که هر رأس قبل از تمام رأس هایی می آید که به آن ها یالی دارد. در حالت کلی این مرتب سازی یکتا نیست. مرتب سازی موضعیِ هر دو گرافی که یک ترتیب جزئی دارند، یکسان است. DAGها را می توان مفهوم گسترده شده ای از درخت ها در نظر گرفت. درخت هایی که در آنها، دسته ای از زیردرخت ها وجود دارد که می توانند در قسمت های مختلف درخت سهیم شوند؛ یعنی از هر رأس به بیش از یک زیردرخت می توان دسترسی داشت. در درخت هایی که تعداد زیادی زیردرختِ یکسان دارند، این ویژگی می تواند فضای مورد یاز برای ذخیره کردنِ این ساختار را تا اندازهٔ زیادی کاهش دهد. به بیانی ساده تر، DAG می تواند با استفاده از الگوریتم زیر، مانند جنگلی از درختان ریشه دار عمل کند:
wiki: گراف جهت دار غیرمدور