Bab II Konsep Dasar Konsep dasar mengenai graf dan jaringan dikutip dari Bondy dan Murty [1], Diestel [2], dan Fleischer [3]. Berikut ini diberikan beberapa notasi himpunan untuk memudahkan pendefinisian graf dan jaringan. Misalkan V adalah himpunan tak hampa. [V ] menyatakan 2
himpunan semua pasangan tak terurut (u,v), dengan u, v ∈ V ( G ) dan u ≠ v . V × V menyatakan himpunan semua pasangan terurut u, v , dengan u, v ∈ V ( G )
dan u ≠ v .
2.1 Graf Sebuah graf G dapat direpresentasikan dalam pasangan (V ( G ) , E ( G ) ) , dimana V ( G ) adalah himpunan tak hampa dan E ( G ) ⊆ [V(G) ] . V ( G ) disebut sebagai 2
himpunan titik, sedangkan E ( G ) disebut sebagai himpunan sisi.
Berikut diberikan suatu contoh dari graf. Graf G = (V ( G ) , E ( G ) ) dengan V ( G ) = {v1, v2, v3, v4, v5} dan E ( G ) = {(v1 , v2 ), (v2 , v3 ), (v3 , v4 ), (v2 , v4 ), (v4 , v5 ), (v2 , v5 )} ditunjukkan pada Gambar 2.1
Gambar 2. 1. Diagram graf G
Suatu graf dikatakan berhingga jika kedua himpunan titik dan sisinya berhingga. Graf yang hanya memiliki satu titik disebut trivial dan semua graf lain disebut nontrivial. Pada tugas akhir ini hanya dipakai graf berhingga dan nontrivial, sehingga pengertian kata ’graf’ selalu berarti ’graf berhingga nontrivial’. Dua titik yang dihubungkan oleh suatu sisi disebut bertetangga (adjacent). Dua sisi yang memiliki satu titik ujung yang sama disebut terkait (incident). Jika e = (u, v) ∈ E ( G ) , maka u dan v dikatakan terkait dengan sisi e, sedangkan titik u dan v disebut ujung dari e.
2.2 Subgraf Graf H dikatakan subgraf dari graf G, dinotasikan dengan H ⊆ G, jika V ( H ) ⊆ V ( G ) dan E ( H ) ⊆ E ( G ) . G dikatakan supergraf dari H jika H adalah subgraf dari G. H dikatakan subgraf pembangun dari G jika H adalah subgraf dari G dan V ( H ) = V ( G ) .
6
Gambar 2. 2. (a) Graf G (b) Graf H yang merupakan subgraf pembangun graf G
2.3 Lintasan (Path) Sebuah lintasan dengan panjang k adalah graf tak hampa P = (V ( P ) , E ( P ) ) dengan V ( P ) = {v0 , v1 ,..., vk } dan E ( P ) = {(v0 , v1 ), (v1 , v2 ),..., (vk −1 , vk )} . Titik vo dan vk disebut titik ujung dari P; titik-titik lainnya di P disebut titik dalam. Banyaknya sisi pada suatu lintasan menyatakan panjang dari lintasan tersebut. Lintasan yang menghubungkan titik u dan titik v dinotasikan dengan lintasan(u,v).
Gambar 2. 3. Graf G yang memuat lintasan P (garis hitam yang lebih tebal)
7
Dua titik u dan v pada graf G dikatakan terhubung jika terdapat lintasan-(u, v) di G. Graf G dikatakan graf terhubung jika untuk setiap pasangan titik u dan v pada G terdapat sedikitnya satu lintasan-(u, v) yang menghubungkannya.
Gambar 2. 4 (a) Graf terhubung, (b) graf tak terhubung
2.4 Graf Berarah dan Subgraf Berarah Definisi graf berarah D sama halnya seperti definisi graf namun sisi-sisinya memiliki arah. Sisi yang berarah ini disebut sebagai busur. Himpunan busur di D dinotasikan dengan A ( D ) , dimana A ( D ) ⊆ V(D) × V(D) . Sebagai pembeda antara notasi sisi dan busur, pada notasi busur diberikan garis panah diatas notasi r tersebut. Jika a = u, v ∈ A ( D ) adalah busur di D yang menghubungkan titik u ke
titik v untuk u,v di V ( D ) , maka u adalah ekor (tail) dari a dan v adalah kepala (head). Sebuah graf berarah D’ adalah subgraf berarah dari D jika V ( D ') ⊆ V ( D ) dan A ( D ') ⊆ A ( D ) . Terminologi dan notasi untuk subgraf berarah adalah sama seperti yang digunakan pada subgraf. Derajat masuk (indegree) pada titik v di D adalah banyaknya busur dengan kepala di v dan derajat keluar (outdegree) pada titik v adalah banyaknya busur dengan ekor di v.
8
Untuk sebuah graf berarah D, dapat dibuat graf G dengan menghilangkan arah pada setiap busur di D, dan graf G tersebut dinamakan underlying graph dari D. Sebaliknya, dari sebuah graf G dapat dibuat graf berarah D dengan memberikan arah tepat satu pada setiap sisi di G, dan graf berarah D tersebut dinamakan orientasi dari G. Misal L adalah lintasan berarah pada graf berarah D. Definisi lintasan berarah L serupa seperti pada lintasan P. Banyaknya busur pada suatu lintasan berarah L menyatakan panjang dari lintasan berarah tersebut. Pada Gambar 2.5 (a) diberikan graf berarah D, dan pada Gambar 2.5 (b) diberikan underlying graf D. Misalkan pada underlying graf D terdapat dua lintasan P1 dan P2,
dengan
V ( P2 ) = {v1, v7, v8, v4}
V ( P1) = {v1, v5, v6, v4} , dan
E ( P1) = {(v1, v5), (v5, v6), (v6, v4)} ,
E ( P2 ) = {(v1, v7), (v7, v8), (v8, v4)}.
Kedua
lintasan
menghubungkan titik v1 dengan titik v4. P1 dan P2 adalah subgraf dari G dan G adalah underlying graph dari D. dengan demikian terdapat subgraf P’1 dari D yang merupakan orientasi dari P1 dan terdapat subgraf P’2 dari D yang merupakan orientasi dari P2. P’1 adalah sebuah lintasan berarah pada graf berarah D tetapi P’2 bukan merupakan sebuah lintasan berarah pada graf berarah D.
9
Gambar 2. 5 (a) Graf berarah D (b) underlying graf D
2.5 Jaringan (Network) Jaringan N adalah graf berarah dengan dua subhimpunan titik yang utama, X dan r Y, dan sebuah fungsi c ( a ) yang bernilai bulat positif dan didefinisikan pada
setiap busur di himpunan A ( N ) ; himpunan X dan Y diasumsikan saling lepas dan tak kosong. Titik-titik di X adalah sources pada N dan titik-titik di Y adalah sinks pada N. Sources adalah titik yang mempunyai derajat masuk 0 (nol) dan sinks adalah titik yang mempunyai derajat keluar 0 (nol). Titik-titik yang bukan sources dan bukan sinks disebut titik tengah; himpunan titik tersebut dinotasikan dengan
r r r I ( N ) . Fungsi c ( a ) adalah kapasitas dari a untuk setiap a anggota A ( N ) . r Kapasitas dari sebuah busur a dapat diartikan sebagai representasi dari r maksimum suatu komoditi yang dapat melewati a .
Jaringan di gambarkan dengan graf berarah yang setiap busurnya dilabeli dengan kapasitasnya. Gambar 2.6 menunjukkan jaringan dengan dua sources x1 dan x2, tiga sinks y1, y2, dan y3, dan empat titik tengah v1, v2, v3, dan v4
10
Gambar 2. 6
Pada pembuatan jadwal pelajaran sekolah, jaringan N yang dibuat mempunyai satu titik sources yang selanjutnya disebut titik s dan satu titik sinks yang selanjutnya disebut titik t. Sedangkan titik-titik tengah disusun kedalam beberapa subhimpunan.
2.6 Aliran Jaringan (Network flow) Jaringan N dapat dilalui dengan aliran (flow) dan kemudian disebut aliran r jaringan. Suatu aliran pada jaringan N adalah fungsi f ( a ) : V × V → R yang
r menyatakan banyaknya komoditi yang melalui busur a atau busur r Selanjutnya kita notasikan f a = f
()
u, v .
( u, v ) = f ( u, v ) . Karakteristik suatu aliran
adalah :
r r r 0 ≤ f a ≤ c a untuk setiap a ∈ A( N ) ,
() ()
f ( u, v ) = − f ( v, u ) untuk setiap u,v ∈ I ( N ) , dan Untuk semua u ∈ I(N) : ∑v∈V(N) f(u, v) = 0 nilai aliran adalah banyaknya komoditi yang mengalir dari titik s menuju titik t.
11
2.7 Jaringan Sisa (Residual Network) Jaringan sisa N’ adalah subgraf berarah dari jaringan N, tetapi kapasitas busur (u,v) pada jaringan N’ adalah c ' ( u, v ) = c ( u, v ) - f ( u, v ) . Jaringan N’ dapat diberi aliran yang mempunyai karakteristik sama dengan aliran jaringan N .
2.8 Augmenting Path dan Aliran Maksimum Augmenting path adalah lintasan berarah dari titik s ke titik t pada jaringan sisa. Sepanjang augmenting path diberikan aliran dengan nilai sebesar kapasitas terkecil cmin dari semua busur yang dimuat augmenting path tersebut. Dengan demikian nilai aliran adalah sebesar cmin untuk tiap satu augmenting path.
Aliran maksimum adalah aliran yang nilainya maksimum. Bagaimana cara mencari aliran maksimum tersebut ? Teorema dibawah memberikan syarat cukup dan syarat perlu untuk mendapatkan aliran maksimum. Teorema [4]. Aliran pada suatu jaringan adalah maksimum jika dan hanya jika
tidak ada augmenting path pada jaringan tersebut.
2.9 Algoritma Ford-Fulkerson Algoritma Ford-Fulkerson adalah metode untuk mendapatkan aliran maksimum pada aliran jaringan. Algoritma Ford-Fulkerson : Masukan : Jaringan N sebagai jaringan sisa N’ yang pertama ( c ( u, v ) = c ' ( u, v ) ). Keluaran : Aliran pada Jaringan N telah maksimum.
12
r 1. Pada jaringan sisa N 'k dengan k = 1, 2, …n, Lakukan inisial f ( a ) = 0 , untuk
r setiap a ∈ A ( N 'k ) . 2. Cari augmenting path pi , jika ada lakukan : •
Cari kapasitas minimum cmin dari setiap busur di pi .
•
r Beri aliran sepanjang pi sebesar f ( a ) = cmin
•
Jika ci adalah kapasitas busur pada pi maka c 'i = ci - cmin.
3. Bentuk Jaringan sisa N 'k +1 dengan mengubah kapasitas busur di pi menjadi c 'i
4. Ulangi langkah (2) untuk N 'k +1 , sampai tidak ada lagi augmenting path di jaringan sisa. Gambar dibawah memberikan ilustrasi mengenai proses pencarian aliran maksimum. Panah warna hitam dan merah menyatakan busur di jaringan. Panah dengan warna merah juga menyatakan busur pada augmenting path pada jaringan tersebut. Panah warna biru menyatakan aliran yang melalui busur pada
augmenting path. Bilangan pada panah merah dan hitam menyatakan kapasitas busur dan bilangan pada panah warna biru menyatakan nilai aliran yang melalui suatu busur.
13
2
2
2 2
2
1
1
1
14
(7)
(8)
v3
v1
v1
v3
0 0
0 0
0
s
0
t 1
4
s
4
t 3
1
4
v4
v2
Jaringan N’4 dengan Augmenting path P4 : s → v2 → v4 → t dan cmin = 3
4 4
3
v2
0
0
3 3
v4
Aliran yang diberikan sepanjang P4 adalah cmin = 3
Gambar 2. 7
15
