گراف جهت دار بدون دور (Directed Acyclic Graph - DAG)، در ریاضیات (Mathematics)
انواع گراف جهت دار (Directed Graph / Digraph) را در آموزش زیر شرح دادیم :
گراف جهت دار بدون دور (Directed Acyclic Graph - DAG) :
یک گراف جهت دار بدون دور (DAG) گرافی است که هیچ دور جهت دار (Directed Cycle) در آن وجود نداشته باشد . یعنی نمی توان با پیروی از جهت یال ها از یک راس شروع کرد و دوباره به همان راس بازگشت. DAGها یکی از مهم ترین و پرکاربردترین انواع گراف های جهت دار در علوم کامپیوتر و ریاضیات هستند. کاربردهای اصلی آن ها شامل مدل سازی برنامه ریزی و وابستگی های زمانی (Scheduling) ، نمایش شبکه های معنایی (Semantic Networks) ، ساختار درختهای خانواده (Family Trees) ، و مدل سازی محاسبات (Computation) در سیستم های مدیریت جریان کار (Workflow) است. ویژگی مهم DAGها این است که می توان راس های آن را به صورت مرتب سازی توپولوژیکی (Topological Sort) مرتب کرد .
\[ \text{هیچ مسیر } v \leadsto v \text{ با طول مثبت وجود ندارد.} \] نویسنده علیرضا گلمکانی
شماره کلید 5463
گزینه ها 
نظرات 0 0 0