حل تعدادی از مسائل بهینه سازی ابرگراف های جهت دار با استفاده از گراف پرشین جهت دار

ابرگراف های جهت دار به عنوان تعمیمی از گراف های معمولی، ابزار قدرتمندی برای مدلسازی روابط چند سویه و جهت دار در مسائل پیچیده شبکه ای محسوب می‌شوند. در این ساختارها، بسیاری از مسائل کلاسیک بهینه سازی نظیر یافتن کوتاهترین مسیر و درخت فراگیر کمینه، به صورت مسائل نوین با چالش های نظری و محاسباتی قابل توجه ظاهر می‌شوند، به ویژه زمانی که ابرگراف از نوع غیریکنواخت باشد. در سال های اخیر، پژوهش های متعددی به بررسی جنبه های نظری، الگوریتمی و کاربردی ابرگراف های جهت دار پرداخته اند، با این حال، نبود یک چارچوب منسجم که بتواند همزمان مسائل کوتاهترین ابرمسیر و ابردرخت فراگیر کمینه را در ابرگراف جهت دار به طور کارآمد حل کند، همچنان محسوس است. تمرکز اصلی مقاله بر معرفی و تحلیل گراف های هم ارز با ابرگراف های جهت دار، به عنوان ابزار کلیدی برای تبدیل مسائل بهینه سازی روی ابرگراف ها به مسائل متناظر روی گراف های جهت دار است. این رویکرد، امکان بهره گیری مستقیم از الگوریتم های کلاسیک نظیر الگوریتم دایجسترا و الگوریتم کراسکال را فراهم می‌سازد. نوآوری اصلی این مقاله در یکپارچه سازی کردن نتایج پراکنده‌ی موجود، ارائه‌ی یک چارچوب وزن دهی مناسب برای ابرگراف های جهت دار یکنواخت و غیریکنواخت و تحلیل دقیق نگاشت ابرمسیرها و ابردرخت ها به مسیرها و درخت های متناظر در گراف پرشین جهت دار نهفته است. همچنین، پیچیدگی زمانی الگوریتم های متناظر به صورت تحلیلی بررسی شده و با ارائه‌ی مثال عددی، کارایی و قابلیت تعمیم چارچوب پیشنهادی نشان داده می‌شود.