Ağ Akış Algoritmaları
Ağ akış algoritmaları, kapasiteli bir ağ üzerinden bir kaynaktan bir hedefe gönderilebilecek maksimum akış miktarını hesaplamaktadır; bu problemin optimumu, ağın minimum kesiti ile ikilik (duality) ilişkisiyle belirlenmektedir.
Tanım
Bir akış ağı, kenar kapasiteleri, bir kaynak ve bir hedef içeren yönlü bir grafiktir; bir maksimum akış algoritması, kapasitelere ve ara köşelerdeki korunum ilkesine uyarak, kaynaktan hedefe toplam akışı maksimize eden bir akış ataması bulmaktadır.
Kapsam
Bu konu, maksimum akış problemini ve algoritmalarını ele almaktadır: artırıcı yollar (augmenting paths) içeren Ford-Fulkerson yöntemini, çalışma süresini sınırlayan Edmonds-Karp ve Dinic iyileştirmelerini ve optimumu karakterize eden maksimum akış-minimum kesit teoremini kapsamaktadır. Ayrıca, iki parçalı eşleştirme (bipartite matching), köşe ayrık yollar (vertex-disjoint paths) ve proje seçimi gibi diğer problemlerin ağ akışına indirgenmesini de içermektedir. Akışın özel bir durumu olduğu genel doğrusal programlamayı (linear programming) ise dışlamaktadır.
Temel sorular
- Bir akış nasıl tanımlanır ve hangi kısıtlamaları karşılaması gerekir?
- Artık grafikteki (residual graph) artırıcı yollar (augmenting paths) akışı maksimuma doğru nasıl artırmaktadır?
- Maksimum akış neden minimum kesit kapasitesine eşittir?
- Edmonds-Karp ve Dinic algoritmaları polinom çalışma süresini nasıl garanti etmektedir?
- Eşleştirme ve diğer problemler maksimum akışa nasıl indirgenmektedir?
Anahtar kavramlar
- akış ağı
- kapasite ve korunum
- artırıcı yol (augmenting path)
- artık grafik (residual graph)
- maksimum akış-minimum kesit teoremi
- Edmonds-Karp algoritması
- Dinic algoritması
- iki parçalı eşleştirme indirgemesi (bipartite matching reduction)
Temel kuramlar
- Maksimum akış-minimum kesit teoremi
- Bir kaynaktan bir hedefe olan maksimum akışın değeri, onları ayıran bir kesitin minimum kapasitesine eşittir; Ford ve Fulkerson'a ait olan bu ikilik (duality), optimumluğu doğrulamakta ve akışı bağlantı ve bölme problemlerine bağlamaktadır.
- Artırıcı yollar (augmenting paths) ve artık grafikler (residual graphs)
- Ford-Fulkerson yöntemi, artık grafikte (residual graph) boş kapasiteye sahip yollar bularak akışı artırmaktadır; en kısa artırıcı yolları (Edmonds-Karp) seçmek veya seviye grafikleri (level graphs) ve engelleme akışları (blocking flows) kullanmak (Dinic), polinom zamanlı garantiler sağlamaktadır.
Klinik önem
Ağ akışı çok yönlü bir modelleme aracıdır: iki parçalı atama (bipartite assignment) ve çizelgeleme (scheduling) problemlerini çözmekte, ağların bağlantısını ve güvenilirliğini hesaplamakta, bilgisayar görüşünde grafik kesitleri (graph cuts) aracılığıyla görüntü segmentasyonu (image segmentation) yapmakta ve kapasitelerin ve darboğazların önemli olduğu lojistik, ulaşım planlaması ve proje seçimi optimizasyonunun temelini oluşturmaktadır.
Tarihçe
Ford ve Fulkerson, 1956 yılında ulaşım ağlarını incelerken maksimum akış problemini ve maksimum akış-minimum kesit teoremini tanıtmışlardır. Edmonds ve Karp (1972) ile bağımsız olarak Dinic (1970), ilk polinom zamanlı algoritmaları sunmuşlardır ve sonraki çalışmalar ise maksimum akışın asimptotik çalışma süresini sürekli olarak iyileştirmiştir.
Öne çıkan isimler
- Lester Ford
- Delbert Fulkerson
- Jack Edmonds
- Yefim Dinic
İlgili konular
Temel eserler
- fordfulkerson1956
- cormen2009
Sıkça sorulan sorular
- Maksimum akış-minimum kesit teoremi aslında neyi ifade etmektedir?
- Bu teorem, bir kaynaktan bir hedefe itilebilecek en büyük akış miktarının, kaynağı hedeften ayıran herhangi bir kenar kümesinin en küçük toplam kapasitesine eşit olduğunu belirtmektedir. Minimum kesit, maksimum akışı sınırlayan darboğaz görevi görmektedir.
- Basit Ford-Fulkerson neden polinom çalışma süresine sahip değildir?
- Eğer artırıcı yollar (augmenting paths) kötü seçilirse ve kapasiteler büyük (veya irrasyonel) ise, artırma sayısı çok büyük olabilir veya hatta sonlanmayabilir. En kısa artırıcı yolları (Edmonds-Karp) seçmek veya engelleme akışlarını (blocking flows) kullanmak (Dinic), artırma sayısını sınırlar ve polinom zamanı sağlamaktadır.