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

چکیده

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