Kelompok IV

1. Muh. Alfiansyah 161050701024

2. Nurqiyamah Hamid 1610507010XX

3. Asmaun 1610507010XX

Sebuah Graph berarah D adalah suatu pasangan berurutan dari dua himpunan V(D) yaitu himpunan berhingga

tak kosong yang anggota-anggotanya disebut titik dan 𝛤(D) yaitu himpunan berhingga (boleh kosong) yang

anggota-anggotanya disebut busur sedemikian sehingga setiap busur merupakan pasangan berurutan

dari dua titik di V(D).

Contoh:

Graph berarah 𝐿 = 𝑉 𝐿 , 𝛤(𝐿)

𝐿 = ( 𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5 , { 𝑣1, 𝑣2 , 𝑣2, 𝑣3 , 𝑣2, 𝑣5 , 𝑣3, 𝑣4 , 𝑣4, 𝑣5 , 𝑣5, 𝑣1 , 𝑣5, 𝑣3 }

JALANKonsep: JEJAK LINTASAN SIRKUIT SIKEL

Istilah sisi pada graph tak berarah diganti dengan istilah busur pada graph berarah

𝑣1

𝑣2

𝑣3

𝑣4𝑣5𝑃

𝑣1

𝑣2

𝑣3

𝑣4𝑣5𝑄

𝐶4 = (𝑣2, 𝑣3, 𝑣4, 𝑣5, 𝑣2)

𝑣1

𝑣2

𝑣3

𝑣4𝑣5 𝑅

𝐶4 adalah sikel berarah dengan

panjang 4 pada graph berarah R.

𝐶5 = (𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5, 𝑣1)

𝐶5 adalah sikel berarah dengan

panjang 5 pada graph berarah P.

Sikel Hamilton adalah sebuah

sikel yang memuat semua

titik sebuah graph.

Graph Hamilton adalah

graph yang memuat sikel

hamilton.

Konsep keterhubungan

pada graph berarah

Terhubung Lemah jika graph

dasarnya terhubung.

Terhubung Kuat jika untuk setiap dua

titik 𝑣𝑖 dan 𝑣𝑗 di suatu graph berarah

terdapat lintasan berarah dari 𝑣𝑖 ke 𝑣𝑗.

Misalkan D sebuah graph berarah dan 𝑣 ∈ 𝑉 𝐷

Derajat keluar titik v, dilambangkan dengan od(v)

adalah banayaknya busur pada graph berarah D yang

keluar dari titik v.

Derajat masuk titik v, dilambangkan dengan id(v)

adalah banayaknya busur pada graph berarah D yang

menuju ke titik v.

𝑣1

𝑣2

𝑣3𝑣4

𝑣5

𝐷

𝑜𝑑(𝑣1) = 2 𝑖𝑑(𝑣1) = 2

𝑜𝑑(𝑣2) = 1 𝑖𝑑(𝑣2) = 1

𝑜𝑑(𝑣3) = 1 𝑖𝑑(𝑣3) = 1

𝑜𝑑(𝑣4) = 2 𝑖𝑑(𝑣2) = 2

𝑜𝑑(𝑣5) = 1 𝑖𝑑(𝑣5) = 1

TEOREMA 10.1:

Jika 𝐷 = (𝑉 𝐷 , 𝛤 𝐷 ) graph berarah maka

𝑣∈𝑉(𝐷)

𝑖𝑑 𝑣 = 𝛤 𝐷 =

𝑣∈𝑉(𝐷)

𝑜𝑑 𝑣

𝑣1

𝑣2

𝑣5

𝑣3

𝑣4

𝑣7𝑣6 𝑄

Misalkan Q sebuah graph berarah terhubung

lemah. Sebuah sirkuit berarah yang memuat semua

busur Q disebut sirkuit euler berarah.

Jika D memuat sirkuit euler berarah maka D

disebut graph euler.

TEOREMA 10.2:

Misalkan graph-berarah 𝐷 terhubung lemah

dengan paling sedikit satu busur. 𝐷 graph

euler jika dan hanya jika 𝑖𝑑 𝑣 = 𝑜𝑑 𝑣

∀ 𝑣 ∈ 𝑉 𝐷 .

𝑣1

𝑣2

𝑣3𝑣4

𝑣5

𝐷

𝑣1

𝑣2

𝑣3

𝑣4𝑣5𝑃

Misalkan G sebuah graph (tak berarah). Jika dibentuk graph berarah D dari graph G dengan cara mengganti

setiap sisi G dengan sebuah busur atau dengan cara memberi “arah” pada setiap sisi G, maka graph berarah D

disebut sebuah orientasi G.

𝑣1

𝑣2

𝑣5𝑣3

𝑣4

𝑣6

𝐺

𝑣1

𝑣2

𝑣5𝑣3

𝑣4

𝑣6

𝐷1

𝑣1

𝑣2

𝑣5𝑣3

𝑣4

𝑣6

𝐷2

𝐷1 dan 𝐷2 dua orientasi graph G yang berbeda

Sebuah orientasi dari graph komplit disebut graph turnamen. Jadi turnamen adalah graph berarah tanpa gelung

sedemikian hingga setiap dua titik yang berbeda 𝑢 dan 𝑣 dihubungkan oleh busur (𝑢, 𝑣) saja atau busur (𝑣, 𝑢)

saja.

Hanya ada 2 turnamen dengan

tiga titik yang non-isomorfik dan

hanya ada 4 turnamen dengan

empat titik yang non-isomorfik.

Contoh:

Suatu pertandingan sepak bola diikuti oleh enam tim yakni A, B, C, D, E dan F, dalam pertandingan ini setiap

dua tim harus bertanding tepat satu kali dan tidak boleh ada seri. Hasil pertandingan yang diperoleh yakni A

menang melawan B dan D, B menang melawan C, D dan F, C hanya menang melawan A, D menang melawan E

dan F, E hanya kalah melawan D serta F menang melawan A dan C.

𝐹 𝐸

𝐷

𝐶𝐵

𝐴

TEOREMA 10.3:

Misalkan T sebuah turnamen dan 𝑢 adalah

sebuah titik di T dengan 𝑜𝑑(𝑢) maksimum. Maka

setiap titik 𝑣 di T, terdapat lintasan berarah dari 𝑢

ke 𝑣 di T dengan panjang maksimum dua.

Akan dibuat sistem alur lalulintas satu arah sedemikian sehingga dari

setiap tempat (persimpangan) seorang pengendara dapat mengakses

tempat yang lain lewat sistem yang dibuat.

Dalam konteks teori graph masalah di atas dapat dirumuskan menjadi

sebagai berikut: diberikan sebuah graph (tak berarah) G. Adakah sebuah

orientasi G merupakan graph beraharah terhubung kuat?

Permasalahan

Solusi

Sebuah graph G dikatakan terorientasi jika terdapat sebuah orientasi G yang terhubung kuat.

TEOREMA 10.4:

Sebuah graph G terorientasi jika dan hanya jika graph G terhubung dan tidak memiliki sisi pemutus.

ALGORITMA HOPCROFT DAN TARJAN

Input : Graph G terhubung dan tidak memiliki sisi pemutus.

Step 1 : Pilih 𝑣 ∈ 𝑉(𝐺), dan label titik 𝑣 dengan λ 𝑣 = 1. Tulis 𝐿 = {𝑣} dan 𝑈 = 𝑉 𝐺 − {𝑣}. (L adalah

himpunan titik-titik terlabel. U adalah himpunan titik-titik tak terlabel). Tulis 𝛤 = ∅ (adalah himpunan

busur yang diperoleh dari pemberian orientasi pada sisi graph G).

Step 2 : Pilih titik 𝑥 di L dengan label maksimum dan berhubungan langsung ke sebuah titik 𝑦 di U.

Lebel titik 𝑦 dengan λ 𝑦 = λ 𝑥 + 1. Ganti L dengan 𝐿 ∪ {𝑦} dan 𝑈 dengan 𝑈 − {𝑦}. Beri orientasi

(arah sis 𝑥𝑦 dari titik 𝑥 ke titik y). Ganti 𝛤 dengan 𝛤 ∪ 𝑥, 𝑦 .

Step 3 : Jika 𝐿 ≠ 𝑉(𝐺) kembali ke step 2.

Step 4 : 𝐿 = 𝑉 𝐺 (Dalam hal ini, semua titik 𝐺 telah dilabel; dan graph dasar dari graph berarah yang

dibangun oleh semua busur 𝛤 merupakan sebuah pohon rentang dari graph 𝐺. Lebih jauh, sisi-sisi 𝐺yang belum diberi orientasi menghubungkan dua titik dengan nilai label berbeda).

Untuk setiap sisi 𝑤𝑧 pada graph 𝐺 yang belum diorientasi, jika λ 𝑤 > λ 𝑧 , maka beri orientasi sisi

𝑤𝑧 dari titik 𝑤 ke titik 𝑧.STOP: “Diperoleh sebuah orientasi graph 𝐺”.

Contoh: (Soal Latihan Nomor 10)

Gunakan algoritma Hopcroft dan Tarjan untuk memberi orientasi

pada setiap sisi graph G berikut agar diperoleh graph berarah

terhubung kuat.

𝑣1

𝑣2

𝑣5

𝑣3

𝑣4

𝑣6

Sebuah Network 𝑵 = (𝑽 𝑵 , 𝛤 𝑵 ) adalah sebuah graph berarah sederhana terhubung lemah yang setiap

busurnya dikaitkan dengan bilangan real non-negatif.

Selanjutnya, bilangan real non-negatif yang dikaitkan pada busur (𝑣𝑖 , 𝑣𝑗) atau disingkat 𝑖, 𝑗 pada Network

N disebut Kapasitas Busur (𝑣𝑖 , 𝑣𝑗) dan dilambangkan dengan c(𝑣𝑖 , 𝑣𝑗) atau c 𝑖, 𝑗

Sebuah titik 𝑠 di network 𝑁 disebut titik sumber

jika 𝑖𝑑 𝑠 = 0.

Sebuah titik 𝑡 di network 𝑁 disebut titik tujuan jika

𝑜𝑑 𝑡 = 0.

Sedangkan, titik yang lain disebut titik antara.

𝑣1 𝑣2

𝑣5

𝑣3

𝑣4𝑣6

Misalkan 𝑋 dan 𝑌 dua himpunan bagian 𝑉(𝑁) padan network 𝑁.

Himpunan semua busur 𝑁 yang berawal di 𝑋 dan berujung di 𝑌 dilambangkan dengan 𝐵 𝑋, 𝑌 .

Total kapasitas semua busur di 𝐵(𝑋, 𝑌) dilambangkan dnegan 𝑐(𝑋, 𝑌). Dengan demikian: 𝑐 𝑋, 𝑌 =

𝑎∈𝐵(𝑋,𝑌)

𝑐(𝑎)

Misalnya dari graph 𝐺:

Jika 𝑋 = {𝑣𝑠, 𝑣1, 𝑣3} dan 𝑌 = 𝑣2, 𝑣4, 𝑣5, 𝑣6, 𝑣𝑡

Maka 𝐵 𝑋, 𝑌 = { 𝑠, 6 , 1,2 , 1,5 , 3, 𝑡 }

Dan 𝑐 𝑋, 𝑌 = 𝑐 𝑆, 6 + 𝑐 1,2 + 𝑐 1,5 + 𝑐 3, 𝑡

= 5 + 8 + 5 + 5 = 23

𝑣1 𝑣2

𝑣5

𝑣3

𝑣4𝑣6

𝐺

𝑣 𝑣

Misalkan 𝑁 sebuah network dengan titik sumber 𝑠 dan titik tujuan 𝑡.

Misalkan himpunan 𝑋 adalah himpunan bagian tak kosong dari 𝑉(𝑁) dan 𝑋′ = 𝑉 𝑁 − 𝑋.

Jika 𝑠 ∈ 𝑋 dan 𝑡 ∈ 𝑋′ maka himpunan busur 𝐵(𝑋, 𝑋′) disebut sebuah pemutus (s,t) dari network 𝑁.

Misalkan 𝐴 adalah himpunan titik antara pada network 𝑁 dan 𝐴′ adalah sebuah himpunan bagian 𝐴.

Jika 𝑋 = {𝑡} ∪ 𝐴 maka 𝐵(𝑋, 𝑋′) sebuah pemutus (𝑠, 𝑡) pada network 𝑁.

Jadi banyaknya pemutus (𝑠, 𝑡) pada network 𝑁 sama dengan banyaknya himpunan bagian dari

himpunan A yaitu 2𝑛 dengan 𝑛 = 𝐴 .

Disebut demikian, karena penghapusan semua busur 𝐵(𝑋, 𝑋′) dari 𝑁, memutus semua lintasan

berarah dari titik 𝑠 ke titik 𝑡 pada network 𝑁.

𝑣1

𝑣2

𝑣𝑡𝑣𝑠

3

6

5

2

4𝑁

Graph 𝑁 diketahui memiliki dua titik antara

Sehingga terdapat 22 = 4 pemutus (s,t) pada 𝑁

𝐵 = 𝑣𝑠 , {𝑣1, 𝑣2, 𝑣𝑡} = 𝑠, 1 , (𝑠, 2)

𝐵 = 𝑣𝑠, 𝑣1 , {𝑣2, 𝑣𝑡} = 𝑠, 2 , 1,2 , (1, 𝑡)

𝐵 = 𝑣𝑠,𝑣2 , {𝑣1, 𝑣𝑡} = 𝑠, 1 , (2, 𝑡)

𝐵 = 𝑣𝑠, 𝑣1, 𝑣2 , {𝑣𝑡} = 1, 𝑡 , (2, 𝑡)

Setiap pemutus (𝑠, 𝑡) pada network 𝑁 mempunyai kapasitas.

Pemutus (𝑠, 𝑡) yang mempunyai kapasitas terkecil disebut

pemutus (𝒔, 𝒕) minimum

Kapasitas dari keempat pemutus tersebut adalah:

c 𝑣𝑠 , {𝑣1, 𝑣2, 𝑣𝑡} = 𝑐 𝑠, 1 + 𝑐 𝑠, 2 = 3 + 4 = 7

c 𝑣𝑠, 𝑣1 , {𝑣2, 𝑣𝑡} = 𝑐 𝑠, 2 + 𝑐 1,2 + 𝑐 1, 𝑡 = 4 + 2 + 5 = 11

𝑐 𝑣𝑠,𝑣2 , {𝑣1, 𝑣𝑡} = 𝑠, 1 + 2, 𝑡 = 3 + 6 = 9

𝑐 𝑣𝑠, 𝑣1, 𝑣2 , {𝑣𝑡} = 1, 𝑡 + (2, 𝑡) = 5 + 6 = 11

Tampak bahwa 𝐵 = 𝑣𝑠 , {𝑣1, 𝑣2, 𝑣𝑡} = 𝑠, 1 , (𝑠, 2)

Dengan kapasitas 7 merupakan sebuah pemutus (𝑠, 𝑡)

minimum pada network 𝑁.

Misalkan 𝑁 sebuah network dengan titik sumber 𝑠 dan titik tujuan 𝑡.

Jika 𝑣 adalah sebuah titik 𝑁, maka himpunan semua busur 𝑁 yang keluar dari titik 𝑣 (meninggalkan titik 𝑣)

dilambangkan dengan 𝑶(𝒗) dan himpunan semua busur 𝑁 yang menuju ke titik 𝑣 dilambangkan dengan 𝑰(𝒗).

𝑣5 𝑣4

𝑣3

𝑣2𝑣1

𝑣𝑡𝑣𝑠

𝐹

20

15

21

9

42

24

104 10

Untuk titik 𝑣𝑠

𝑂 𝑣𝑠 = 𝑂 𝑠 = {(𝑣𝑠, 𝑣1), (𝑣𝑠, 𝑣5)}={(s,1),(s,5)}

𝐼(𝑣𝑠) = 𝐼 𝑠 = { }

Untuk titik 𝑣3

𝑂 𝑣3 = 𝑂 3 = {(𝑣3, 𝑣2), (𝑣3, 𝑣4)}={(3,2),(3,4)}

𝐼(𝑣3) = 𝐼 3 = {(𝑣1, 𝑣3), (𝑣5, 𝑣3)}={(1,3),(5,3)}

Sebuah flow di network 𝑁 dari titik sumber 𝑠 ke titik

tujuan 𝑡 adalah suatu fungsi 𝑓 yang memetakan

setiap busur (𝑖, 𝑗) di 𝑁 dengan sebuah bilangan non-

negatif yang memenuhi syarat-syarat berikut:

• 0 ≤ 𝑓 𝑖, 𝑗 ≤ 𝑐 𝑖, 𝑗 ∀(𝑖, 𝑗) ∈ 𝛤(𝑁) (disebut

“kapasitas pembatas”).

• (𝑖,𝑗)∈𝑂(𝑠) 𝑓 𝑖, 𝑗 = (𝑖,𝑗)∈𝐼(𝑡) 𝑓 𝑖, 𝑗 (disebut

“nilai flow f”)

• (𝑖,𝑗)∈𝑂(𝑥) 𝑓 𝑖, 𝑗 = (𝑖,𝑗)∈𝐼(𝑥) 𝑓 𝑖, 𝑗 ∀𝑥 ∈

𝑉 𝑁 − {𝑠, 𝑡} (disebut “konservasi flow”)

𝑣5 𝑣4

𝑣3

𝑣2𝑣1

𝑣𝑡𝑣𝑠

Flow 𝑭 pada 𝑵 dengan nilai 12

20 : 7

15 : 5

21 : 2

9 : 3

8 : 52 : 1

24 : 3

10 : 9

4 : 2 10 : 6

𝑣5 𝑣4

𝑣3

𝑣2𝑣1

𝑣𝑡𝑣𝑠

Flow 𝑭 pada 𝑵 dengan nilai 27

20 : 20

15 : 7

21 : 16

9 : 3

8 : 42 : 2

24 : 18

10 : 9

4 : 4 10 : 6

𝑣5 𝑣4

𝑣3

𝑣2𝑣1

𝑣𝑡𝑣𝑠

Flow 𝑭 pada 𝑵 dengan nilai 12

20 : 7

15 : 5

21 : 2

9 : 3

8 : 52 : 1

24 : 3

10 : 9

4 : 2 10 : 6

Jika 𝑋 = 𝑣𝑠, 𝑣1 = 𝑠, 1 dan 𝑋′ = {𝑣2, 𝑣3, 𝑣4, 𝑣5, 𝑣𝑡} = {2,3,4,5, 𝑡}

Maka 𝐵 = 𝑋, 𝑋′ = { 𝑠, 5 , 1,2 , 1,3 ) sebuah pemutus (𝑠, 𝑡) di N

Kapasitas 𝑐 𝑋, 𝑋′ = 𝑐 𝑠, 5 + 𝑐 1,2 + 𝑐 1,3 = 15 + 21+4=30

Terlihat bahwa nilai flow f yaitu 12, tidak melebih kapasitas

pemutus 𝒔, 𝒕 𝑩(𝑿, 𝑿′).

TEOREMA 10.5:

Misalkan 𝑁 sebuah network dengan titik sumber 𝑠 dan titik tujuan 𝑡. Jika 𝑓 adalah sebuah flow

dan 𝑠 ke 𝑡 pada 𝑁 dengan nilai 𝑓𝑠,𝑡 dan 𝐵(𝑋, 𝑋′) sebuah pemutus 𝑠, 𝑡 pada 𝑁, maka 𝑓𝑠,𝑡 =

𝑓 𝑋, 𝑋′ − 𝑓(𝑋′, 𝑋) ≤ 𝑐(𝑋, 𝑋′).

Teorema 10.5 menjamin bahwa nilai sebarang flow

pada suatu network 𝑁 dari titik sumber 𝑠 ke titik tujuan

𝑡 tidak akan melebihi kapasitas sebarang pemutus (𝑠, 𝑡)

pada 𝑁.

Jadi, jika terdapat suatu flow 𝑓 di 𝑁 yang nilainya sama

dengan kapasitas suatu pemutus 𝑠, 𝑡 , maka flow f

tersebut adalah flow maksimum dan pemutus (𝑠, 𝑡)

tersebut adalah sebuah pemutus (𝑠, 𝑡) minimum. Jadi

flow 𝑓 bernilai 𝑓𝑠,𝑡 dari titik sumber s ke tujuan 𝑡 pada

network 𝑁 dikatakan Flow Maksimum jika

𝑓𝑠,𝑡 = 𝑚𝑖𝑛{𝑐(𝑋, 𝑋1)/𝐵 𝑋, 𝑋1 suatu pemutus (𝑠, 𝑡)

pada network 𝑁}.

𝑣4

𝑣3

𝑣2

𝑣1

𝑣𝑡𝑣𝑠 3 : 0

5 : 4

6 : 5

4 : 1

4 : 4

2 : 2

8 : 7

3 : 23 : 3

Flow 𝑓2

Perhatikan flow 𝑓2 yang bernilai 9.

Jika 𝑋 = 𝑠, 2 dan 𝑋1 = {1,3,4, 𝑡},

maka 𝐵 𝑋, 𝑋1 = { 𝑠, 1 , 2,3 , 2,4 } adalah

pemutus (𝑠, 𝑡) pada 𝑁 dengan kapasitas

𝑐 𝑋, 𝑋1 = 𝑐 𝑠, 1 + 𝑐 2,3 + 𝑐 2,4 = 4 + 2 + 3

= 9 = 𝑛𝑖𝑙𝑎𝑖 𝑓𝑙𝑜𝑤𝑓2

Misalkan N sebuah network dan G adalah graph dasar N. Misalkan pada graph G terdapat lintasan 𝑃 =

(𝑣1, 𝑣2, 𝑣3,...,𝑣𝑖 , 𝑣𝑖+1, … , 𝑣𝑛).

Jika (𝑣𝑖 , 𝑣𝑖+1) sebuah busur pada N maka busur tersebut dinamakan busur maju terhadap P.

Sebaliknya jika (𝑣𝑖+1, 𝑣𝑖) sebuah busur pada N maka busur tersebut dinamakan busur balik terhadap P.

𝑣4

𝑣3

𝑣2

𝑣1

𝑣𝑡𝑣𝑠 3 : 0

5 : 4

6 : 5

4 : 1

4 : 4

2 : 2

8 : 7

3 : 2

3 : 3

Flow 𝑓2

Jadi, apakah suatu busur pada N termasuk busur maju atau busur balik, sangat tergantung pada

lintasan P pada graph dasarnya.

Sebagai contoh: misalkan G graph dasar dari network N

pada gambar di samping, maka 𝑃 = (𝑣𝑠, 𝑣2,𝑣1, 𝑣3,𝑣4, 𝑣𝑡)adalah sebuah lintasan (𝑣𝑠, 𝑣𝑡) pada G (perlu dicatat

bahwa P bukan lintasan berarah pada N).

Sehingga terdapat P, busur-busur (𝑣𝑠, 𝑣2) , (𝑣1, 𝑣3) dan

(𝑣4, 𝑣𝑡) merupakan busur-busur maju.

Sementara (𝑣2, 𝑣1) dan (𝑣4, 𝑣3) merupakan busur balik

Misalkan f adalah sebuah flow dari titik sumber s ke titik tujuan t pada network N, dan misalkan G adalah

graph dasar N. Pikirkan sebuah lintasan P pada G. Inkremen sebuah busur a pada N yang berkorespondensi

dengan sebuah sisi P pada G, dilambangkan dengan i(a) dan didefinisikan sebagai berikut:

Jika a busur maju maka 𝑖 𝑎 = 𝑐 𝑎 − 𝑓(𝑎)

Jika a busur balik maka 𝑖 𝑎 = 𝑓(𝑎)

Inkremen lintasan 𝑃 disimbolkan dengan 𝑖(𝑃) didefinisikan sebagai berikut:

𝑖 𝑝 = min{𝑖 𝑎 │𝑎 𝑎𝑑𝑎𝑙𝑎ℎ 𝑏𝑢𝑠𝑢𝑟 𝑁 𝑦𝑎𝑛𝑔 𝑏𝑒𝑟𝑠𝑒𝑠𝑢𝑎𝑖𝑎𝑛 𝑑𝑒𝑛𝑔𝑎𝑛 𝑠𝑖𝑠𝑖 𝑃}

Sebuah lintasan P dengan i(P) positif disebut lintasan augmentasi.

Selanjutnya lintasan augmentasi P dari titik s ke titik tujuan t dinamakan

sebuah lintasan peningkatan. Sebagai contoh perhatikan flow f dari titik

sumber s ke titik tujuan t di network N pada gambar disamping. Pikirkan

lintasan 𝑃 = (𝑣𝑠, 𝑣2,𝑣1, 𝑣3,𝑣4, 𝑣𝑡) .

𝑣4

𝑣3

𝑣2

𝑣1

𝑣𝑡𝑣𝑠 3 : 1

5 : 2

6 : 2

4 : 1

4 : 3

2 : 1

8 : 4

3 : 13 : 2

Flow 𝑓

Lemma 10.6: misalkan f sebuah flow bernilai 𝑓𝑠,𝑡 dari titik sumber s ke titik tujuan t pada network N. Jika

terdapat lintasan P dari titik s ke titik t dengan 𝑖 𝑃 = 𝛿 > 0, didefinisikan fungsi 𝑓1 pada himpunan 𝛤(𝑁)

sebagai berikut: jika a busur maju terhadap P maka 𝑓1 𝑎 = 𝑓 𝑎 + 𝛿 sedangkan jika a busur balik terhadap

P maka 𝑓1 𝑎 = 𝑓 𝑎 − 𝛿, serta𝑓1 𝑎 = 𝑓(𝑎) untuk busur a lainnya. Maka 𝑓1 adalah flow dari titik s ke titik t

pada N dengan nilai 𝑓𝑠,𝑡 + 𝛿

𝑣4

𝑣3

𝑣2

𝑣1

𝑣𝑡𝑣𝑠 3 : 1

5 : 2

6 : 2

4 : 1

4 : 3

2 : 1

8 : 4

3 : 13 : 2

Flow 𝑓𝑣4

𝑣3

𝑣2

𝑣1

𝑣𝑡𝑣𝑠 3 : 0

5 : 3

6 : 3

4 : 0

4 : 3

2 : 1

8 : 4

3 : 23 : 2

Flow 𝑓′

Algoritma Flow Maksimum

Input: Network 𝑁 = (𝑉, 𝐺) dengan titik sumber s dan titik

tujuan t.

Step 1: Misalkan f sebuah flow dari s ke t pada N (Boleh

dimulai dengan flow bernilai nol, yaitu 𝑓 𝑖, 𝑗 = 0∀(𝑖, 𝑗) ∈ 𝐼) dilanjutkan ke routin pelabelan.

Step 2: Routin Pelabelan.

1. label 𝑣𝑠 = (𝑠, +, 휀 𝑠 = ~) titik 𝑣𝑠 telah terlabel dan

belum teramati. (Note: sebuah titik v dikatakan telah

teramati jika semua titik yang dapat dilabel dari titik v

sudah terlabel).

2. Pilih sebarang titik yang terlabel tetapi belum teramati,

misalkan titik tersebut 𝑣𝑥. ∀𝑣𝑦∃ 𝑦, 𝑥 ∈ 𝛤, 𝑣𝑦 belum

berlabel dan 𝑓 𝑦, 𝑥 > 0 maka label 𝑣𝑦 = (𝑥,−, 휀 𝑦 )

dengan 휀 𝑦 = min{휀 𝑥 , 𝑓 𝑦, 𝑥 }. Sekarang titik 𝑣𝑦telah terlabel, tetapi belum teramati. ∀𝑣𝑦∃ 𝑥, 𝑦 ∈

𝛤, 𝑣𝑦 belum berlabel dan c 𝑥, 𝑦 > 𝑓(𝑥, 𝑦) maka

label 𝑣𝑦 = (𝑥, +, 휀 𝑦 ) dengan 휀 𝑦 = min{휀 𝑥 ,

𝑐 𝑥, 𝑦 − 𝑓 𝑥, 𝑦 } . Sekarang titik 𝑣𝑦 telah terlabel,

tetapi belum teramati. Ubahlah label 𝑣𝑥 dengan cara

melingkari tanda + atau -.

3. Ulangi step 2.2 sampai:

a. Titik 𝑣𝑡 terlabel atau

b. Semua titik teralabel telah teramati tetapi titik 𝑣𝑡 tak

terlabel.

a. Jika titik 𝑣𝑡 terlabel, lanjut ke step 3.

b. Jika semua titik terlabel telah teramati tetapi titik 𝑣𝑡 tak

terlabel maka STOP: “flow f adalah flow maksimum pada

network N”.

Step 3: dengan prosedur “balik” tentukan lintasan peningkatan

P dengan i(P) adalah label 𝑣𝑡.Step 4: tingkatkan nilai flow f sebesar label 𝑣𝑡 berdasarkan

lintasan peningkatan-P dengan menggunakan routine

peningkatan.

1. Misal Z=t lanjutkan ke step 4.2.

2. Jika label 𝑣𝑧 = (𝑞,+, 휀 𝑡 ) tingkatkan nilai 𝑓(𝑞, 𝑧) dengan

휀 𝑡 = 𝑖(𝑃) . Jika label 𝑣𝑧 = (𝑞,− , 휀 𝑡 ) turunkan nilai

𝑓(𝑞, 𝑧) dengan 휀 𝑡 = 𝑖(𝑃)3. Jika 𝑞 = 𝑠 hapus semua label. Pada tahap ini diperoleh flow

f baru dengan nilai 𝑖 𝑃 + 𝑛𝑖𝑙𝑎𝑖 𝑓𝑙𝑜𝑤 𝑙𝑎𝑚𝑎. Ganti flow f

dengan flow f yang baru dan kembali ke step 1.

𝑣4

𝑣3

𝑣2

𝑣1

𝑣𝑡𝑣𝑠 3 : 1

5 : 2

6 : 2

4 : 1

4 : 3

2 : 1

8 : 4

3 : 1

3 : 2

Flow 𝑓0

Tentukan flow maksimum dari 𝒇𝟎!

𝑣4

𝑣3

𝑣2

𝑣1

𝑣𝑡𝑣𝑠 3 : 1

5 : 3

6 : 2

4 : 1

4 : 4

2 : 1

8 : 5

3 : 1

3 : 2

Flow 𝑓1

𝑣4

𝑣3

𝑣2

𝑣1

𝑣𝑡𝑣𝑠 3 : 1

5 : 3

6 : 3

4 : 1

4 : 4

2 : 2

8 : 6

3 : 1

3 : 2

Flow 𝑓2

𝑣4

𝑣3

𝑣2

𝑣1

𝑣𝑡𝑣𝑠 3 : 1

5 : 3

6 : 4

4 : 1

4 : 4

2 : 2

8 : 6

3 : 2

3 : 3

Flow 𝑓3

𝒗𝟒

𝒗𝟑

𝒗𝟐

𝒗𝟏

𝒗𝒕𝒗𝒔 3 : 0

5 : 4

6 : 5

4 : 1

4 : 4

2 : 2

8 : 7

3 : 2

3 : 3

Flow 𝒇𝟒