Examkin

Maksimum Akış Problemi

2 soru

Soru 1Soru →

Bir afet yönetimi planlamasında, deprem riski yüksek olan bir bölgeden (11 numaralı düğüm), güvenli toplanma alanına (66 numaralı düğüm) vatandaşların tahliyesi için yönlü bir karayolu ağı kullanılacaktır. Ağ üzerindeki düğümler kavşakları, oklar ise tek yönlü yolları temsil etmektedir.

Yollar ve maksimum taşıma kapasiteleri (saatte bin araç) şu şekildedir:
- 1→21 \to 2: 1818
- 1→31 \to 3: 1212
- 2→42 \to 4: 88
- 2→52 \to 5: 66
- 3→23 \to 2: 44
- 3→53 \to 5: 1010
- 4→64 \to 6: 1515
- 5→45 \to 4: 55
- 5→65 \to 6: 1212

Buna göre, bu ulaşım ağı kullanılarak riskli bölgeden (11) güvenli toplanma alanına (66) saatte maksimum kaç bin araç tahliye edilebilir?

Cevabı ve açıklamayı göster

Cevap: 24

Cevap

Maksimum tahliye kapasitesi saatte 24 bin araçtır.
Maksimum akış problemi çözülürken, başlangıç düğümünden hedef düğüme kadar artan yollar aranır veya ağın kapasitesini sınırlayan 'minimum kesit' bulunur. Bu soruda, düğümleri {1, 2, 3} ve {4, 5, 6} şeklinde iki ayrı kümeye ayıran kesit, ağdaki akışı sınırlar. Bu iki küme arasındaki tek yönlü geçişler 2→42 \to 4 (kapasite: 8), 2→52 \to 5 (kapasite: 6) ve 3→53 \to 5 (kapasite: 10) yollarıdır. Toplam darboğaz (min-cut) 8+6+10=248 + 6 + 10 = 24 birim olduğundan maksimum tahliye edilebilir araç sayısı 24 bindir.

Adım Adım Çözüm

1
Ford-Fulkerson algoritması kullanılarak artan yollar üzerinden akış atanır. İlk olarak en yüksek kapasiteli yol olan 1→2→4→61 \to 2 \to 4 \to 6 yolu seçilir.
Bu yolun darboğaz kapasitesi min⁡(18,8,15)=8\min(18, 8, 15) = 8 birimdir. Akış atandığında kalan kapasiteler: (1→2):10(1 \to 2): 10, (2→4):0(2 \to 4): 0, (4→6):7(4 \to 6): 7 olur.
Maksimum akışa ulaşmak için öncelikle kapasitesi tükenmemiş geçerli yollar bulunmalıdır.
2
İkinci bir yol olarak 1→3→5→61 \to 3 \to 5 \to 6 yolu değerlendirilir.
Bu yolun darboğaz kapasitesi min⁡(12,10,12)=10\min(12, 10, 12) = 10 birimdir. Akış atandığında kalan kapasiteler: (1→3):2(1 \to 3): 2, (3→5):0(3 \to 5): 0, (5→6):2(5 \to 6): 2 olur.
Diğer bağımsız rotalar üzerinden akış artırılmaya devam edilir.
3
Yeni bir artan yol olan 1→2→5→61 \to 2 \to 5 \to 6 yolu üzerinden akış geçirilir.
Kalan kapasitelere göre bu yolun darboğazı min⁡(10,6,2)=2\min(10, 6, 2) = 2 birimdir. Kalan kapasiteler: (1→2):8(1 \to 2): 8, (2→5):4(2 \to 5): 4, (5→6):0(5 \to 6): 0 olur.
Ana yollar dolduğunda ara bağlantılar ve kalan kapasiteler kullanılarak akışın sınırları zorlanır.
4
Son olarak, halen kapasitesi bulunan 1→2→5→4→61 \to 2 \to 5 \to 4 \to 6 çapraz yolu kullanılır.
Bu yolun kalan kapasiteler üzerinden darboğazı min⁡(8,4,5,7)=4\min(8, 4, 5, 7) = 4 birimdir. Toplam akış: 8+10+2+4=248 + 10 + 2 + 4 = 24 birim bulunur.
Hedefe ulaşan başka bir artan yol kalmadığı için ulaşılan toplam değer ağın maksimum akışıdır.
5
Minimum Kesit (Min-Cut) teoremi ile sağlama yapılır.
Düğümleri S={1,2,3}S = \{1, 2, 3\} ve T={4,5,6}T = \{4, 5, 6\} olarak iki kümeye böldüğümüzde, SS'den TT'ye giden yolların kapasiteleri toplamı: C(2→4)+C(2→5)+C(3→5)=8+6+10=24C(2\to4) + C(2\to5) + C(3\to5) = 8 + 6 + 10 = 24 birimdir.
Max-Flow Min-Cut teoremine göre, herhangi bir şebekedeki maksimum akış, o şebekenin minimum kesit kapasitesine eşittir.

Anahtar Kavram

Maksimum Akış Problemi ve Ford-Fulkerson Algoritması / Min-Cut Teoremi
Soru 2Soru →

Toprak Mahsulleri Ofisi (TMO), İç Anadolu Bölgesi'ndeki ana toplama merkezinden (KK) limana (LL) tren yoluyla buğday taşımaktadır. Ağ üzerinde bölgesel aktarma istasyonları (AA ve BB) ile liman ardalanı dağıtım merkezleri (CC ve DD) bulunmaktadır.

Düğümler arasındaki tek yönlü demiryolu hatlarının haftalık maksimum taşıma kapasiteleri (bin ton) aşağıda verilmiştir:
- K→AK \to A: 1515
- K→BK \to B: 1010
- A→BA \to B: 22
- A→CA \to C: 1212
- B→CB \to C: 44
- B→DB \to D: 99
- C→DC \to D: 33
- C→LC \to L: 1414
- D→LD \to L: 88

Buna göre, şebekede başlangıç (KK) düğümünden bitiş (LL) düğümüne taşınabilecek maksimum buğday miktarı ve sistemin taşıma kapasitesini doğrudan sınırlayan darboğaz hatları (minimum kesme) aşağıdakilerin hangisinde sırasıyla doğru verilmiştir?

Cevabı ve açıklamayı göster

Cevap: 22 bin ton; C→LC \to L ve D→LD \to L

Cevap

Sistemdeki maksimum akış 22 bin tondur ve ağı sınırlayan darboğaz hatları C'den L'ye ve D'den L'ye giden hatlardır (C→LC \to L ve D→LD \to L).
Verilen şebekede maksimum akış 22 bin tondur. Başlangıçtan hedefe ulaşılabilecek alternatif yollar (K→A→C→LK\to A\to C\to L, K→B→D→LK\to B\to D\to L ve K→A→B→C→LK\to A\to B\to C\to L) kullanıldığında toplam 22 birimlik bir kapasite tüketilir. Limana (LL) giden son hatlar olan C→LC \to L (14 birim) ve D→LD \to L (8 birim) hatları tamamen dolarak toplam 22 birimlik kapasite kısıtına ulaşır. Max-Akış Min-Kesme (Max-Flow Min-Cut) teoremine göre, ağın darboğazı, toplam kapasiteleri 22 olan bu iki hattın oluşturduğu kesmedir.

Adım Adım Çözüm

1
K→A→C→LK \to A \to C \to L yolu üzerinden maksimum olası akışı gönderme
Kapasiteler (15, 12, 14) arasından minimum olan 12 birim akış gönderilir. Kalan kapasiteler: K→AK \to A: 3, A→CA \to C: 0, C→LC \to L: 2.
Maksimum akış algoritmalarında (Ford-Fulkerson) önce yüksek kapasiteli direkt yollar tercih edilerek başlangıç akışı sağlanır.
2
K→B→D→LK \to B \to D \to L yolu üzerinden maksimum olası akışı gönderme
Kapasiteler (10, 9, 8) arasından minimum olan 8 birim akış gönderilir. Kalan kapasiteler: K→BK \to B: 2, B→DB \to D: 1, D→LD \to L: 0. Toplam akış 20 birime ulaşır.
Başka bir bağımsız yol üzerinden sisteme akış eklenir.
3
Artık (residual) kapasiteleri kullanarak alternatif bir çapraz yol (K→A→B→C→LK \to A \to B \to C \to L) arama
Kalan kapasiteler: K→AK \to A: 3, A→BA \to B: 2, B→CB \to C: 4, C→LC \to L: 2. Minimum kapasite 2 birimdir. Bu yoldan 2 birim akış gönderilir. Toplam akış: 20 + 2 = 22 birim olur.
Ana yollar dolduğunda, sistemdeki atıl kapasiteler çapraz yollar üzerinden değerlendirilerek akış maksimize edilir.
4
Minimum kesme (darboğaz) kontrolü yapma
L düğümüne giren tüm hatların kapasiteleri tamamen dolmuştur (C→LC \to L: 14 ve D→LD \to L: 8). 14+8=2214 + 8 = 22. Max-Akış Min-Kesme teoremine göre kesme kapasitesi maksimum akışa eşittir.
Sistemin daha fazla akış taşıyamamasının temel nedeni, hedef düğüme (LL) ulaşan hatların toplam kapasitesinin (22) tamamen tükenmiş olmasıdır.

Anahtar Kavram

Maksimum Akış ve Minimum Kesme (Max-Flow Min-Cut) Teoremi