Maksimum Akış Problemi

Projenin Amacı

Sınırsız bir kaynaktan sınırsız bir havuza belirtilen tesisat üzerinden en fazla kaç birim akış sağlanabileceğini(Max-Flow) ve en fazla akış durumunda tesisattaki akışı sıfıra indirmek için en az kaç kenarın kesilmesi(Min-Cut) gerektiğini bulmak.

Kullanılan Algoritmalar

Problemi çözmek için genel olarak kullanılan algoritma Ford-Fulkerson algoritmasıdır. Akış yolu bulmak için ise Capacity Scaling algoritması kullanımıştır.

Proje Dökümanı

Döküman

Proje, Visual Studio 2019 üzerinde C# dilinde yazıldı.

Ekran Görüntüleri

Örnek Graf

Graf Oluşturma Ekranı - 1

Graf Oluşturma Ekranı - 2

Graf Oluşturma Ekranı - 3

Çözüm Grafı

• Kırmızı renkli kenarlar akışın sıfır olması için kesilmesi gereken kenarları temsil ediyor.
• Turuncu renkli kenarlar akışın sıfırdan farklı olduğu kenarları temsil ediyor.

Kaynaklar

1. Max Flow Ford Fulkerson | Network Flow | Graph Theory
2. Capacity Scaling | Network Flow | Graph Theory
3. Max Flow Problem
4. Ford Fulkerson algorithm for Maximum Flow Problem Example
5. Ford Fulkerson Algorithm for Maximum Flow Problem
6. Microsoft Automatic Graph Layout
7. How to create a message box in Windows Form Application
8. Modern Flat UI, Drop-down/Slider Menu, Side Menu, Responsive, Only Form - C#, WinForm
9. Max-flow Min-cut Algorithm