/maxFlowProblem

Max-flow min-cut theorem states that the maximum flow through any network from a given source to a given sink is exactly equal to the minimum sum of a cut. This theorem can be verified using the Ford-Fulkerson algorithm.

Primary LanguageC#

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

graf1

Graf Oluşturma Ekranı - 1

menu1

Graf Oluşturma Ekranı - 2

menu2

Graf Oluşturma Ekranı - 3

menu2

Çözüm Grafı

graf2

  • 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