Ford-Fulkerson Algoritması
Ford-Fulkerson Algorithm for Maximum Flow · Ayrıca şöyle bilinir: Ford-Fulkerson method, augmenting path method
Lester R. Ford ve Delbert R. Fulkerson tarafından 1956'da geliştirilen Ford-Fulkerson Algoritması, bir akış ağındaki maksimum akışı hesaplamak için temel bir yöntemdir. Kapasite kısıtlamalarına sahip yönlü bir graf üzerinden bir kaynaktan bir hedefe gönderilebilecek maksimum akış miktarını bulur.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Yönlü veya yönsüz akış ağlarında pozitif tamsayı kapasiteleri ile maksimum akışı bulmak için Ford-Fulkerson algoritmasını uygulayın. Küçük ve orta ölçekli ağlar için iyi çalışır ve ağ akışı kavramlarının sezgisel anlaşılmasını sağlar. Çok büyük ağlar için veya tamsayı akışlarının gerekli olduğu durumlarda, daha iyi en kötü durum performansı için Edmonds-Karp (BFS kullanarak) veya Dinic algoritmasını düşünün. Algoritma davranışını anlamanın hız kadar önemli olduğu durumlarda kullanın.
Güçlü yönler & sınırlılıklar
- Artırıcı yollara dayanan basit ve sezgisel yaklaşım
- Kapasiteler rasyonel veya tamsayı olduğunda optimal çözüm garantisi
- Küçük tamsayı kapasiteli ağlar için verimli
- Maksimum akış-minimum kesim ikiliğini anlamak için teorik temeli oluşturur
- Hem yönlü hem de yönsüz graflarla çalışır
- Zaman karmaşıklığı kapasite değerlerine bağlıdır (genel olarak polinom değil; irrasyonel kapasitelerle üssel olabilir)
- Kapasiteler irrasyonel ise sonlanmayabilir (rasyonel aritmetik ile dikkatli uygulama gerektirir)
- Büyük ağlarda Edmonds-Karp veya Dinic gibi özel algoritmalardan daha az verimli
- Artırıcı yol seçim sırasına duyarlı
SSS
Maksimum akış-minimum kesim teoremi nedir?
Teorem, kaynaktan hedefe olan maksimum akışın, kaynaktan hedefe ayıran herhangi bir kesimin minimum kapasitesine eşit olduğunu belirtir. Bu, hem teorik bir içgörü hem de akış algoritmaları için bir doğrulama yöntemi sağlar.
Algoritma neden bazen yavaş yakınsar?
Talihsiz yol seçimleriyle, algoritma daha büyük artışlar mümkünken bile iterasyon başına yalnızca bir birim akış artırabilir. Genişlik öncelikli arama (Edmonds-Karp) kullanmak polinom zamanlı yakınsamayı garanti eder.
Algoritma yönsüz kenarları nasıl ele alır?
Her yönsüz kenarı, her ikisi de aynı kapasiteye sahip iki yönlü kenarla değiştirin. Algoritma daha sonra yönlü ağda akışı bulur.
Bir kenardaki akış ile artık kapasite arasındaki fark nedir?
Bir kenardaki akış, boyunca gönderilen malzeme miktarını temsil ederken, artık kapasite mevcut kalan kapasitedir. Akış arttıkça artık kapasite azalır ve ters kenarlar akışı geri alma yeteneğini izler.
Kaynaklar
- Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404. DOI: 10.4153/CJM-1956-045-5 ↗
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. ISBN: 978-0-262-03384-8
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Ford-Fulkerson Algorithm for Maximum Flow. ScholarGate. https://scholargate.app/tr/operations-research/ford-fulkerson-algorithm
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Bellman-Ford AlgoritmasıYöneylem araştırması↔ karşılaştır
- Dijkstra AlgoritmasıYöneylem araştırması↔ karşılaştır
- Push-Relabel AlgoritmasıYöneylem araştırması↔ karşılaştır
- Simpleks YöntemiYöneylem araştırması↔ karşılaştır