Graf Oleh: Panca Mudjirahardjo
Pendahuluan
Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.
1
Pendahuluan
Jaringan jalan raya di propinsi Jawa Tengah
1. Sejarah Graf
Masalah jembatan Kőnigsberg adalah masalah yang pertama kali menggunakan graf (1736). Masalahnya adalah: apakah mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula?
2
2. Definisi Graf
Graf G didefinisikan sebagai pasangan himpunan (V,E) dimana:
V
: himpunan berhingga dan tidak kosong dari simpul-simpul (vertices atau node) : {v1, v2,….., vn}
E
: himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. : {e1, e2,….., en}
2. Definisi Graf (lanjutan) Graf sederhana G1 adalah graf dengan himpunan simpul V dan himpunan sisi E, dimana:
V
= {1,2,3,4}
E = {(1,2),(1,3),(2,3),(2,4),(3,4)}
3
2. Definisi Graf (lanjutan)
Graf ganda G2 adalah himpunan simpul V dan himpunan sisi E, dimana:
V = {1,2,3,4}
E = {(1,2),(2,3),(1,3),(1,3),(2,4),(3,4)(3,4)}
2. Definisi Graf (lanjutan)
Graf semu G3 adalah himpunan simpul V dan himpunan sisi E, dimana:
V = {1,2,3,4}
E = {(1,2),(2,3),(1,3),(1,3),(2,4),(3,4),(3,4),(3,3)}
4
3. Jenis-jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, graf dibedakan:
Graf
sederhana (simple graph) (G1)
Graf tak sederhana (unsimple graph) (G2, G3)
3. Jenis-jenis Graf (lanjutan)
Berdasarkan jumlah simpul, graf dibedakan:
Graf
berhingga (limited graph)
Graf tak-berhingga (unlimited graph)
5
3. Jenis-jenis Graf (lanjutan)
Berdasarkan orientasi arah pada sisi, graf dibedakan:
Graf tak berarah (undirected graph)
Graf berarah (directed graph atau digraph)
3. Jenis-jenis Graf (lanjutan)
Jenis graf
Sederhana Ganda Semu Berarah Ganda berarah
Sisi
tak-berarah tak-berarah tak-berarah berarah berarah
Sisi ganda dibolehkan? tidak ya ya tidak ya
Sisi gelang dibolehkan? tidak tidak ya ya ya
6
Contoh Terapan Graf Rangkaian Listrik Isomer senyawa kimia karbon Transaksi konkuren pada basis data Pengujian program Terapan graf pada teori otomata Turnamen round-robin
Terminologi Graf
(1) Ketetanggaan (adjacent) Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung. Simpul 3 bertetangga dengan simpul 1,2, dan 4
7
Terminologi Graf (lanjutan)
(2) Bersisian (Iicidency)
Untuk sembarang sisi e = (vj,vk) dikatakan
e bersisian dengan simpul vj, atau e bersisian dengan simpul vk.
Contoh: sisi (2,4) bersisian dengan simpul 2 dan simpul 4.
Terminologi Graf (lanjutan)
(3) Simpul Terpencil (Isolated Vertex) Adalah simpul yang tidak mempunyai sisi yang bersisian dengannya. Contoh: simpul 5 adalah simpul terpencil.
8
Terminologi Graf (lanjutan)
(4) Graf Kosong Definisi graf menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Contoh: Graf kosong N5
.1 .4 .5 .2 .3
Terminologi Graf (lanjutan)
(5) Derajat (Degree) Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut. Notasi : d(v) Contoh: d(2) = d(3) = 3 dan d(1) = d(2) = 2
9
Terminologi Graf (lanjutan)
(5) Derajat (Degree) Jika terdapat g buah gelang dan e buah sisi bukan gelang yang bersisian dengan simpul v, d(v) = 2g + e Contoh: d(3) = 2(1)+2 = 4
Terminologi Graf (lanjutan)
(5) Derajat (Degree) Pada graf berarah dibedakan menjadi dua macam: din(v) = jumlah busur yang masuk ke simpul v dout(v) = jumlah busur yang keluar dari simpul v d(v) = din(v) + dout(v) Contoh: din(3) = 3, dout(3) = 4
10
Terminologi Graf (lanjutan)
(5) Derajat (Degree) Untuk graf berarah: ∑ din(v) =∑ dout(v)=|E| Contoh: din(1)+ din(2)+ din(3)+ din(4)= dout(1)+ dout(2)+ dout(3)+ dout(4) 3+1+3+2 = 1+2+4+2 = 9
Terminologi Graf (lanjutan)
(5) Derajat (Degree) Untuk graf sembarang: ∑ d(v) =2|E| Contoh: d(1)+ d(2)+ d(3)+ d(4)= 4 + 3 + 7 + 4 = 18 = 2(9)
11
Terminologi Graf (lanjutan)
(6) Lintasan (Path) Sederhana: lintasan dengan semua sisi yang dilalui hanya sekali Elementer: lintasan dengan semua simpul yang dilalui hanya muncul sekali, kecuali, mungkin simpul pertama & simpul terakhir Tertutup: berawal dan berakhir pada simpul yang sama Terbuka: berawal dan berakhir pada simpul yang tak sama
Terminologi Graf (lanjutan)
(7) Siklus atau Sirkuit Adalah: lintasan elementer dengan simpul pertama sama dengan simpul terakhir Contoh : Panjang sirkuit: jumlah sisi dalam sirkuit tersebut,
12
Under
construct
Terima kasih
13
