Bab 2 Teori Dasar Pada bagian ini diberikan definisi-definisi dasar dalam teori graf berikut penjabaran mengenai kompleksitas algoritma beserta contohnya yang akan digunakan dalam tugas akhir ini. Berikut ini diberikan beberapa notasi himpunan untuk memudahkan pendefinisian graf. Misalkan V adalah himpunan berhingga tak hampa. [V]2 menyatakan himpunan semua pasangan tak terurut (u, v), dengan u, v ∈ V dan u ≠ v. V×V menyatakan himpunan semua pasangan terurut u, v , dengan u, v ∈ V dan u ≠ v.
2.1 Definisi Graf Sebuah graf G dapat direpresentasikan dalam pasangan (V(G), E(G)), dimana V(G) adalah himpunan berhingga tak hampa dan E(G) ⊆ [V(G)]2. V(G) disebut sebagai himpunan titik, sedangkan E(G) disebut sebagai himpunan sisi. Secara umum graf dapat digambarkan sebagai suatu diagram, dimana setiap titik di V(G) direpresentasikan sebagai titik sedangkan setiap sisi di E(G) direpresentasikan sebagai ruas garis yang menghubungkan titik-titik di V(G). Jika e = (u, v)∈E(G) merupakan sisi yang menghubungkan titik u dan v maka titik u dan v dikatakan sebagai titik ujung dari e. Sebagai contoh Gambar 2.1.a merupakan graf G dengan V(G) = {v1, v2, v3, v4, v5, v6} dan E(G) = {(v1, v2), (v1, v3), (v2, v3), (v2, v4), (v5, v6)}.
3
Dua titik yang dihubungkan oleh sebuah sisi disebut bertetangga (adjacent) sedangkan dua sisi yang berbagi titik ujung disebut terkait (incident). Graf lengkap (complete graph) dengan n titik dan dinotasikan Kn adalah suatu graf yang setiap pasang titiknya bertetangga. Pada Gambar 2.1.b diberikan graf lengkap K5. Derajat suatu graf G, dinotasikan dG(v), menyatakan banyaknya sisi yang terkait dengan v. Suatu graf G disebut r-regular jika dG(v) = r untuk semua v
V(G). Gambar 2.1.c
merupakan contoh graf-graf regular. Misalkan e = (u, v) ∈ E(G), bobot sisi e menyatakan banyaknya sisi yang terkait dengan (u,v). Gambar 2.1.a adalah graf G dimana bobot sisi (v1, v2) dan (v2, v3) adalah 3, bobot sisi (v1, v3) dan (v2, v4) adalah 2, sedangkan bobot sisi (v5, v6) adalah 0.
Gambar 2.1.a. Graf G dengan himpunana titik V(G) = {v1, v2, v3, v4, v5, v6} dan himpunan sisi E(G) = {(v1, v2), (v1, v3), (v2, v3), (v2, v4), (v5, v6)}.
Gambar 2.1.b. Graf lengkap K5.
4
d
b
f
a
m
j
i
n
h
q
c g
e
r=0
l
r=1
k
r=2
p
o
r=3
r=4
Gambar 2.1.c. Graf r-regular dengan r = 0, 1, 2, 3, 4.
2.2 Matriks Ketetanggaan dan Keterkaitan Graf G(V, E) dengan
V
= v dan
E
= ε memiliki matriks berukuran v
X
ε yang
disebut matriks keterkaitan dari G. Misalkan V = {v1, v2,...,vv}dan E = {e1, e2,...,eε} maka matriks
keterkaitan
dari
G
adalah
matriks
M(G)
=
[mij]
dimana
⎧ 1, jika vi terkait dengan ej mi j = ⎨ ⎩0, jika vi tidak terkait dengan ej . Matriks lain yang berukuran v
X
v disebut matriks ketetanggaan dari G yang dinotasikan
⎧ 1, jika vi bertetangga dengan vj A(G) = [aij] dimana ai j = ⎨ ⎩0, jika vi tidak bertetangga dengan vj .
e1 e2 e3 e4 e5 v1 v2 v3 v4
1 1 0 0
0 1 0 1
1 0 1 0
M(G)
0 0 1 1
1 0 0 1
v1 v2 v3 v4
v1
v2 v3 v4
0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 0
A(G)
Gambar 2.2. Graf G beserta matriks keterkaitan dan ketetanggan.
5
2.3 Subgraf, Gabungan Graf dan Jumlah Graf Suatu graf H disebut subgraf dari G, ditulis H ⊆ G, jika V ( H ) ⊆ V (G ) dan E ( H ) ⊆ E (G ) . Jika H subgraf dari G, maka G disebut supergraf dari H.
G1
G2
Gambar 2.3.1. G2 adalah suatu subgraf dari G1. Gabungan dari dua graf G1 = (V1, E1) dan G2 = (V2, E2) adalah suatu graf G3, ditulis G3 = G1 ∪ G2, jika V3 = V1 ∪ V2 dan E3 = E1 ∪ E2. Jika G1 = G2 maka G1 ∪ G2 bisa ditulis sebagai 2G1. Jumlah dari dua graf G1 = (V1, E1) dan G2 = (V2, E2) adalah suatu graf G4 ditulis G4 = G1 + G2, jika V4 = V1 ∪ V2 dan E4 = E1 ∪ E2 ∪ {(u, v)│ u ∈ V1, v ∈ V2}.
Gambar 2.3.2. Gabungan dan jumlah dari dua graf.
6
Gambar 2.3.3. Gabungan dua graf G1 dan G2 dimana G1 = G2.
2.4 Perkalian Kartesius, Komplemen, Subdivisi dan Induksi pada Graf Perkalian kartesius dari graf G1(V1, E1) dan G2(V2, E2) adalah graf G(V, E), ditulis G = G1 × G2, jika V = V1 × V2, dan dua titik u1, u2 dan v1, v2 di G bertetangga jika dan hanya jika salah satu dari dua hal berikut berlaku: u1 = v1 dan (u2, v2) ∈ E2 atau u2 = v2 dan (u1, v1) ∈ E1. Pada Gambar 2.4.1 diberikan graf G1 dan G2 serta hasil kali kartesiusnya. Komplemen G dari suatu graf G adalah graf dengan V( G ) = V(G), dan (u, v) ∈ E ( G ) jika dan hanya jika (u, v) ∉ E (G). Pada Gambar 2.4.2 diberikan graf G beserta G . Subdivisi pada sisi (u, v) dari suatu graf G dilakukan dengan mengganti sisi (u, v) dengan sebuah titik w dan sisi (u,w) serta (w, v). Pada Gambar 2.4.3, G2 merupakan graf yang diperoleh dari G1 dengan melakukan subdivisi pada sisi (1, 3) ∈ E(G1). Subgraf dari G yang himpunan titiknya V' ⊆ V(G) dan himpunan sisinya merupakan himpunan semua sisi pada G yang kedua titik ujungnya berada di V' disebut subgraf dari G yang diinduksi oleh V' dan dinotasikan sebagai G[V']. Gambar 2.4.4 merupakan graf G yang diinduksi oleh V' = {2, 3, 4, 6}.
7
;
G1
;
G2
G = G1
G2
Gambar 2.4.1. Perkalian kartesius dua buah graf G1 dan G2.
Gambar 2.4.2. Graf G dengan komplemennya G .
Gambar 2.4.3. G2 adalah hasil subdivisi sisi (1, 3) pada G1.
Gambar 2.4.4. Graf G dan subgraf terinduksinya.
8
2.5 Keterhubungan Lintasan-(v0, vn) pada suatu graf G adalah barisan titik di G v0, v1, v2, v3, .., vn dimana (vi, vi+1) ∈ E(G) untuk setiap i = 0, 1, 2,..., n-1 dan vi ≠ vj untuk i ≠ j. u e
a f
y d x
v
Lintasan-(x, v) : xwyuv
b
g
w
c
Gambar 2.5.1 Graf G beserta salah satu lintasannya. Dua titik u, v pada graf G dikatakan terhubung jika terdapat lintasan-( u, v) di G. Graf G dikatakan graf terhubung jika untuk setiap pasangan dua titik u dan v pada G terdapat lintasan-(u, v).
(a)
(b)
Gambar 2.5.2. (a) Graf terhubung, (b) graf tak terhubung. Komponen dari suatu graf adalah subgraf terhubung yang maksimal.
9
2.6 Maximal Matching Definisi 2.6.1. M disebut matching di G jika M ⊆ E(G) dimana tiap dua sisi di M tidak
terkait. Definisi 2.6.2. Maximal matching di G adalah suatu matching M dimana untuk setiap
e ∈ E(G)\M terdapat t ∈ M sehingga e terkait dengan t. Kardinalitas dari suatu maximal matching menyatakan banyaknya anggota dari himpunan tersebut. Pada Gambar 2.6.1 diberikan graf Petersen dan dua maximal matching-nya yaitu
S1 = {(1, 6), (2, 7), (3, 4), (5, 10)} dan S2 = {(1, 6), (3, 4), (7, 10)}. 1 5
1 2
6
5
7
10 9
7
10
8
4
9 3
2
6
4
8 3
Gambar 2.6.1. Maximal matching pada graf Petersen. Jelas bahwa
S2 < S1 . Perhatikan bahwa setiap sisi pada graf Petersen terkait
dengan lima sisi (termasuk dirinya sendiri). Dengan demikian agar diperoleh suatu maximal
matching dibutuhkan paling sedikit
15 = 3 sisi. Jadi, S2 merupakan suatu maximal 5
matching dengan kardinalitas terkecil pada graf Petersen.
10
2.7 Kelas-Kelas Graf Definisi 2.7.1. Graf lintasan dengan n titik, n≥2, dinotasikan sebagai Pn adalah graf dengan
barisan titik v1, v2, v3, ..., vn dan (vi, vi+1) ∈ E(Pn) untuk setiap i = 1, 2,..., n-1 dan vi ≠ vj untuk i ≠ j. Definisi 2.7.2. Graf lingkaran dengan n titik, n≥3, dinotasikan sebagai Cn adalah graf
tehubung yang setiap titiknya berderajat dua. Definisi 2.7.3. Graf roda dengan n titik, n≥4 dinotasikan sebagai Wn, dimana
Wn = Cn-1 + K1. Jika v0 ∈ K1 dan v ∈ Cn-1 maka sisi (v0, v) ∈ E(Wn) disebut jari-jari dari Wn. Definisi 2.7.4. Graf kipas dengan n titik, n≥3 dinotasikan sebagai Fn, dimana
Fn = Pn-1 + K1. Jika v0 ∈ K1 dan v ∈ Pn-1 maka sisi (v0, v) ∈ E(Fn) disebut jari-jari dari Fn. Definisi 2.7.5. Graf lingkaran ganda dengan 2n titik, n≥3 dinotasikan sebagai D2n dimana
D2n = P2 × Cn. Definisi 2.7.6. Graf kincir angin dengan 2n+1 titik, n≥1 dinotasikan sebagai KA2n+1 dimana
KA2n+1 = nP2 + K1. Jika v0 ∈ K1 dan v ∈ nP2 maka sisi (v0, v) ∈ E(KA2n+1) disebut jari-jari dari KA2n+1. Definisi 2.7.7. Graf jahangir dengan 2n+1 titik, n≥1, dinotasikan sebagai J2n+1, adalah graf
yang diperoleh dari Wn+1 = Cn + K1 dengan cara melakukan subdivisi pada setiap sisi di Cn.
11
(a) Graf lintasan P5,
(b) graf lingkaran C8,
(c) graf roda W9,
1
9 10 3
2
8
2
3
9
16
11
15
12
14
1
7
4
8
13 6
4 5
(d) graf kipas F7,
(e) graf lingkaran ganda D16,
5 6
7
(f) graf kincir KA9,
(g) graf jahangir J9. Gambar 2.6 Contoh kelas-kelas graf.
12
2.8 Algoritma dan Kompleksitasnya Definisi 2.8.1. Algoritma adalah serangkaian langkah-langkah berhingga untuk melakukan
perhitungan atau menyelesaikan suatu masalah. Secara umum suatu algoritma dituliskan menggunakan bahasa komputer. Sebagai contoh berikut ini diberikan algoritma untuk mencari nilai maksimum dari suatu barisan bilangan yang berhingga.
ALGORITMA 2.8 Procedure max(a1, a2,..., an: bilangan bulat)
max := a1 for i := 2 to n if max < ai then max := ai
{max berisi nilai maksimum yang dicari} Definisi 2.8.2. Misal f dan g adalah fungsi dari himpunan bilangan riil ke himpunan
bilangan riil. Kita katakan f(x) adalah O(g(x)) (dibaca: f(x) berorde g(x)) jika terdapat konstanta C dan k sehingga
f(x) ≤ C g(x)
bilamana x > k.
Sebagai contoh akan ditunjukkan bahwa f(x) = x2+2x+1 adalah O(x2). Perhatikan bahwa
x2+2x+1 ≤ x2+2x2+ x2 = 4x2 bilamana x >1. Jadi, dengan mengambil C = 4 dan k = 1 terbukti f(x) adalah O(x2). Bagaimanakah menganalisis keefisiensian suatu algoritma? Salah satu ukurannya adalah banyaknya waktu yang dibutuhkan (time complexity) komputer untuk menyelesaikan masalah dengan menggunakan algoritma tersebut ketika nilai masukan (input) diberikan dengan ukuran tertentu. Ukuran lainnya adalah kapasitas memori komputer yang dibutuhkan (space complexity) dalam mengimplementasikan algoritma tersebut ketika nilai masukan (input) diberikan dengan ukuran tertentu. Namun, pada bagian ini kita hanya memandang ukuran waktu saja. Besarnya ukuran waktu dipengaruhi oleh banyaknya
13
operasi dasar yang digunakan dalam algoritma tersebut. Misalnya operasi perbandingan, perkalian, penjumlahan, pembagian atau operasi dasar lainnya. Jika banyaknya operasi dasar dalam suatu algoritma berorde f(x), maka dikatakan algoritma tersebut berorde
O(f(x)), atau algoritma tersebut mempunyai kompleksitas O(f(x)). Apabila suatu algoritma berorde O(g(x))−dimana g(x) adalah suatu polinom−maka dalam hal ini sudah cukup untuk mengatakan algoritma tersebut efisien. Banyaknya perbandingan akan digunakan sebagai ukuran keefisienan Algoritma 2.8. Perhatikan bahwa untuk mencari nilai maksimum dari himpunan dengan n elemen, nilai maksimum sementara berisi nilai yang berada pada urutan pertama pada daftar sebagai nilai awal (initial value). Kemudian nilai ini terus diperbaharui seiring perbandingan yang dilakukan selama nilai maksimum belum tercapai. Karena dua perbandingan digunakan untuk setiap dua elemen pada himpunan tersebut dan satu perbandingan lagi digunakan untuk keluar dari loop ketika i = n+1, tepatnya ada 2(n-1) +1 = 2n-1 perbandingan ketika algoritma ini diterapkan. Jadi, algoritma tersebut berorde n atau O(n). Berikut penjelasan mengenai P, NP, NP-Complete menurut Garey dan Johnson [6]. Jika suatu masalah yang dapat diselesaikan dengan algoritma berorde polinom (algoritma polinomial), maka kita katakan masalah tersebut berada dalam kelas P. Misalkan suatu masalah belum dapat dicari solusinya dengan algoritma polinomial. Tetapi, jika diberikan solusi untuk masalah ini, kebenarannya dapat diverifikasi dengan algoritma polinomial. Masalah yang demikian dikelompokkan ke dalam kelas NP.
NP-Complete adalah sub kelas dari NP yang terdiri dari masalah yang ekivalen. Jadi dalam kelas NP-Complete setiap masalah dapat ditransformasikan menjadi masalah lainnya di kelas yang sama. Kelas NP-Complete dipandang sebagai kelompok masalah yang paling sulit untuk diselesaikan. Teorema Garey [6]
14
Menentukan maximal matching terkecil pada sebarang graf termasuk masalah
NP-Complete.
15
