مرجع کلمات و اصطلاحات اختصاری

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

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

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

ارسال نظر