گراف جهت دار وزن دار (Weighted Directed Graph / Digraph)، در ریاضیات (Mathematics)
انواع گراف وزن دار (Weighted Graph) را در آموزش زیر شرح دادیم :
گراف جهت دار وزن دار :
در این نوع گراف، یال ها دارای جهت (Direction) هستند. به عبارت دیگر، یال از رأس
\[ u \]به رأس
\[ v \]با یال از
\[ v \]به
\[ u \]متفاوت است و می توانند وزن های متفاوتی نیز داشته باشند. این ویژگی، آن را برای مدل سازی سیستم هایی ایده آل می کند که در آنها رابطه، یک طرفه یا نامتقارن است.
برای مثال، در یک شبکه اجتماعی مانند اینستاگرام، اگر کاربر A کاربر B را دنبال کند، یک یال جهت دار از A به B وجود دارد، اما الزاما برعکس آن صادق نیست. وزن این یال می تواند تعداد تعاملات باشد.
در مسائل بهینه سازی، گراف های جهت دار وزن دار برای مدل سازی جریان شبکه (Network Flow) استفاده می شوند. در این مسائل، وزن یال نشان دهنده حداکثر ظرفیت (Capacity) یک لوله یا مسیر است که سیال (داده، کالا و غیره) می تواند در آن جهت حرکت کند.
فرمول بندی ریاضی آن مشابه گراف ساده است، با این تفاوت که مجموعه یال ها
\[ E \]شامل زوج های مرتب (Ordered Pairs) از رئوس است. الگوریتم هایی مانند الگوریتم بلمن-فورد (Bellman-Ford) می توانند روی این گراف ها کار کنند، حتی اگر وزن ها منفی باشند.
