Bab 2 LANDASAN TEORI. 2.1 Definisi Graf

Bab 2 LANDASAN TEORI 2.1

Definisi Graf

Suatu graf G terdiri dari himpunan tak kosong terbatas dari objek yang dinamakan titik dan himpunan pasangan (boleh kosong) dari titik G yang dinamakan sisi. Himpunan titik dari graf G dinotasikan VG atau V dan himpunan sisi dinotasikan EG atau E. Graf G, biasanya dinotasikan G = (V G, EG) atau G = (V, E). Dalam tugas akhir ini, banyaknya titik |V G| dan sisi |EG| dari suatu graf G dinotasikan n(G) dan m(G) atau n dan m. Graf G = (V, E) direpresentasikan dalam bentuk gambar. Setiap titik u ∈ V digambarkan dengan lingkaran kecil (titik) dan setiap sisi e ∈ E digambarkan dengan garis yang menghubungkan titik-titik di graf G . Posisi titik dan sisi dapat digambar secara bebas, seperti tampak pada Gambar 2.1. Titik u dan v dikatakan titik ujung dari suatu sisi e di graf G jika e = {u, v}. Lebih lanjut, u dan v dikatakan titik-titik yang bertetangga, sedangkan u dan e dikatakan terkait, begitu juga dengan v dan e. Jika e1 dan e2 adalah dua buah sisi yang berbeda dari graf G yang terkait pada sebuah titik yang sama, maka e1 dan e2 dikatakan bertetangga. Untuk memudahkan, sisi e = {u, v} dinotasikan dengan e = uv atau e = vu. Sebuah sisi yang terkait hanya pada satu titik disebut loop,

5

6

BAB 2. LANDASAN TEORI

Gambar 2.1: Graf G1 sedangkan dua sisi atau lebih yang terkait pasangan titik yang sama, disebut sisi ganda. Banyaknya sisi ganda pada pasangan titik u dan v disebut multiplisitas sisi dari (u,v ) dan dinotasikan µ(u, v). Sementara, bilangan terbesar dari sisi ganda yang terdapat pada setiap pasangan titik di G disebut multiplisitas dari G dan dinotasikan µ(G). Multiplisitas dari graf pada Gambar 2.1 adalah 3 (µ(G) = 3) yang merupakan multiplisitas sisi dari pasangan titik v1 dan v4 .

Gambar 2.2: Graf yang memuat loop

Graf sederhana adalah graf yang tidak memuat loop dan sisi ganda. Sedangkan graf yang memiliki sisi ganda disebut multigraf. Gambar 2.1 merupakan salah satu contoh multigraf dan Gambar 2.3 merupakan salah satu contoh graf sederhana.


7

Gambar 2.3: Graf sederhana

Selanjutnya pada tugas akhir ini, G diasumsikan graf sederhana. Untuk setiap v ∈ V pada suatu graf G = (V, E), banyaknya sisi yang terkait dengan v disebut derajat dari v, dinotasikan d(v, G) atau d(v). Derajat minimum dari G dinotasikan δ(G). Derajat maksimum dari G dinotasikan ∆(G). Sebuah titik yang berderajat nol disebut titik terisolasi. Jika setiap titik dari G memiliki derajat yang sama, maka G dikatakan graf ∆(G)-teratur. Sebagai contoh, derajat minimum dan maksimum graf sederhana pada Gambar 2.3 adalah dua dan empat, yaitu derajat pada titik v3 serta v2 dan v4 . Sementara, Gambar 2.4 adalah contoh dari graf 2-teratur.

Gambar 2.4: Graf 2-teratur

Sebarang graf G berkorespondensi dengan suatu matriks berukuran n×n yang disebut matriks ketetanggaan dari G . Misalkan G = {V, E} dengan v1 , v2 , ..., vn ∈ V dan e1 , e2 , ..., em ∈ E. Matriks ketetanggaan adalah matriks A(G) = [aij ], dimana aij adalah banyaknya sisi yang berkaitan dengan pasangan titik vi dan vj . Matriks

8


lainnya yang berkorespondensi dengan sebarang graf G adalah matriks keterkaitan dari G . Berbeda dengan matriks ketetanggaan, matriks keterkaitan adalah matriks B(G) = bij yang berukuran n × m dimana bij menunjukkan keterkaitan antara titik vi dan sisi ej , yaitu   1, jika v dan e berkaitan; i j bij =  0, lainnya.

(2.1.1)

Tabel 2.1: Matriks ketetanggaan dari graf pada Gambar 2.3 v1

v2

v3

v4

v5

v1

0

1

0

1

1

v2

1

0

1

1

1

v3

0

1

0

1

0

v4

1

1

1

0

1

v5

1

1

0

1

0

Matriks ketetanggaan dan keterkaitan dari graf pada Gambar 2.3 dapat dilihat pada Tabel 2.1 dan 2.2. Tabel 2.2: Matriks keterkaitan dari graf pada Gambar 2.3 e1

e2

e3

e4

e5

e6

e7

e8

v1

1

0

0

0

1

0

0

1

v2

1

1

0

0

0

1

1

0

v3

0

1

1

0

0

0

0

0

v4

0

0

1

1

0

0

1

1

v5

0

0

0

1

1

1

0

0

Suatu subgraf dari graf G = (V, E) adalah graf H = (V H, EH) dimana V H ⊆ V dan EH ⊆ E. Sebuah subgraf dikatakan subgraf pembangun jika V H = V . Jika U

9


adalah sebuah subhimpunan tak kosong dari himpunan titik V dari G , maka subgraf G[U ] dari G yang terinduksi oleh U adalah graf yang memiliki himpunan titik U dan himpunan sisinya adalah sisi-sisi di G yang berkaitan dengan dua anggota di U. Begitu juga, apabila X adalah subhimpunan tak kosong dari E, maka subgraf G[X] terinduksi sisi oleh X adalah graf yang himpunan titiknya memuat titik-titik yang berkaitan dengan paling sedikit satu sisi di X dan himpunan sisinya adalah X.

Gambar 2.5: G4 [v4 ] Misalkan e merupakan sisi dari suatu graf G = (V, E). G − e adalah notasi untuk graf yang didapat dari G dengan menghapus sisi e. Lebih umum, jika E ′ adalah subhimpunan dari E, graf yang didapat dengan menghapus sisi-sisi E ′ dari G dinotasikan G − E ′ . Sama halnya, jika v adalah titik dari G , G − v adalah notasi untuk graf yang didapat dari G dengan menghapus titik v dan semua sisi yang berkaitan dengan v. Lebih umum, jika V ′ adalah subhimpunan dari V , graf yang didapat dengan menghapus titik-titik V ′ dari G bersama-sama dengan sisi-sisi yang berkaitan dengan titik-titik di V ′ dinotasikan G − V ′ . Perhatikan Gambar 2.5. Graf pada Gambar 2.5(b) didapat dengan cara menghapus titik v4 pada graf pada Gambar 2.5(a). Sehingga graf pada Gambar 2.5 dapat juga ditulis G4 − v4 . Pada titik u, v ∈ V , notasi d∗v (u) menunjukkan banyaknya tetangga dari v selain u yang memiliki derajat ∆(G). Sebuah sisi uv ∈ E dikatakan dapat dieleminasi jika d(u) + d∗u (v) ≤ ∆(G) atau d(v) + d∗v (u) ≤ ∆(G).

10


Sebuah graf G dikatakan terhubung jika untuk setiap pasang titik u, v ∈ V dapat dicari barisan dari titik dan sisi di G dalam bentuk u = u0 , u0 u1 , u1 , u1 u2 , ..., un−1 un , un = v. Komponen adalah graf terhubung maksimal. Banyaknya komponen pada sebarang graf G dinotasikan dengan ω(G). Sebagai contoh, perhatikan Gambar 2.6. Misalkan graf pada Gambar 2.6(a) dinamakan graf G dan graf pada Gambar 2.6(b) dinamakan graf H. Karena pada setiap pasang titik pada G dapat dicari barisan dari titik dan sisi dalam bentuk u = vi , vi vi+1 , vi , ..., vj−1 vj , vj = u dimana 1 ≤ i ≤ j ≤ 5 maka G dikatakan graf terhubung dan karenanya, graf G hanya memiliki satu komponen. Berbeda halnya dengan H, titik v3 tidak memiliki satu pun pasangan sehingga dapat dibentuk barisan dari titik dan sisi yang menunjukkan bahwa H adalah terhubung. Akibatnya, H adalah graf tak terhubung. Komponen pada G adalah satu dan pada H adalah dua.

Gambar 2.6: (a) Graf terhubung (b) Graf tak terhubung

2.2

Beberapa Kelas Graf

Suatu graf yang setiap dua titiknya bertetangga, disebut graf lengkap. Graf lengkap dengan n titik dinotasikan dengan Kn .

K1 disebut graf trivial.

Graf bipartit

G = (U, W, E) adalah graf yang himpunan titiknya dapat di partisi menjadi dua himpunan U dan W sehingga setiap sisi menghubungkan titik dari himpunan U


11

ke titik dari himpunan W . Graf bipartit lengkap adalah graf bipartit dimana setiap titik dari himpunan U bertetangga dengan setiap titik dari himpunan W . Jika himpunan U dan W memiliki r dan s titik, maka graf bipartit lengkap dinotasikan dengan Kr,s .

Gambar 2.7: (a) K4 (b) Graf trivial (c) Graf bipartit

Graf G dikatakan siklis, jika G adalah graf 2-teratur dan terhubung. Graf unisiklis adalah graf yang memuat paling banyak satu graf siklis. Graf asiklis adalah graf yang tidak memuat graf siklis. Sebuah graf pohon adalah graf asiklis terhubung, sementara itu, graf hutan adalah graf asiklis. Lebih lanjut, graf siklis disebut graf lingkaran. Teorema 2.1 [1] Jika G adalah suatu hutan dengan n titik maka m = n − ω(G).

Gambar 2.8: Graf hutan


12

Pengertian pohon hampir serupa dengan pengertian hutan. Perbedaan kedua definisi hanya terletak pada kata terhubung. Karena hutan tidak harus berupa graf terhubung maka hutan bisa memiliki komponen lebih dari satu sedangkan pohon merupakan graf terhubung sehingga hanya memiliki satu komponen. Oleh karena itu, untuk pohon G dengan n titik berlaku m=n − 1. Graf roda Wn adalah graf dengan n + 1 titik, yang didapat dari menambahkan satu titik w pada suatu graf lingkaran G dengan n titik dan menghubungkan w ke setiap titik di G . Titik w disebut titik dasar. Graf roda Wn memiliki 2n sisi. Graf lintasan Pn adalah graf terhubung yang terdiri dari tepat dua titik berderajat satu dan n − 2 titik berderajat dua. Graf kipas Fn adalah graf yang memiliki n+1 titik, yang didapat dari menambahkan satu titik w pada suatu graf lintasan Pn dan menghubungkan w ke setiap titik di Pn . Titik w disebut titik dasar. Graf kipas memiliki 2n − 1 sisi

Gambar 2.9: (a) Graf roda (b) Graf lintasan (c) Graf kipas

Misalkan s adalah bilangan bulat positif. G dikatakan graf s-degenerate jika titiktitik dari G dapat diurutkan menjadi v1 , v2 , ..., vn sehingga d(vi , Gi ) ≤ s untuk setiap i, 1 ≤ i ≤ n, dimana Gi = G − {v1 , v2 , ..., vi−1 }. Degeneracy s(G) dari G adalah bilangan bulat terkecil s sehingga G adalah s-degenerate. Perhatikan Gambar 2.10. Graf yang dikonstruksi pada Gambar 2.10 merupakan graf H = (V, E) dengan himpunan titik yang telah terurut, yaitu V = {v1 , v2 , v3 , v4 , v5 , v6 },

13


kemudian didapat d(v1 , H1 ) = 1, d(v2 , H2 ) = 1, d(v3 , H3 ) = 2, d(v4 , H4 ) = 2, d(v5 , H5 ) = 1 dan d(v6 , H6 ) = 0. Sehingga d(vi , Hi ) ≤ 2 untuk setiap i, 1 ≤ i ≤ 6. Akibatnya, graf G merupakan graf 2-degenerate. Pengurutan titik-titik dari graf G tidaklah tunggal. Pengurutan titik-titik ini, hanyalah salah satu contoh pengurutan yang optimal sehingga s(G) = 2.

Gambar 2.10: Graf 2-degenerate

Pada graf kipas Fn , berlaku δ(Fn ) = 2. Misalkan titik-titik pada graf kipas, v ∈ V Fn diurutkan menjadi v1 , v2 , ..., vn+1 , dimana v1 dan vn adalah titik dengan derajat terkecil, vn+1 adalah titik dasar, dan sisanya, v2 , v3 , ..., vn−1 . Sehingga akan didapatkan s(Fn ) = 2.

(2.2.1)

Pada graf roda Wn , berlaku δ(Wn ) = 3. Misalkan titik-titik pada graf roda, v ∈ V Wn diurutkan menjadi v1 , v2 , ..., vn+1 , dimana vn+1 adalah titik dasar, dan sisanya,

14


Gambar 2.11: Pengurutan titik pada graf kipas dan graf roda v2 , v3 , ..., vn−1 . Sehingga akan didapatkan s(Wn ) = 3.

(2.2.2)

Arboricity a(G) dari graf G adalah bilangan terkecil dari banyaknya subgraf yang dapat dipartisi sisi dari G sehingga setiap subgraf menghasilkan sebuah subgraf asiklis atau hutan. Nash-Williams [3] telah membuktikan bahwa a(G) = max ⌈m(H)/(n(H) − 1)⌉ , H⊆G

(2.2.3)

dimana H adalah setiap subhimpunan tak kosong dari G . Sebarang subgraf H dari G adalah s(G)-degenerate, akibatnya m(H) ≤ s(G)(n(H) − 1) dan m(H)/(n(H) − 1) ≤ s(G). Sehingga, a(G) ≤ s(G).

(2.2.4)

Gambar 2.12: a(G9 ) = 2

Bilangan unisiklis a′ (G) dari graf G adalah bilangan terkecil dari banyaknya subgraf


15

unisiklis, yang dapat dipartisi sisi dari G . Karena sebuah hutan adalah sebuah graf unisiklis dan sebuah graf unisiklis dapat dipartisi menjadi satu atau dua hutan, maka a′ (G) ≤ a(G) ≤ 2a′ (G).

(2.2.5)

Gambar 2.13: Graf G dengan a′ (G) = 2

Lemma 2.1 [7] Untuk sebarang graf taktrivial G berlaku kondisi (1)-(3) dibawah ini: 1. δ(G) ≤ 2a(G) − 1; 2. δ(G) ≤ 2a′ (G); dan 3. jika a′ (G) terbatas dan U = {u ∈ V |d(u, G) ≤ 2a′ (G)}, maka |U | ≥ n/(2a′ (G)+ 1 dan |U | = Θ(n). Bukti: (1.) Pertama-tama, asumsikan bahwa G tidak memiliki titik terisolasi. Misalkan n′ adalah banyaknya titik v dari G sehingga 1 ≤ d(v) ≤ 2a(G) − 1. Maka jelas, n′ + 2a(G)(n − n′ ) ≤ 2m. Dengan kata lain, G dapat dipartisi menjadi a(G) hutan dan sebarang hutan memiliki paling banyak n−1 sisi. Oleh karena itu, m ≤ a(G)(n − 1). Sehingga n′ ≥ 2a(G)/(2a(G) − 1) > 1, dan karenanya δ(G) ≤ 2a(G) − 1. (2.) dan (3.) Karena setiap titik di V − U memiliki derajat ≥ 2a′ (G) + 1, maka (2a′ (G) + 1)(n − |U |) ≤ 2m. Karena sebarang graf unisiklis memiliki paling banyak n sisi, maka m ≤ a′ (G)n. Sehingga |U | ≥ n/(2a′ (G) + 1). Karenanya, U 6= φ dan

16

BAB 2. LANDASAN TEORI δ(G) ≤ 2a′ (G). Jika a′ (G) terbatas, maka |U | = Θ(n).\\

Dengan Lemma 2.1 dan persamaan (2.2.5), akan didapat batas atas untuk s(G) dalam kaitannya dengan a(G), dan a′ (G). Perhatikan bahwa untuk sebarang subgraf H dari G berlaku a(H) ≤ a(G) dan a′ (H) ≤ a′ (G). Lemma 2.2 [7] Untuk sebarang graf taktrivial G berlaku kondisi dibawah ini: 1. s(G) ≤ 2a(G) − 1; 2. s(G) ≤ 2a′ (G);

2.3

Pewarnaan Sisi-f

Kapasitas titik f adalah suatu fungsi dari himpunan titik V ke himpunan bilangan asli. Pewarnaan sisi -f dari suatu graf G = (V, E) adalah suatu fungsi cf dari himpunan sisi E ke himpunan warna, yang biasanya diwakili oleh himpunan bilangan asli, sedemikian rupa sehingga sisi-sisi yang berkaitan dengan sebarang titik v ∈ V , memiliki paling banyak f (v) warna yang sama. Fungsi cf disebut pewarnaan sisi-f dengan k warna jika cf (E) ≤ {1, 2, ..., k}. Bilangan terkecil k sehingga terdapat pewarnaan sisi-f dengan k warna disebut bilangan kromatik sisi-f, dan dinotasikan χ′ f (G). Hakimi dan Kariv [5] mendapatkan batas untuk χ′ f (G), yaitu d(v) + µ(v, w) ′ ∆f (G) ≤ χ f (G) ≤ max , v,w∈V f (v)

(2.3.1)

dimana

d(v) ∆f (G) = max . v∈V f (v)

(2.3.2)

Persamaan (2.3.1) dapat disederhanakan menjadi χ′ f (G) ≤ ∆f (G) + µf (G).

(2.3.3)

Batas yang didapat oleh Hakimi dan Kariv merupakan perumuman dari batas Vizing [8] untuk pewarnaan sisi. Bukti dari batas (2.3.1) yang dikemukakan oleh Hakimi

17


Gambar 2.14: Graf G dengan χ′f (G) = 4 dan Kariv cukup sulit. Karena pada multiplisitas graf sederhana adalah satu, sehingga untuk graf sederhana berlaku χ′f (G) = ∆f (G) atau ∆f (G) + 1. Nishizeki et al [7], juga memberikan batas atas bagi χ′ f (G), yaitu 9∆f (G) + 6 ′ χ f (G) ≤ max lf (G), 8 dimana lf (G) =

max

H⊆G,n(H)≥3

&

m(H) Σv∈V H f (v) 2

'

.

(2.3.4)

(2.3.5)

(2.3.6)

Pewarnaan sisi merupakan hal khusus dari pewarnaan sisi-f dengan f (v) = 1 untuk setiap titik v ∈ V . Pada pewarnaan sisi, bilangan kromatik sisi dinotasikan χ′ (G). Selanjutnya, pada bagian ini akan dibahas teorema-teorema yang berkaitan dengan pewarnaan sisi. K¨onig telah menunjukkan batas dari χ′ (G) untuk graf bipartit. Teorema 2.2 [8] Jika G adalah graf bipartit, maka χ′ (G) = ∆(G). Selanjutnya, akan diberikan batas bawah dari ∆(G) sehingga χ′ (G) = ∆(G) yang berkaitan dengan a(G), dan a′ (G) pada graf sederhana. Lemma 2.3 [7] Jika uv sisi yang dapat dieliminasi dari sebuah graf sederhana G dan χ′ (G − uv) ≤ ∆(G), maka χ′ (G) = ∆(G). Dengan demikian, jika sisi yang dieliminasi uv dihilangkan dan graf G - uv diwarnai


18

dengan ∆(G) warna maka untuk mewarnai sisi uv tidak diperlukan warna baru. Vizing telah mendapatkan teorema berikut ini. Teorema 2.3 [7] Sebarang graf sederhana taktrivial G memiliki sisi yang dapat dieliminasi jika ∆(G) ≥ 2s(G). Bukti:

Misalkan G = (V, E). Misalkan U = {u ∈ V |d(u, G) ≤ s(G)}. Definisi

degeneracy, menunjukkan bahwa G paling sedikit satu titik yang berderajat ≤ s(G) sehingga U 6= ∅. Lebih jauh, V − U 6= ∅ karena ∆(G) ≥ 2s(G) > s(G) dan sebab itu titik-titik yang berderajat ∆(G) tidak terdapat di U. Dengan demikian, H = G − U tidak kosong dan s(H) ≤ s(G). Oleh karena itu, H memiliki sebuah titik v yang berderajat ≤ s(G). Karena s(G) + 1 ≤ d(v, G) dan d(u, H) ≤ s(G), G memiliki sebuah sisi uv yang berkaitan dengan v ,u ∈ U . Karena u ∈ U, d(u) ≤ s(G) < 2s(G) ≤ ∆. Maka dari itu tidak ada tetangga dari v di U memiliki derajat ∆(G), dan sebab itu d∗u (v) ≤ d(v, H) ≤ s(G). Oleh karena itu, d(u) + d∗u (v) ≤ 2s(G) ≤ ∆(G) dan sisi uv dapat dieliminasi.\\ Teorema 2.4 [8] χ′ (G) = ∆(G) jika ∆(G) ≥ 2s(G). Bukti:

Misalkan G adalah graf taktrivial dengan ∆(G) ≥ 2s(G). Maka dengan

Teorema 2.3 G memiliki sisi yang dieliminasi, misalkan e1 . Misalkan G1 = G − {e1 }, maka s(G1 ) ≤ s(G). Jika ∆(G1 ) = ∆(G), maka G1 memiliki sisi yang dapat dieliminasi, misalkan e2 . Oleh karena itu terdapat sebuah barisan sisi e1 , e2 , ..., ej sehingga • ∆(Gj ) = ∆(G) − 1 dimana Gj = G − {e1 , e2 , ...ej }; dan • setiap sisi ei , 1 ≤ i ≤ j, dapat dieliminasi di Gi−1 = G − {e1 , e2 , ..ei−1 }. Dengan Teorema Vizing, χ′ (Gj ) ≤ ∆(Gj )+1 = ∆(G). Maka dari itu, dengan menggunakan Lemma 2.3 secara berulang, akan didapat χ′ (G) = ∆(G).\\ Teorema 2.5 Misalkan Fn adalah graf kipas dengan n > 2 maka χ′ (Fn ) = ∆(Fn ).


19

Bukti: Jika Fn adalah graf kipas dengan n = 2, maka Fn merupakan 2-teratur dengan banyaknya titik 3. Sehingga tidak mungkin untuk diwarnai dengan dua warna. Misalkan Fn adalah graf kipas dengan n > 2 dan setiap sisinya akan dipetakan ke himpunan warna {1,2,...,∆(Fn )}. Misalkan titik w merupakan titik dasar dari graf Fn dan v1 , v2 , ..., vn merupakan titik-titik pada graf lintasan Pn . Misalkan sisi-sisi E = e1 , e2 , ..., e2n−1 pada Fn diurutkan sebagai berikut. e1 , e2 , ..., en−1 merupakan sisi pada graf lintasan Pn , dan sisanya adalah sisi yang terkait denga w. Tanpa mengurangi keumuman, diasumsikan ∆(Fn ) = d(w). Kemudian, akan dikonstruksi pewarnaan sisi pada graf kipas dengan ∆(Fn ) warna. Pertama-tama warnai terlebih dahulu seluruh sisi yang berkaitan dengan w dengan warna terkecil sehingga warna yang terpakai adalah ∆(Fn ). Kemudian warnai sisi-sisi pada graf lintasan e1 , e2 , ..., en−3 dengan warna i + 2, i = 1, 2, .., n − 3 dan warna 1 dan 2 pada sisi en−2 dan en−1 . Sehingga, sisi pada graf lintasan dapat diwarnai dengan ∆(Fn ) − 1 warna dan sisi yang terkait dengan w dapat diwarnai dengan ∆(G) warna. Jadi, Fn dapat diwarnai dengan ∆(Fn ) warna.\\ Teorema 2.6 Misalkan Wn adalah graf roda dengan n > 2 maka χ′ (Wn ) = ∆(Wn ). Bukti:

Cara mengkonstruksi pewarnaan sisi pada Wn mirip dengan konstruksi

pewarnaan sisi pada graf kipas Fn pada bukti dari Teorema 2.5, yaitu dengan mewarnai terlebih dahulu sisi yang terkait dengan titik dasar dengan ∆(Wn ) warna. Tetapi, sisi-sisi pada graf lingkaran diwarnai dengan ∆(Wn ) warna karena pada graf lingkaran terdapat n sisi. Sehingga Wn dapat diwarnai dengan ∆(Wn ) warna.\\ Dari Teorema 2.4 dan Lemma 2.1 didapat akibat sebagai berikut. Akibat 2.1: χ′ (G) = ∆(G) jika salah satu dibawah ini berlaku: 1. ∆(G) ≥ 4a(G) − 2; 2. ∆(G) ≥ 4a′ (G); 3. G adalah graf kipas Fn dan n > 2 4. G adalah graf roda Wn dan n > 2

20


2.4

Reduksi Pewarnaan Sisi-f

Pada bagian ini akan ditunjukkan bahwa permasalahan pewarnaan sisi-f pada suatu graf sederhana G dapat direduksi menjadi permasalahan pewarnaan sisi biasa dengan graf baru Gf . Tanpa mengurangi keumuman, diasumsikan f (v) ≤ d(v) untuk setiap v ∈ V . Untuk setiap v ∈ V , ganti v dengan f (v) salinan v1 , v2 , ..., vf (v) , dan lampirkan d(v) buah sisi yang berkaitan dengan v pada salinan; lampirkan ⌈d(v)/f (v)⌉ atau ⌊d(v)/f (v)⌋ sisi pada setiap salinan vi , 1 ≤ i ≤ f (v). Misalkan Gf adalah graf hasil dari operasi tersebut. Perhatikan bahwa konstruksi dari Gf tidak tunggal. Gambar 2.15 mengilustrasikan G dan contoh konstruksi dari Gf . Karena pewarnaan sisi dari Gf menyebabkan pewarnaan sisi-f dari G yang sama dalam banyaknya warna yang dipakai, maka akan didapat χ′ f (G) ≤ χ′ (Gf ).

(2.4.1)

Persamaan (2.4.1) tidak selalu berlaku dalam kesamaan. Perhatikan Gambar 2.15. Pada graf G , χ′f (G) = 2 yang ditunjukkan oleh dua warna, yaitu hitam dan biru. Sedangkan pada graf Gf , χ′ (Gf ) = 3 yang ditunjukkan oleh warna hitam, biru dan merah. Jelas, ∆(Gf ) = ∆f (G) = maxv∈V ⌈d(v)/f (v)⌉. Jika G adalah graf sederhana, maka Gf sederhana juga dan karenanya, χ′ (Gf ) ≤ ∆(Gf ) + 1 = ∆f (G) + 1. Sehingga pewarnaan sisi dari Gf dengan χ′ (Gf ) warna tidak selalu menghasilkan sebuah pewarnaan sisi-f dari G dengan χ′ f (G) warna tetapi menghasilkan sebuah solusi yang mendekati solusi optimal dari pewarnaan sisi-f dari G dengan paling banyak ∆f (G) + 1 warna. Banyaknya sisi di Gf sama dengan G tetapi banyaknya titik di Gf bertambah menP jadi v∈V f (v)(≤ 2m).

Lemma 2.4 [7] Untuk suatu graf G terdapat Gf sehingga 1. Gf bipartit jika G bipartit; 2. s(Gf ) ≤ s(G);


21

3. a(Gf ) ≤ a(G); dan 4. a′ (Gf ) ≤ a′ (G);

Gambar 2.15: Reduksi graf Diketahui juga bahwa χ′ (G) = ∆(G) jika G adalah graf bipartit dan χ′ (G) = ∆(G) jika G graf planar dengan ∆(G) ≥ 8. Karena itu dengan Teorema 2.5 , Akibat 2.1, Lemma 3.1 didapat teorema berikut ini. Teorema 2.7 [7] χ′f (G) = ∆f (G) jika salah satu dari (1)-(8) berlaku: 1. G adalah bipartit; 2. ∆f (G) ≥ 2s(G); 3. ∆f (G) ≥ 4a(G) − 2; dan 4. ∆f (G) ≥ 4a′ (G);


2.5 2.5.1

22

Kompleksitas Komputasi Analisis algoritma

Secara intuitif, algoritma adalah sebuah himpunan peraturan atau prosedur berhingga yang harus diikuti dalam menyelesaikan suatu permasalahan. Sebuah algoritma yang mengandung peraturan-peraturan akan berhenti dengan sukses setelah melewati beberapa langkah sehingga dapat mengubah masukan menjadi keluaran yang merupakan solusi dari masalah atau gagal setelah menolak masukan yang diberikan. Selain itu, sebuah algoritma juga dapat tidak berhenti atau dalam kata lain, berjalan selamanya.

Gambar 2.16: Algoritma RataRataPrefix1

Keistimewaan dari sebuah algoritma dapat dinilai dari efisiensi waktu jalannya. Waktu jalan sebuah algoritma bergantung pada perangkat lunak dan perangkat keras yang digunakan untuk menjalankannya sehingga waktu jalan sebuah algoritma akan berbeda jika digunakan pada perangkat lunak atau perangkat keras yang berbeda. Akibatnya, analisis secara teoritis yang tidak bergantung pada perbedaan penggunaan perangkat lunak atau perangkat keras dikembangkan untuk menghitung waktu jalan dari sebuah algoritma.

23


Waktu jalan dari sebuah algoritma dapat dilihat sebagai sebuah fungsi h yang memetakan setiap masukan x dalam suatu daerah asal yang ditentukan ke sebuah keluaran h(x) dalam suatu daerah hasil yang diberikan. Rata-rata waktu jalan dari sebuah algoritma seringkali sulit untuk didapat, sehingga analisis waktu jalan algoritma lebih difokuskan pada analisis waktu terburuk dari sebuah algoritma. Algoritma RataRataPrefix1 pada Gambar 2.16 memiliki n+n+n+(1+2+...+(n− 1)) + (1 + 2 + ... + (n − 1)) + n (= 4n + n(n − 1)) buah operasi. Pengeksekusian setiap operasi berbeda bergantung pada penggunaan memory cells pada RAM (Random Access Machine). Definisikan a sebagai waktu operasi tercepat dan b sebagai waktu operasi terlambat. Misalkan T (n) merupakan waktu jalan terburuk, maka a(4n + n(n − 1)) ≤ T (n) ≤ b(4n + n(n − 1)).

(2.5.1)

Dalam banyak kasus, bentuk tepat dari T (n) sulit untuk dihitung. Karenanya, bentuk tepat dari T (n) diganti dengan orde asimtotiknya, O(g). Untuk sebarang fungsi g : ℵ → ℵ, fungsi kelas O(g) didefinisikan sebagai berikut O(g) = {T : ℵ → ℵ|(∃c > 0)(∃n0 ∈ ℵ)(∀n ≥ n0 )[T (n) ≤ c(g(n))]}.

(2.5.2)

Sebagai contoh, akan dianalisa kelas O(g) dari Algoritma RataRataPrefix1. Sesuai dengan definisi, T (n) ≤ c(g(n)). Sehingga n2 + 3n ≤ c(g(n)).

(2.5.3)

Misalkan g(x) = n2 . Persamaan (2.5.3) menjadi n2 + 3n ≤ c(n2 )

(2.5.4)

(c − 1)n2 ≥ 3n

(2.5.5)

n ≥ 3/(c − 1).

(2.5.6)

Pilih c = 2 dan n0 = 3 sehingga Algoritma RataRataPrefix1 termasuk pada kelas O(n2 ) atau dapat diselesaikan dalam waktu O(n2 ).


24

Sebuah permasalahan dikatakan diselesaikan dalam waktu polinom jika terdapat suatu polinom p sehingga T (|x|) ∈ O(p|x|) untuk semua masukan x pada permasalahan tersebut. Contohnya, jika terdapat suatu k sehingga T (|x|) ∈ O(|x|k ). Masalah pada Algoritma RataRataPrefix1 dapat diselesaikan dalam waktu polinom.

2.5.2

Teori kompleksitas

Suatu masalah dikatakan masalah keputusan jika hanya memiliki dua keluaran yang direpresentasikan dengan {1,0}. Keluaran bisa berupa jawaban {ya,tidak} atau pasangan keluaran lainnya. Contohnya pada permasalahan penentuan bilangan kromatik χ′ (G) dari sebuah graf G . Pada graf sederhana G , bilangan kromatik dari G adalah ∆(G) atau ∆(G)+1. Masalah keputusan pada penentuan bilangan kromatik memiliki dua macam keluaran yaitu {∆(G),∆(G) + 1}. Kelas dari semua masalah keputusan yang dapat diselesaikan dalam waktu polinom dinotasikan dengan P . Ketika sebuah masalah bilangan kromatik diformulasikan sebagai masalah keputusan, terdapat ketidaksimetrisan antara masukan yang menghasilkan keluaran ”ya” dan yang menghasilkan keluaran ”tidak”. Sebuah jawaban”ya” dapat ditandai dengan sebuah informasi: suatu graf G yang memiliki bilangan kromatik ∆(G). Lebih umum, misalkan N P menotasikan suatu kelas masalah keputusan dimana setiap masukan dengan jawaban ”ya” ditandai y, sehingga |y| dibatasi oleh suatu polinom dalam x dan terdapat sebuah algoritma dengan waktu polinom untuk menguji bahwa y adalah tanda yang tepat bagi x. Setiap masalah keputusan yang dapat diselesaikan dalam waktu polinom termasuk ke dalam kelas N P (Nondeterministic Polynomial-time). Jika terdapat sebuah masalah P dan sebuah algoritma yang menghitung setiap masukan x menjadi keluaran h(x) ∈ {ya, tidak} dalam langkah polinom, maka jawaban h(x) dapat digunakan sebagai tanda. Tada ini dapat diperiksa oleh algoritma. Sehingga P juga termasuk ke dalam N P yang mengakibatkan P ⊆ N P .


25

Kelas NP-complete adalah kelas yang paling sulit untuk diselesaikan dalam N P . Konsep NP-complete dikenalkan oleh Stephen Cook dalam sebuah jurnal yang berjudul ”The Complexity of theorem-proving procedurs”. Saat ini, semua algoritma yang telah diketahui yang digunakan untuk masalah NPcomplete memerlukan waktu superpolinom, tergantung dari masukannya. Belum diketahui apakah terdapat algoritma yang lebih cepat. Oleh karena itu, untuk menyelesaikan masalah NP-complete, untuk sebarang masalah taktrivial, beberapa pendekatan digunakan, yaitu: 1. Taksiran: sebuah algoritma yang menemukan solusi suboptimal, yaitu solusi dengan daerah hasil tertentu; 2. Probabilistik: sebuah algoritma yang dapat dibuktikan memberikan kelakuan yang baik dari rata-rata waktu jalan untuk suatu distribusi yang diberikan dari masalah; 3. Kasus-kasus khusus: sebuah algoritma yang dapat berjalan dengan cepat jika masalah termasuk ke dalam suatu kelas khusus yang ditentukan; 4. Heuristik: sebuah algoritma yang bekerja cukup baik dalam banyak kasus, tetapi kecepatan dari algoritma dan ketepatan dari solusi yang dihasilkan tidak terjamin. Untuk dua buah masalah keputusan, misalkan P dan Q, P dikatakan tereduksi menjadi Q(dinotasikan P ∞Q) jika terdapat fungsi g yang dapat dicari dengan waktu polinom yang mengubah masukan untuk P menjadi masukan untuk Q sehingga x adalah masukan dari ”ya” untuk P jika dan hanya jika g(x) masukan ”ya” untuk Q. Garey dan Johnson mengemukakan suatu konjektur bahwa penentuan bilangan kromatik sisi dari suatu graf termasuk ke dalam kelas NP-complete. Kemudian, Ian Hoyler telah membuktikan bahwa permasalahan dalam menentukan bilangan kromatik pada graf 3-teratur adalah 3 atau 4 merupakan masalah NP-complete. Se-


26

hingga tidak terdapat algoritma yang dapat menyelesaikan masalah dalam waktu polinom. Akibatnya, pewarnaan sisi-f termasuk ke dalam kelas, karena pewarnaan sisi merupakan kasus khusus dari pewarnaan sisi-f dimana f (v) = 1 untuk setiap v.

Bab 2 LANDASAN TEORI. 2.1 Definisi Graf

Recommend Documents