Examkin

Question

Difficulty: HardMaksimum Akış Problemi

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?

  1. A
    18
  2. B
    20
  3. 24Answer
  4. D
    27
  5. E
    30

Answer

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.

Step-by-Step Solution

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.

Key Concept

Maksimum Akış Problemi ve Ford-Fulkerson Algoritması / Min-Cut Teoremi
Rate this question

Topics

Maksimum Akış Problemi

More questions from this topic