الگوریتم های یافتن جریان بیشینه در گراف های مسطح

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

کلیدواژه ها:

جریان بیشینه ، گراف مسطح ، شار بیشینه