Maksimum Akış Problemi

2 questions

Bir afet yönetimi planlamasında, deprem riski yüksek olan bir bölgeden ( $1$ numaralı düğüm), güvenli toplanma alanına ( $6$ 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 \to 2$ : $18$
- $1 \to 3$ : $12$
- $2 \to 4$ : $8$
- $2 \to 5$ : $6$
- $3 \to 2$ : $4$
- $3 \to 5$ : $10$
- $4 \to 6$ : $15$
- $5 \to 4$ : $5$
- $5 \to 6$ : $12$

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

Show answer & explanation

Answer: 24

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 \to 4

(kapasite: 8),

2 \to 5

(kapasite: 6) ve

3 \to 5

(kapasite: 10) yollarıdır. Toplam darboğaz (min-cut)

8 + 6 + 10 = 24

birim olduğundan maksimum tahliye edilebilir araç sayısı 24 bindir.

Step-by-Step Solution

Ford-Fulkerson algoritması kullanılarak artan yollar üzerinden akış atanır. İlk olarak en yüksek kapasiteli yol olan

1 \to 2 \to 4 \to 6

yolu seçilir.

Bu yolun darboğaz kapasitesi

\min(18, 8, 15) = 8

birimdir. Akış atandığında kalan kapasiteler:

(1 \to 2): 10

(2 \to 4): 0

(4 \to 6): 7

olur.

Maksimum akışa ulaşmak için öncelikle kapasitesi tükenmemiş geçerli yollar bulunmalıdır.

İkinci bir yol olarak

1 \to 3 \to 5 \to 6

yolu değerlendirilir.

Bu yolun darboğaz kapasitesi

\min(12, 10, 12) = 10

birimdir. Akış atandığında kalan kapasiteler:

(1 \to 3): 2

(3 \to 5): 0

(5 \to 6): 2

olur.

Diğer bağımsız rotalar üzerinden akış artırılmaya devam edilir.

Yeni bir artan yol olan

1 \to 2 \to 5 \to 6

yolu üzerinden akış geçirilir.

Kalan kapasitelere göre bu yolun darboğazı

\min(10, 6, 2) = 2

birimdir. Kalan kapasiteler:

(1 \to 2): 8

(2 \to 5): 4

(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.

Son olarak, halen kapasitesi bulunan

1 \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

birimdir. Toplam akış:

8 + 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.

Minimum Kesit (Min-Cut) teoremi ile sağlama yapılır.

Düğümleri

S = \{1, 2, 3\}

T = \{4, 5, 6\}

olarak iki kümeye böldüğümüzde,

S

'den

T

'ye giden yolların kapasiteleri toplamı:

C(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

Question 2Question →

Toprak Mahsulleri Ofisi (TMO), İç Anadolu Bölgesi'ndeki ana toplama merkezinden ( $K$ ) limana ( $L$ ) tren yoluyla buğday taşımaktadır. Ağ üzerinde bölgesel aktarma istasyonları ( $A$ ve $B$ ) ile liman ardalanı dağıtım merkezleri ( $C$ ve $D$ ) 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 \to A$ : $15$
- $K \to B$ : $10$
- $A \to B$ : $2$
- $A \to C$ : $12$
- $B \to C$ : $4$
- $B \to D$ : $9$
- $C \to D$ : $3$
- $C \to L$ : $14$
- $D \to L$ : $8$

Buna göre, şebekede başlangıç ( $K$ ) düğümünden bitiş ( $L$ ) 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?

20 bin ton;

A \to C

D \to L

22 bin ton;

C \to L

D \to L

24 bin ton;

K \to B

A \to B

A \to C

25 bin ton;

K \to A

K \to B

22 bin ton;

K \to A

B \to C

D \to L

Show answer & explanation

Answer: 22 bin ton; $C \to L$ ve $D \to L$

Answer

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 \to L

D \to L

Verilen şebekede maksimum akış 22 bin tondur. Başlangıçtan hedefe ulaşılabilecek alternatif yollar (

K\to A\to C\to L

K\to B\to D\to L

K\to A\to B\to C\to L

) kullanıldığında toplam 22 birimlik bir kapasite tüketilir. Limana (

L

) giden son hatlar olan

C \to L

(14 birim) ve

D \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.

Step-by-Step Solution

K \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 \to A

: 3,

A \to C

: 0,

C \to L

: 2.

Maksimum akış algoritmalarında (Ford-Fulkerson) önce yüksek kapasiteli direkt yollar tercih edilerek başlangıç akışı sağlanır.

K \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 \to B

: 2,

B \to D

: 1,

D \to L

: 0. Toplam akış 20 birime ulaşır.

Başka bir bağımsız yol üzerinden sisteme akış eklenir.

Artık (residual) kapasiteleri kullanarak alternatif bir çapraz yol (

K \to A \to B \to C \to L

) arama

Kalan kapasiteler:

K \to A

: 3,

A \to B

: 2,

B \to C

: 4,

C \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.

Minimum kesme (darboğaz) kontrolü yapma

L düğümüne giren tüm hatların kapasiteleri tamamen dolmuştur (

C \to L

: 14 ve

D \to L

: 8).

14 + 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 (

L

) ulaşan hatların toplam kapasitesinin (22) tamamen tükenmiş olmasıdır.

Key Concept

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

Maksimum Akış Problemi

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes