Ford-Fulkerson Algoritması Nedir?
Ford-Fulkerson algoritması, bir ağdaki kaynak (kaynak düğüm) ile hedef (hedef düğüm) arasındaki maksimum akışı bulmak için kullanılan etkili bir yöntemdir. Bu algoritma, artırılmış yolları bularak ve bu yollar üzerinden akışı artırarak çalışır.
Ford-Fulkerson algoritması, bir yönlü bir grafikteki iki düğüm arasındaki maksimum akışı hesaplamak için kullanılan bir kesme-akış teoremi ispatıdır. Artırılmış yollar bularak ve bu yolların kapasitesini aşmayacak şekilde akışı artırarak maksimum akışı bulur.
Adım adım çözümlü örnekler
Basit bir Ford-Fulkerson örneği ile algoritmayı açıklayınız.
1. Kaynak (s) ve hedef (t) düğümlerini belirleyin. 2. 's'den 't'ye giden, kapasitesi pozitif olan bir artırılmış yol bulun. 3. Bu yolun minimum kapasitesini (akış artışı) belirleyin. 4. Bu akış artışını yol üzerindeki tüm kenarların kapasitesinden çıkarın ve ters kenarların kapasitesine ekleyin (artık kapasite grafiği). 5. Artık 's'den 't'ye giden bir yol kalmayana kadar 2-4 arası adımları tekrarlayın. 6. Tüm akış artışlarının toplamı maksimum akıştır.
Ford-Fulkerson algoritmasının temel mantığını örnekle açıklayınız.
Bir su boru hattı düşünün. Kaynak (s) suyu pompalar ve hedef (t) suyu alır. Boru hatlarının (kenarların) belirli bir taşıma kapasitesi vardır. Ford-Fulkerson, suyu 's'den 't'ye en verimli şekilde nasıl taşıyabileceğimizi bulmaya çalışır. Bunu, her seferinde mevcut en iyi yolu bularak ve o yoldan olabildiğince fazla su göndererek yapar. Bir yol tıkandığında veya kapasitesi dolduğunda, başka bir yol dener. Bu işlem, artık su gönderilebilecek bir yol kalmayana kadar devam eder.
Bilgi kartları
Mini test
S1.Ford-Fulkerson algoritması hangi tür problemlerin çözümünde kullanılır?
S2.Bir artırılmış yol bulunduğunda ne yapılır?
S3.Ford-Fulkerson algoritmasının sonlanma garantisi hangi durumda vardır?
Sık yapılan hatalar
Her zaman en uzun yolu kullanarak akışı artırmak en iyisidir. — Doğrusu: Herhangi bir artırılmış yol bulunabilir; en kısa yol (Edmonds-Karp) veya en uzun yol seçimi algoritmanın verimliliğini etkiler ancak temel prensip herhangi bir artırılmış yolu kullanmaktır.
Bir kenarın kapasitesi dolduğunda, o kenar grafikten tamamen çıkarılır. — Doğrusu: Bir kenarın kapasitesi dolduğunda, artık kapasite grafiğinde o yönde akış yapılamaz, ancak ters yönde hala akış potansiyeli olabilir (artık kapasite grafiği güncellenir).
Sıkça sorulan sorular
Ford-Fulkerson algoritması neden önemlidir?
Ağ akışı problemlerinin temelini oluşturur ve birçok gerçek dünya uygulamasında (örneğin, trafik akışı, kaynak tahsisi, ağ bant genişliği yönetimi) kullanılır.
Ford-Fulkerson'ın karmaşıklığı nedir?
Temel Ford-Fulkerson'ın karmaşıklığı, kapasite değerlerine bağlıdır. Edmonds-Karp varyantı (BFS ile) O(VE^2) karmaşıklığına sahiptir, burada V düğüm sayısı ve E kenar sayısıdır.
Algoritma sonsuz döngüye girebilir mi?
Tam sayı kapasitelerle sonsuz döngüye girmez. Ancak rasyonel veya reel sayılarla, artırılmış yollar akıllıca seçilmezse teorik olarak sonsuz döngüye girebilir, ancak pratikte bu nadiren olur.