فناوری

گراف جهت دار غیرمدور (DAG) چیست؟

گراف چیست؟

هر مجموعه ای شامل یک سری نقاط و اتصالات بین آنها گراف نامیده میشود. که به نقاط گره و به اتصالات یال گفته میشود

در ریاضیات ، به ویژه نظریه گراف ، و علوم کامپیوتر ، یک گراف جهت دار غیر مدور (directed acyclic graph) گرافی جهت دار و بدون چرخه های جهت دار است. به زبان ساده تر DAG گرافی است که هیچ دوری در آن وجود ندارد . یعنی از رئوس و لبه ها تشکیل شده و هر لبه از یک راس به راس دیگر هدایت می شود ، به طوری که پیروی از آن جهت ها هرگز یک حلقه بسته ایجاد نمی کند. یک نمودار جهت دار یک DAG است اگر و فقط اگر بتوان آن را از نظر توپولوژیکی مرتب کرد ، با ترتیب دادن رئوس به صورت یک ترتیب خطی که با تمام جهات لبه سازگار باشد. DAG ها کاربردهای علمی و محاسباتی بی شماری دارند ، از زیست شناسی (تکامل ، درختان خانوادگی ، اپیدمیولوژی) گرفته تا جامعه شناسی (شبکه های استنادی) گرفته تا محاسبات (برنامه ریزی).

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

نمایش بیشتر

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا