Examkin

Soru

Zorluk: ZorMaksimum Akış Problemi

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?

  1. A
    20 bin ton; A→CA \to C ve D→LD \to L
  2. 22 bin ton; C→LC \to L ve D→LD \to LCevap
  3. C
    24 bin ton; K→BK \to B, A→BA \to B ve A→CA \to C
  4. D
    25 bin ton; K→AK \to A ve K→BK \to B
  5. E
    22 bin ton; K→AK \to A, B→CB \to C 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
Bu soruyu puanla

Konular

Maksimum Akış Problemi

Bu konudan daha fazla soru