شار بيشینه و روش فورد-فالكرسون

توضیحات

در جلسه بیست و سوم درس طراحی الگوریتم دکتر حمید حاج سیدجوادی که اهمیت به سزایی در کنکور ارشد کامپیوتر و کنکور ارشد آی تی و نیز کنکور دکتری کامپیوتر و کنکور دکتری آی تی دارد، مطالب مهمی درباره مبحث شار بيشینه و روش فورد-فالكرسون ارائه می‌شود. همانطور كه می‌توانید یک نقشه راه را به عنوان یک گراف جهت دار مدل کنید تا كوتاهترین مسیر از یک نقطه به نقطه ديگر بیابید، می‌توانید يک گراف جهت دار را به عنوان یک «شبکه شار» تفسیر کنید و از آن برای پاسخ به سؤاﻻت مربوط به شار مواد استفاده کنید. تصور کنید که یک ماده در يك سیستم از یک منبع، جایی كه مواد تولید می‌شود، به سمت يک سینک، جایی كه مصرف می‌شود، حركت می‌کند. منبع مواد را با سرعت ثابتی تولید می‌کند و سینک با همان سرعت مواد را مصرف می‌مند. "شار" مواد در هر نقطه از سیستم سرعت حركت مواد است. شبكه‌های شار می‌توانند بسیاری از مسائل را مدل‌سازی کنند، از جمله مایعات عبوری از لوله‌ها، قطعات از طریق خطوط مونتاژ، جريان از طریق شبکه‌ها و مدارات الکتریکی و اطلاعات از طریق شبکه‌های ارتباطی. در این جلسه شبکه شار و مسئله شار بیشینه تعریف می‌شود. سپس روش Ford-Fulkerson تدریس می‌شود که به سه ایده مربوط می‌شود که فراتر از روش هستند و به بسیاری از الگوریتم‌ها و مسائل شار مربوط می‌شوند: 1) شبکه‌های باقیمانده 2) مسائل افزایشی 3) برش های شبکه شار. در ادامه این سه مبحث به تفصیل با مثال و شکل و با جزئیات کامل تشریح می‌گردد. پس از آن الگوریتم اصلی سپس Ford-Fulkerson و شبه کد آن با یک مثال با جزئیات کامل تشریح و تحلیل شده و در انتها پیچیدگی زمانی آن ارائه می‌گردد. در آخر 8 تست کنکور ارشد و دکترای طراحی الگوریتم در خصوص شبکه شار و شار بیشینه مطرح و حل تشریحی آنها ارائه می‌گردد.