ارایه یک رویکرد ابتکاری نوین برای ساده سازی گراف اولیه مسأله بیشینه جریان

Abstract

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