مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.

====== شبکه شار ======
در این مسایل یک گراف داریم که دو گره مبدأ و مقصد دارد و هر یال یک ظرفیت دارد. می‌خواهیم حداکثر شار را از مبدأ به مقصد برسانیم، طوری که شار عبوری از یک یال از ظرفیت آن کمتر باشد و بقای شار برقرار باشد (شاری از بین نرود و به وجود هم نیاید). هدف بیشینه کردن شار عبوری است.

===== شار بیشینه با پیمایش گراف =====
گراف جدیدی به نام متمم شار می‌سازیم که در آن شار عبوری از هر رأس به رأس دیگر نشان داده شده است. هر بار یک مسیر از مبدأ به مقصد با استفاده از [[الگوریتم:پیمایش_گراف|پیمایش گراف]] به دست می‌آوریم. در ابتدا وزن یالهای این گراف به اندازه‌ی ظرفیت آنها است ولی با عبور دادن شار در یک جهت در گراف اصلی، در گراف متمم شار در خلاف آن جهت شار اضافه و در همان جهت کم می‌شود تا بتواند شار عبوری را خنثی کند. این کار را ادامه می‌دهیم تا دیگر در گراف متمم شار مسیری پیدا نشود که از میدأ به مقصد برود. در این صورت به شار بیشینه رسیده‌ایم.

اگر از پیمایش عمقی گراف استفاده کنیم، زمان الگوریتم $O(|E|f)$ است که $f$ شار بیشینه است و می‌تواند عدد بزرگی باشد. پس باید از پیمایش عرضی گراف استفاده کنیم که در این صورت زمان الگوریتم $O(|V||E|^2)$ است.

[[http://fa.wikipedia.org/wiki/%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D8%A8%DB%8C%D8%B4%DB%8C%D9%86%D9%87_%D8%AC%D8%B1%DB%8C%D8%A7%D9%86|مطالب بیشتر در مورد شار بیشینه]]

====== تطابق ======
مسأله‌ی تطابق بیشینه در گراف بدون وزن، می‌خواهد حداکثر تعداد یالهایی را پیدا کند که سر مشترک نداشته باشند.

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

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

زمان این الگوریتم $O(|V||E|)$ است.

[[http://en.wikipedia.org/wiki/Matching_(graph_theory)#In_unweighted_bipartite_graphs|مطالب بیشتر در مورد تطابق دوبخشی در گراف بدون وزن]]

مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه