BAB II LANDASAN TEORI

5

BAB II

LANDASAN TEORI

2.1

Sejarah Graf

Menurut catatan sejarah, masalah jembatan KÖnigsberg adalah masalah yang pertama kali menggunakan graf (tahun 1736). Di kota KÖnigsberg (sebelah timur Negara bagian Prussia, Jerman), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai.

Gambar 2.1 Jembatan dan Graf yang merepresentasikan jembatan KÖnigsberg

Universitas Sumatera Utara

6

Ada tujuh buah jembatan yang menghubungkan daratan yang dibelah oleh sungai tersebut (Gambar 2.1(a)). Masalah jembatan KÖnigsberg adalah apakah mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula. Sebagian penduduk kota sepakat bahwa memang tidak mungkin melalui setiap jembatan itu hanya sekali dan kembali lagi ke tempat asal mula keberangkatan, tetapi mereka tidak dapat menjelaskan mengapa demikian jawabannya, kecuali dengan cara coba-coba. Tahun 1736, seorang matematikawan Swiss, L.Euler, adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan pembuktian yang sederhana. Ia memodelkan masalah ini ke dalam graf. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakannya sebagai titik (noktah) yang disebut simpul (vertex) dan jembatan dinyatakan sebagai garis yang disebut sisi (edge). Setiap titik diberi label huruf A, B, C, dan D. Graf yang dibuat oleh Euler diperlihatkan pada Gambar 2.1(b). Jawaban yang dikemukakan oleh Euler adalah orang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembal lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya genap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh, simpul C memiliki derajat 3 karena ada 3 buah garis yang bersisian dengannya, simpul B dan D juga berderajat 3, sedangkan simpul A berderajat 5. karena tidak semua simpul berderajat genap, maka tidak mungkin dilakukan perjalanan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut.

2.2

Teori Graf

Sebelum sampai pada pendefinisian masalah eksentrisitas, terlebih dahulu pada bagian ini akan diuraikan mengenai konsep- konsep dasar dari model graf. sebuah graf G adalah pasangan (V,E) dimana V adalah himpunan tak kosong yang anggotanya disebut verteks dan E adalah himpunan yang anggotanya adalah pasangan tak berurut dari verteks V yang disebut edge. Secara umum graf dapat digambarkan dengan suatu diagram dimana verteks ditunjukkan sebagai titik yang dinotasikan dengan vi , i = 1, 2, …, P dan edge digambarkan dengan sebuah garis lurus atau garis lengkung yang menghubungkan dua


7

verteks (vi, vj) dan dinotasikan dengan ek. sebagai ilustrasi dapat dilihat gambar 2.2 yaitu suatu graf yang mempunyai lima verteks dan enam edge.

Gambar 2.2 Graf dengan lima verteks dan enam edge

2.2.1 Definisi dan Notasi Sisi yang menghubungkan dua titik yang sama,yakni e = vv disebut loop. Jika terdapat lebih dari satu sisi yang menghubungkan dua titik, maka sisi tersebut dinamakan sisi rangkap (multiple edge). Pada gambar 2.3 sisi e3 adalah loop dan sisi e1, e2 adalah sisi rangkap. Graf yang tidak mempunyai loop dan sisi rangkap disebut graf sederhana.

Order n dari graf G adalah banyaknya titik di G, yakni n = │V│. Graf yang order-nya hingga disebut dengan graf hingga.

Gambar 2.3 Graf yang memuat loop dan sisi rangkap


8

Jalan (walk) W dengan panjang n dari titik a ke b pada graf G adalah barisan titik a = v0, e1, v1, e2, v2, e3, v3, …, vn-1, en, vn = b (n ≥ 0) yang terdiri dari titik dan sisi di G yang diawali dan diakhiri dengan titik, sedemikian hingga (vi, vi+1) adalah sisi di

G untuk setiap i = 0, 1, 2, …, n-1. Jalan ini menghubungkan titik v0 dan vn, dan dapat juga dinotasikan sebagai v0, v1,…, vn. Jalan dikatakan tertutup jika a = b dan terbuka jika a ≠ b. Sebagai contoh pada Gambar 2.4, x-w-y-v-u-x adalah jalan tertutup dengan panjang 5 dan u-v-w-x-u-v-y adalah jalan terbuka dengan panjang 6. Jejak (trail) adalah jalan dimana tidak ada sisi yang berulang. Jalan dikatakan lintasan (path) jika semua titiknya berbeda. Lintasan adalah jejak, akan tetapi tidak semua jejak adalah lintasan. Sedangkan lintasan tertutup dinamakan siklus (cycel). Pada gambar 2.4, jalan x-w-v-u-w-y adalah jejak tetapi bukan lintasan, sedangkan u-x-w-v-y adalah lintasan, dan u-w-y-v-u adalah siklus.

u

e1

v

Gambar 2.4 Walk pada graf Misal pada graf G terdapat 2 titik vi dan vj , dua buah titik pada graf G dikatakan berdekatan (adjacent) bila keduanya terhubung langsung dengan sebuah sisi. Atau dapat ditulis singkat dengan notasi e = (vi , vj) Є E (G). Diberikan graf G dan {vi , vj} Є v (G) , jika e = (vi , vj) Є E (G). maka dikatakan

e insiden ( incident) dengan titik vi atau e incident dengan titik vj . Derajat (degree) sebuah titik v pada sebuah graf G yang dituliskan dengan deg (v ) adalah banyak sisi yang insiden pada v , dengan kata lain banyak sisi yang


9

memuat v sebagai titik ujung. Derajat minimal pada suatu graf G dinotasikan δ, sedangkan derajat maksimal pada graf G dinotasikan dengan ∆. Misal terdapat dua buah titik u dan v di dalam graf, dimana u dan v saling berdekatan. Jika sisi e insiden terhadap titik u dan v , maka titik u dan v disebut

endpoint dari sisi e.

Gambar 2.5 Graph G Graph G memuat V (G) = {v1 , v2 , v3 , v4 , v5} dan

E (G) = {e1 , e2 , e3 , e4 , e5 , e6 , e7} (i) Pada graf G , titik v2 dan titik v3 merupakan titik yang berdekatan, sedangkan titik

v2 dan titik v4 bukan merupakan titik yang berdekatan. (ii) Pada graf G , sisi e3 insiden dengan titik v2 dan titik v3 , tetapi tidak terdapat sisi yang insiden dengan titik v2 dan titik v4 . (iii) Pada graf G , titik v2 dan titik v3 merupakan endpoint dari sisi e3 . (iv) Pada graf G , deg (v3 ) = 5, deg (v4 ) = 2, dan deg (v5 ) = 0 2.2.2 Macam-macam graf Berdasarkan sifatnya graf dapat dikelompokkan menjadi beberapa kategori (jenis) bergantung pada sudut pandang pengelompokannya. Pengelompokan graf dapat dipandang berdasarkan jumlah simpul yang dimilikinya, arah dan bobotnya, ada tidaknya sisi ganda.


10

Berdasarkan jumlah simpul yang dimilikinya, graf digolongkan menjadi dua jenis: 1. Graf berhingga (limited graph) yaitu graf yang memilki jumlah simpul berhingga.

Gambar 2.6 Graf berhingga 2. Graf tak berhingga (unlimited graph) yaitu graf yang jumlah simpulnya tak berhingga. Secara geometris graf tak berhingga digambarkan dengan sisi–sisi yang hanya memiliki satu simpul untuk setiap simpul luarnya. Sekilas nampak seperti graf yang belum selesai digambar.

Gambar 2.7 Graf tak berhingga.


11

Berdasarkan arah dan bobotnya, graf digolongkan menjadi empat jenis, yaitu: 1. Graf berarah dan berbobot: tiap busur mempunyai anak panah dan bobot. Gambar 2.8 menunjukkan graf berarah dan berbobot yang terdiri dari tujuh titik yaitu titik A,B,C,D,E,F,G. Titik A menunjukkan arah ke titik B dan titik C, titik B menunjukkan arah ke titik D dan titik C, dan seterusnya. Bobot antar titik A dan titik B pun telah di ketahui.

2 E

B 2

3

2

1 2

1 A

D

G 2

1 4

-

C

F

3

4

Gambar 2.8 Graf berarah dan berbobot 2. Graf tidak berarah dan berbobot: tiap busur tidak mempunyai anak panah tetapi mempunyai bobot. Gambar 2.9 menunjukkan graf tidak berarah dan berbobot. Graf terdiri dari tujuh titik yaitu titik A,B,C,D,E,F,G. Titik A tidak menunjukkan arah ke titik B atau C, namun bobot antara titik A dan titik B telah diketahui. Begitu juga dengan titik yang lain.


12

2 B

E

2

2

3

1

1

A

2

D

G 2

1

4 C

F

3

4

Gambar 2.9 Graf tidak berarah dan berbobot 3. Graf berarah dan tidak berbobot: tiap busur mempunyai anak panah yang tidak berbobot. Gambar 2.10 menunjukkan graf berarah dan tidak berbobot.

B

A

E

D

C

G

F

Gambar 2.10 Graf berarah dan tidak berbobot 4. Graf tidak berarah dan tidak berbobot: tiap busur tidak mempunyai anak panah dan tidak berbobot.


13

B

A

E

D

C

G

F

Gambar 2.11 Graf tidak berarah dan tidak berbobot Berdasarkan jenis sisinya graf digolongkan menjadi dua jenis: 1. Graf sederhana yaitu graf yang tidak memiliki sisi ganda maupun loop.

Gambar 2.12 Graf sederhana. 2. Graf tidak sederhana yaitu graf yang memiliki sisi ganda maupun loop. Graf ini dibedakan menjadi dua yaitu: a. Graf ganda yaitu graf yang memiliki sisi ganda. Sisi ganda adalah sekumpulan sisi yang menghubungkan sepasang simpul yang sama.

Gambar 2.13 Graf ganda


14

b. Graf semu yaitu graf yang memiliki sisi loop. Loop adalah sisi yang menghubungkan sebuah simpul dengan dirinya sendiri.

Gambar 2.14 Graf semu

2.3

Graf Cycel (sikel)

Cycel (siklus) atau Sirkuit (Circuit) adalah lintasan yang berawal dan berakhir pada simpul yang sama. Panjang sirkuit adalah jumlah sisi di dalam sirkuit tersebut, pada Gambar 2.15 sirkuit memiliki panjang 3, sebuah sirkuit dikatakan sirkuit sederhana (simple circuit) jika setiap sisi yang dilalui berbeda. Pada Gambar 2.15. 1, 2, 3, 1 adalah sirkuit sederhana sedangkan 1, 2, 4, 3, 2, 1 bukan sirkuit sederhana karena sisi 1, 2 dilalui dua kali. 1

2

3

4

Gambar 2.15 Graf Sikel


15

Graf cycel (sikel) ialah graf yang terdiri dari satu sikel. Graf sikel dengan n titik dinotasikan dengan Cn. Pada graf sikel, jumlah titiknya minimal 3. contoh Graf sikel diberikan pada Gambar 2.16.

Gambar 2.16 Graf sikel


16

2.4

Graf Lintasan (Path)

Lintasan (path) yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi yang terbentuk v0, e1, v1,

e2, v2,..., vn-1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2),... , en = (vn-1, vn) adalah sisi-sisi dari graf G. Jika graf yang ditinjau adalah graf sederhana, maka kita cukup menuliskan lintasan sebagai barisan simpul-simpul saja v0, v1, v2, ..., vn-1, vn, karena antara dua buah simpul berturutan di dalam lintasan tersebut hanya ada satu sisi.Sebagai contoh pada Gambar 2.15 lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3). Sebuah lintasan dikatakan lintasan sederhana (simple path) jika semua simpulnya berbeda (setiap sisi yang dilalui hanya satu kali). Lintasan yang berawal dan berakhir pada simpul yang sama disebut lintasan tertutup (closed path), sedangkan lintasan yang tidak berawal dan berakhir pada simpul yang sama disebut lintasan terbuka (open path). Panjang lintasan adalah jumlah sisi dalam lintasan tersebut . Contoh lintasan sederhana, lintasan tertutup, lintasan terbuka dan panjang lintasan diberikan pada Gambar 2.15 adalah sebagai berikut: Lintasan 1, 2, 4, 3 adalah lintasan sederhana, juga lintasan terbuka. Lintasan 1, 2, 4, 3, 1 adalah juga lintasan sederhana, dan lintasan tertutup. Lintasan 1, 2, 4, 3, 2 bukan lintasan sederhana, tetapi lintasan terbuka. Lintasan 1, 2, 4, 3 memiliki panjang 3. Graf lintasan (path) ialah graf yang terdiri dari satu lintasan. Graf lintasan dengan n titik, dinotasikan dengan Pn, contoh dari graf lintasan diberikan pada Gambar 2.17.


17

P1

:

v1 P2

:

v1 P3

v2

:

v1

v2

v3

Gambar 2.17 Graf lintasan

2.5

Graf n-partit

Graf n – partit di definisikan sebagai graf dimana himpunan titik V(G) dapat di pisah menjadi n himpunan titik, yaitu V1(G), V2(G),...,Vn(G). Sisi-sisi pada graf n-partit terhubung dari titik-titik pada Vi(G) ke titik-titik pada himpunan titik selain Vi(G) atau Vi (G ) , dimana Vi (G ) adalah komplemen dari Vi(G). Untuk n = 2, dinamakan graf

bipartit. Jika V1 = k dan V 2 = l , maka graf bipartit tersebut dinotasikan dengan Bk,l. Sedangkan untuk n = 3, dinamakan dengan graf tripartit, yang dinotasikan dengan Tk,l,m. 2.6

Lintasan Terpendek (Short Path)

Persoalan mencari lintasan terpendek di dalam graf merupakan salah satu persoalan optimasi. Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan,dan sebagainya. Asumsi yang kita gunakan disini adalah bahwa semua bobot bernilai posotif. Kata ”terpendek” jangan selalu diartikan secara fisik sebagai panjang minimum, sebab kata ”terpendek” berbeda-beda maknanya bergantung pada tipikal persoalan yang akan diselesaikan. Namun secara umum ”terpendek” berarti meminimasi bobot pada suatu lintasan di dalam graf.


18

Ada beberapa macam persoalan lintasan terpendek, antara lain: a. Lintasan terpendek antara dua buah simpul tertentu, b. Lintasan terpendek antara semua pasangan simpul, c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain, d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu. Pada dasarnya, jenis persoalan a mirip dengan persoalan c, karena pencarian lintasan terpendek pada jenis persoalan c dapat dihentikan bila simpul tujuan yang dikehendaki sudah ditemukan lintasan terpendeknya.

2.7

Eksentrisitas Digraf

Eksentrisitas ec(v) pada titik v dalam graf G adalah jarak terjauh (maksimal lintasan terpendek) dari titik v ke setiap titik di G, dapat dituliskan ec(v) = max = {d(v,u) ‫ ׀‬u Є V(G}. Radius r(G) dari G adalah eksentrisitas minimum pada setiap titik di G, dapat dituliskan r(G) = min {ec(v) ‫ ׀‬v Є V} dan diameter dari G dinotasikan diam (G) adalah eksentrisitas maksimum pada setiap titik di G, dapat dituliskan dim(G) = maks {ec(v) ‫׀‬

v Є V}, titik v disebut titik central jika ec(v) = r(G), center dinotasikan cen(G) adalah subgraf pada G yang terbentuk dari titik central. Titik v dikatakan titik eksentrik dari u jika jarak dari v ke u sama dengan titik eksentrik dari u, dapat dituliskan d(v,u) = ec(u). Eksentrisitas digraf diperkenalkan pertama kalinya oleh Fred Buckley pada tahun 90-an. Eksentrisitas Digraf ED(G) didefinisikan sebagai graf yang mempunyai himpunan titik yang sama dengan himpunan titik di G atau V(ED(G)) = V(G), dimana arc menghubungkan titik u ke v jika v adalah titik eksentrik dari u. Buckley menyimpulkan bahwa hampir setiap graf G, eksentrik digrafnya adalah ED(G) = (G)*, dimana (G)* adalah komplemen dari G yang setiap sisinya diganti dengan arc simetrik. Contoh eksentrisitas titik, titik eksentrik, radius, diameter, center dan eksentrisitas digraf adalah sebagai berikut:


19

Gambar 2.18 Eksentrisitas Titik

Eksentrisitas

Titik Eksentrik

a

ec(a) = 3

f

b

ec(b) = 2

c,f

c

ec(c) = 3

f

d

ec(d) = 2

a,f

e

ec(e) = 2

a,c

f

ec(f) = 3

a,c

Tabel 2.1 Eksentrisitas dan titik eksentrik Jadi r(G) = 2, diam(G) = 3, cen(G) = b e d

v a

b e

c

f

d

Gambar 2.19 Eksentrisitas Digraf


BAB II LANDASAN TEORI

Recommend Documents