Bab 2 LANDASAN TEORI

Bab 2 LANDASAN TEORI Pada bab ini akan dijelaskan mengenai teori – teori yang berhubungan dengan penelitian sehingga dapat dijadikan sebagai landasan berfikir dalam melakukan penelitian dan akan mempermudah dalam hal pembahasan hasil utama pada bab berikutnya.

2.1 Teori

SEJARAH GRAF graf

merupakan

suatu

model

matematika

yang

sangat

pesat

perkembangannya, guna menyelesaikan masalah – masalah di berbagai bidang, khususnya bidang yang mengimplementasikan dengan komputerisasi. Contohnya dibidang elektro, telekomunikasi, teknik sipil, transportasi, ekonomi dan lain – lain.

Pada tahun 1736 seorang matematikawan yang berkebangsaan Swiss bernama Leonhard Euler berhasil mengungkapkan misteri jembatan Konigzberg yang terdapat dikota Konigzberg. Di Rusia mengalir sebuah sungai yang bernama sungai Pregel ditengah – tengah sungai tersebut tedapat dua buah pulau kemudian antara kedua pulau dan kedua tepian sungai tedapat jembatan. Adapun gambarnya sebagai berikut.

Gambar 2.1 Jembatan Konigzberg

Universitas Sumatera Utara

Selanjutnya Euler berpikir untuk menyajikan jembatan Konigzberg

C

A

D

B

kedalam bentuk graf dimana pulau disimbolkan titik dan jembatan disimbolkan sebagai garis. Gambar 2.2. representasi graf dari jembatan Konigzberg

2.2. Konsep dasar Graf Suatu Graf G adalah pasangan berurut dari himpunan verteks dan edge, di tulis G(V,E). Himpunan V = {v1 , v2 , v3 , ... , vn} adalah himpunan berhingga yang elemennya disebut dengan verteks ( node atau point atau titik atau verteks), dan E adalah himpunan bagian dari kumpulan pasangan verteks V yang tidak berurut.

Elemen dari E disebut edges (line atau arc atau garis), E = {v1v2 , v1v3 , ... , v1vj , ... , vivj} , i = 1,...,n-1; j = i+1,...,n atau E = {ei ,e2 , ... , en}. Dua buah verteks vi dan vj dikatakan adjacent jika kedua verteks dihubungkan dengan sebuah edge. Sementara verteks itu disebut incident terhadap edge yang menghubungkan verteks tersebut.

Gambar 2.3 Graf Sederhana


Pada gambar 2.3. adalah suatu representasi dari Graf sederhana, verteks pada Graf tersebut adalah {v1 , v2 , v3 , v4 , v5}. Edgesnya adalah {e12 , e23 , e35 , e45 , e15 , e13 , e14 , e25}. Verteks v1 dan v2 disebut adjacent karena kedua verteks tersebut dihubungkan oleh edge e12, sedangkan v1 disebut incident terhadap e12. Verteks yang dihubungkan oleh edge ke dirinya sendiri disebut loop (gelang). Dalam suatu graf setiap pasangan yang berbeda dapat terdiri dari 2 atau lebih edge disebut dengan edge paralel (edge ganda).

Banyaknya edge yang incident terhadap suatu verteks didalam graf G di mana loop dihitung dua kali disebut dengan degree / valensi / derajat dari verteks tersebut dinotasikan d(v).

Suatu verteks yang berderajat satu dalam graf hamilton akan menjadi verteks awal atau akhir. Sedangkan suatu verteks yang bervalensi nol disebut isolated verteks. 1

1

1

e2

2

4

e3

e1

3

2

G1

e4

5

3

3

e5

2

G2

4

G3

Gambar 2.4. Graf dengan isolated verteks dan loop

Tinjau graf G1: d(1) = d(4) = 2 d(2) = d(3) = 3 Tinjau graf G3: d(5) = 0  verteks terpencil (isolated verteks) d(4) = 1  verteks anting-anting (pendant verteks)


Tinjau graf G2: d(1) = 3 d(2) = 4

 beredgean dengan edge ganda

 beredgean dengan edge gelang (loop)

Pada graf berarah, din(v) = derajat-masuk (in-degree) = jumlah busur yang masuk ke verteks v dout(v) = derajat-keluar (out-degree) = jumlah busur yang keluar dari verteks v 1

2

1

3

2

3

4

4

d(v) = din(v) + dout(v) D4

D5

Gambar 2.5. Digraf dengan din dan dout Tinjau graf D4: din(1) = 2; dout(1) = 1 din(2) = 1; dout(2) = 3 din(3) = 2; dout(3) = 1 din(4) = 1; dout(4) = 2

2.3. Jenis – jenis Graf Berdasarkan ada tidaknya gelang atau edge ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:


1. Graf sederhana (simple Graf). Graf yang tidak mengandung gelang maupun edge-ganda dinamakan graf sederhana.

2. Graf tak-sederhana (unsimple-Graf). Graf yang mengandung edge ganda dan atau gelang dinamakan graf taksederhana (unsimple Graf).

Berdasarkan orientasi arah pada edge, maka secara umum graf dibedakan atas 2 jenis: 1. Graf tak-berarah (undirected Graf) Graf yang edgenya tidak mempunyai orientasi arah disebut graf tak-berarah.

2. Graf berarah (directed Graf atau diGraf) Graf yang setiap edgenya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada Gambar 2.6 adalah graf berarah.

1

2

1

3

2

3

4

(a) D4

4

(b) D5

Gambar 2.6. Digraph (a) graf berarah, (b) graf-ganda berarah

2.4. Lintasan (Walk)


Lintasan yang panjangnya n dari verteks awal v0 ke verteks tujuan vn di dalam graf G ialah barisan berselang-seling verteks-verteks dan edge-edge yang berbentuk v0, e1, v1, e2, v2,... , vn –1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah edge-edge dari graf G. Tinjau graf G1: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan edge (1,2), (2,4), (4,3).

Panjang lintasan adalah jumlah edge dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G1 memiliki panjang 3. Verteks awal dan verteks akhir dalam suatu walk mungkin saja merupakan verteks yang sama maka walk yang demikian disebut dengan closed walk

Trail dari suatu graf adalah suatu walk yang setiap edgenya berbeda. Path dari suatu graf adalah walk yang mana setiap verteksnya berbeda.

2.5. Siklus (Cycle) atau Sirkuit (Circuit)

Lintasan yang berawal dan berakhir pada verteks yang sama disebut sirkuit atau siklus.

Tinjau graf G1: 1, 2, 3, 1 adalah sebuah sirkuit. Panjang sirkuit adalah jumlah edge dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1 memiliki panjang 3. 2.6. Terhubung (Connected)


Graf disebut connected apabila setiap verteks yang berbeda dihubungkan dengan sebuah edge, dan disebut disconnected jika terdapat 2 atau lebih connected Graf. Setiap connected Graf disebut komponen. Dua buah verteks v1 dan verteks v2 disebut terhubung jika terdapat lintasan dari v1 ke v2. G disebut graf terhubung (connected Graf) jika untuk setiap pasang verteks vi dan vj dalam himpunan V terdapat lintasan dari vi ke vj. Jika tidak, maka G disebut graf tak-terhubung (disconnected Graf).

Contoh graf tak-terhubung: 2 5

1

4 6 3

8

7

Gambar 2.7. Disconnected Graf Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G diperoleh dengan menghilangkan arahnya).

Dua verteks, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.

Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly coonected). Graf berarah G disebut graf terhubung kuat (strongly connected Graf) apabila untuk setiap pasang verteks sembarang u dan v di G, terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.


1 1 2

2 3

3

4

Graf berarah terhubung lemah

graf berarah terhubung kuat

Gambar 2.8. Graf Bearah terhubung lemah dan kuat

2.7. Upagraf (SubGraf) dan Komplemen Upagraf

Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf (subGraf) dari G jika V1 ⊆ V dan E1 ⊆ E.

Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan verteks yang anggotaanggota E2 beredgean dengannya.

2

2

1

1

3

3

1 3

6

4

5

6 2

5

5

Gambar 2.9. Upagraf dan Komplemen (a) Graf G1

(b) Sebuah upagraf

(c) komplemen dari

upagraf Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum upagraf yang terhubung kuat.


Graf di bawah ini mempunyai 2 buah komponen terhubung kuat:

1

2

4

3

5

Gambar 2.10. Strongly Connected component

2.8 Deletion

Jika ej ∈ Graf G maka G – ej merupakan suatu subgraf dari graf G yang diperoleh dengan menghapus edge ej. 2.9 Contraction

Jika vi ∈ verteks di graf G maka G – vi adalah subgraf yang diperoleh dengan menghapus verteks vi serta edge yang inciden dengan verteks tersebut. 2.10 Cut-Set

Cut-set dari graf terhubung G adalah himpunan edge yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.


Pada graf di bawah, {(4,5), (4,6) } adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung. 1

5

2

1

5

2

4

4

6 3

6 3

Gambar 2.11. Cut Set

2.11

Beberapa Operasi Dalam Graf

2.11.1 Intersection

Dua buah graf G1 (v1,e1) dan G2 (v2, e2) adalah membentuk suatu graf baru yaitu G3(v3, e3) dimana G3 = G1 ∩ G2, v3 = v1 ∩ v2, dan e3 = e1 ∩ e2 2.11.2 Union

Dua buah graf G1 (v1,e1) dan G2 (v2, e2) adalah membentuk suatu graf baru yaitu G3(v3, e3) dimana G3 = G1 ∪ G2, v3 = v1 ∪ v2, dan e3 = e1 ∪ e2 2.12

Beberapa Graf Sederhana Khusus


2.12.1 Graf Lengkap (Complete Graf)

Graf lengkap ialah graf sederhana yang setiap verteksnya mempunyai edge ke semua verteks lainnya. Graf lengkap dengan n buah verteks dilambangkan dengan Kn. Jumlah edge pada graf lengkap yang terdiri dari n buah verteks adalah n(n – 1)/2.

K1 K2

K3

K4

K5

K6

Gambar 2.12. Graf Lengkap

2.12.2 Graf Lingkaran

Graf lingkaran adalah graf sederhana yang setiap verteksnya berderajat dua. Graf lingkaran dengan n verteks dilambangkan dengan Cn.

Gambar 2.13. Graf Lingkaran

2.12.3 Graf Teratur (Regular Grafs)

Graf yang setiap verteksnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap verteks adalah r, maka graf tersebut


disebut sebagai graf teratur derajat r. Jumlah edge pada graf teratur adalah nr/2. Gambar 2.14. Graf Teratur

2.12.4. Graf Bipartite (Bipartite Graf)

Graf G yang himpunan verteksnya dapat dipisah menjadi dua himpunan bagian V1 dan V2,

sedemikian sehingga setiap edge pada G

menghubungkan sebuah verteks di V1 ke sebuah verteks di V2 disebut graf Bipartite dan dinyatakan sebagai G(V1, V2).

V1

V2

Gambar 2.15. Graf Bipartite

Graf G di bawah ini adalah graf bipartit, karena verteks-verteksnya dapat dibagi menjadi V1 = {a, b, d} dan V2 = {c, e, f, g} a

b

g

c

f e

d

G Gambar 2.16. Graf Bipartite dengan verteks


2.13

Lintasan dan Sirkuit Euler

Lintasan Euler ialah lintasan yang melalui masing-masing edge di dalam graf tepat satu kali.

Sirkuit Euler ialah sirkuit yang melewati masing-masing edge tepat satu kali. Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian Graf). Graf yang hanya mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian Graf).

Teorema 2.1:

Suatu connected graf G adalah Eulerian graf jika dan hanya jika setiap verteks mempunyai valensi genap.

Bukti:

Jika sebuah graf G mempunyai verteks dengan valensi (derajat) genap semuanya maka dapat dipastikan memiliki Eulerian graf karena dalam setiap Eulerian graf memiliki satu jalur masuk dan satu jalur keluar yang berbeda.

Akibat 2.1:

Suatu connected graf adalah semi Eulerian jika dan hanya jika tidak ada atau ada dua verteks yang berderajat ganjil.

Bukti:


Jika sebuah graf G mempunyai verteks dengan valensi (derajat) genap sebagian atau tidak ada, maka graf tersebut akan mempunyai kemungkinan untuk memiliki Eulerian graf.

a b

d

c

d

c

a

b

a

b

g

f

c e

d (a)

(b)

(c)

Gambar 2.17 Euler Digraf (a) Graf berarah Euler (a, g, c, b, g, e, d, f, a) (b) Graf berarah semi-Euler (d, a, b, d, c, b) (c) Graf berarah bukan Euler maupun semi-Euler

2.14

Lintasan dan Sirkuit Hamilton

Lintasan Hamilton ialah lintasan yang melalui tiap verteks di dalam graf tepat satu kali.

Sirkuit Hamilton ialah sirkuit yang melalui tiap verteks di dalam graf tepat satu kali, kecuali verteks asal (sekaligus verteks akhir) yang dilalui dua kali.Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.


1

2

1

2

1

2

4

3

4

3

4

3

(a)

Gambar 2.18

(b)

(c)

Hamiltonian Graf (a) graf yang memiliki lintasan Hamilton (misal: 3, 2, 1, 4) (b) graf yang memiliki sirkuit Hamilton (1, 2, 3, 4, 1) (c) graf yang tidak memiliki lintasan maupun sirkuit Hamilton 1 6 15 5

12

2 8

19 13

7

16

20

14

17 18 11

9 10 3

4

Gambar 2.19 Prominent Cities Dalam Graf (a) Dodecahedron Hamilton, dan (b) graf yang mengandung sirkuit Hamilton


Teorema 2.2: Syarat cukup (jadi bukan syarat perlu) supaya graf sederhana G dengan n (≥ 3) buah verteks adalah graf Hamilton ialah bila derajat tiap verteks paling sedikit n/2 (yaitu, d(v) ≥ n/2 untuk setiap verteks v di G). Bukti:

Telah dibuktikan dan menjadi rumusan yang general oleh Dirac. Dan dikenal dengan teorema Dirac.

Teorema 2.3:

Setiap graf lengkap adalah graf Hamilton.

Bukti:

Misalkan setiap verteks diberi penomoran, v1,v2,v3,...,vn. Untuk setiap graf lengkap pasti selalu memiliki edge yang akan menghubungkan setiap titik dalam graf tersebut. Maka kita bisa memulai menyelesaikan graf hamilton dimulai dengan v1 lalu ke v2 lalu ke v3 sampat vn. Maka ini didapatkan sebuah graf hamilton.

Beberapa graf dapat mengandung sirkuit Euler dan sirkuit Hamilton sekaligus, mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton, mengandung sirkuit Euler dan lintasan Hamilton, mengandung lintsan Euler


maupun

lintasan

Hamilton,

tidak

mengandung lintasan

Euler namun

mengandung sirkuit Hamilton, dan sebagainya. 2.15

Knight’s Tour

Permasalahan menarik yang terkait dengan Siklus Hamilton adalah perjalanan kuda (Knight’s Tour). Suatu Knight’s Tour pada papan catur adalah rangkaian perjalanan kuda catur pada papan catur sehingga seluruh kotak terlewati kuda tepat satu kali.

Aturan langkah kuda pada permainan catur adalah sebagai berikut : • Melangkah dua kotak ke arah horisontal kemudian satu persegi ke arah vertikal, •

Melangkah dua kotak ke arah vertikal kemudian satu persegi ke arah

horizontal.

Jika dalam Knight’s Tour setiap persegi dari papan catur dapat dilewati tepat satu kali dan kuda kembali pada persegi semula maka disebut langkah kuda tertutup (Closed Knight’s Tour). Namun, jika semua persegi telah dilewati dan kuda tidak dapat kembali ke posisi semula maka disebut langkah kuda yang terbuka (Open Knight’s Tour). Teorema 2.4:

Sebuah Graf G tidak memiliki Hamiltonian Path jika jumlah verteks yang berdegree satu lebih dari satu, tanpa melihat degree dari verteks awal.

Bukti:

Jika dalam graf G ada 1 buah verteks yang berdegree satu maka verteks tersebut akan menjadi verteks akhir dari Knight’s tour. Jika dalam graf G ada 2 buah atau lebih verteks yang berdegree satu maka tidak akan terjadi knight’s tour.


Bab 2 LANDASAN TEORI

Recommend Documents