Tugas Mandiri

Ringkasan Materi Graf

Mata Kuliah: Matematika Diskrit

Nama Mahasiswa : Kelvin

NPM : 123410004

Dosen :Ary Prasetyo, S.T.

UNIVERSITAS PUTERA BATAM

2013

KATA PENGANTAR

Marilah kita panjatkan puji dan syukur kepada Tuhan Yang Maha Esa

karena berkat dan rahmat yang diberikan sehingga tugas makalah yang berisi

tentang Algoritma dan Pemograman ini dapat terselesaikan tepat pada waktunya.

Dalam makalah ini, dibahas secara dasar mengenai graf, beberapa graf

khusus, representasi graf, graf isomorfik, graf planar dam, graf bidang, teorema

kuratowski, lintasan dan sirkuit Euler, lintasan dan sirkuit Hamilton, dan beberapa

aplikasi graf yang diharapkan akan menambah wawasan bagi mahasiswa dan

setiap orang yang membacanya.

Ibarat peribahasa ‘Tiada Gading Yang Tak Retak’ penulis menyadari bahwa

makalah ini jauh dari sempurna, maka kritik dan saran yang bersifat membangun

akan penulis terima dengan segenap kerendahan hati. Semoga makalah ini dapat

bermanfaat bagi setiap orang yang membacanya. Sekian dan terima kasih.

Batam,10 Januari 2013

Penyusun

Kelvin

ii

DAFTAR ISI

Jilid................................................................................................................... i

Kata Pengantar.................................................................................................. ii

Daftar Isi........................................................................................................... iii

BAB I PENDAHULUAN................................................................................. 1

1.1 Pengertian Graf................................................................................. 1

1.2 Graf sederhana................................................................................... 2

BAB II PEMBAHASAN.................................................................................. 3

2.1 Beberapa Graf Khusus....................................................................... 3

2.2 Representasi Graf............................................................................... 5

2.3 Graf Isomorfik................................................................................... 8

2.4 Graf Planar dan Graf Bidang............................................................. 9

2.5 Teorema Kuratowski......................................................................... 10

2.6 Lintasan dan Sirkuit Euler................................................................. 12

2.7 Lintasan dan Sirkuit Hamilton........................................................... 14

2.8 Beberapa Aplikasi Graf..................................................................... 15

BAB III PENUTUP.......................................................................................... 17

3.1 Kesimpulan........................................................................................ 17

3.2 Saran.................................................................................................. 17

DAFTAR PUSTAKA……………………………………………………......... iv

iii

BAB I

PENDAHULUAN

1.1 Pengertian Graf

Secara sederhana graf didefinisikan sebagai kumpulan titik yang dihubungkan

oleh garis. Secara matematis , graf adalah pasangan dari himpunan (V,E) dimana

V adalah sebuah himpunan tak kosong yang memiliki elemen yang disebut simpul

(verticles) dan E adalah kumpulan dari 2 elemen subset V yang disebut dengan

busur (Edges).

Simpul diwakili menggunakan titik dan busur diwakili menggunakan garis.

Gambar dibawah ini adalah contoh graf (V,E) di mana:

V = {A, B, C, D, E, F}

E = {(A,B), (A,C), (B,D), (C,D), (C,E), (E,F), (E,G)}

Gambar 1.1

Sebuah busur memiliki 2 endpoint atau titik akhir, misalnya busur (E,G) memiliki

endpoint E dan G. Graf biasanya digunakan untuk memodelkan objek-objek

diskrit dan hubungan antar objek-objek tersebut.

1

1.2 Graf Sederhana (Simple Graph)

Graf sederhana adalah graf yang tidak mengandung loops atau pun multiple

edges. Loops adalah busur yang memiliki endpoint atau titik akhir, sedangkan

multiple edges adalah busur yang memiliki pasangan endpoint atau titik akhir

yang sama.

Gambar 1.2 Gambar 1.3 Gambar 1.4

Contoh graf sederhana dan bukan sederhana dapat dilihat pada gambar di atas.

Gambar 1.2 bukan graf sederhana karena memiliki loop atau pengulangan pada

titik yang sama. Gambar 1.4 juga bukan merupakan graf sederhana karena

memiliki multiple edges. Hanya gambar 1.3 yang merupakan graf sederhana

karena tidak memiliki loops dan multiple edges.

2

BAB II

PEMBAHASAN

2.1 Beberapa Graf Khusus

Berikut ini adalah beberapa jenis graf khusus yang perlu diketahui:

a. Graf Lengkap

Graf lengkap merupakan graf sederhana yang tiap-tiap simpulnya

terhubung ke simpul lainnya. Dengan kata lain, tiap simpul dari graf

lengkap itu bertetangga. Graf yang lengkap dengan n buah simpul

delambangkan dengan Kn. Jumlah sisi pada sebuah graf lengkap yang

terdiri dari n buah simpul adalah n(n-1)/2 sisi.

K1 K2 K3 K4

Gambar 1.5 Graf lengkap Kn, 1≤ n ≤ 4

b. Graf Lingkaran (Cycle Graph)

Graf lingkaran merupakan sebuah graf sederhana yang dimana setiap di

tiap simpulnya berderajat dua (2). Graf lingkaran dengan n simpul

dilambangkan dengan Cn.

K2 K3

Gambar 1.6

K3 merupakan graf lingkaran karena di tiap simpulnya berserajat dua,

sedangkan K2 bukan merupakan graf lingkaran karena simpulnya tidak

berderajat 2.

3

c. Graf Roda (Wheels Graph)

Graf roda merupakan graf yang diperoleh dengan cara menambahkan

satu simpul pada sebuah graf lingkaran (Cn), dan menghubungkan simpul

yang baru tersebut dengan semua simpul yang ada pada graf lingkaran

tersebut.

Gambar 1.7

Kedua gambar di atas adalah contoh dari graf roda, itu dibuktikan adanya

simpul baru yang menghubungkan simpul tersebut ke semua simpul dalam

graf lingkaran.

d. Graf Teratur (Regular Graph)

Graf teratur merupakan graf yang setiap simpulnya mempunyai derajat

yang sama. Apabila derajat tiap simpul dari sebuah graf teratur adalah r,

maka graf tersebut diberi nama graf teratur berderajat r. Jumlah sisi pada

graf teratur dengan n simpul adalah nr2

sisi.

Gambar 1.8

Graf teratur dengan 4 simpul berderajat 2.

4

2.2 Representasi Graf

a. Matriks Ketetanggaan (Adjadency Matrix)

Matriks ketetanggaan ada 2, yaitu untuk graf sederhana dan untuk graf tak

sederhana. Seperti yang kita ketahui sebelumnya, 2 buah simpul dianggap

bertetangga jika kedua simpul tersebut terhubung langsung ke sebuah sisi.

Matriks ketetanggaan untuk graf sederhana merupakan matriks bujur sangkar

yang unsur-unsurnya terdiri dari 2 bilangan, yaitu 0 dan 1. Baris dan kolom

pada matriks ini masing-masing merupakan representasi dari setiap simpul

pada graf tersebut, Misalkan aij merupakan unsur pada matriks tersebut,

maka:

Jika aij = 1 maka hal ini berarti simpul i dan simpul j bertetangga.

Jika aij = 0 maka hal ini berarti simpul i dan simpul j tidak

bertetangga.

Contoh :

Perhatikan graf sederhana berikut ini :

Matriks ketetanggaan dari graf sederhana tersebut adalah sebagai berikut :

Terlihat bahwa matriks tersebut simetris dan setiap unsur diagonalnya

adalah nol (0).

5

Matriks ketetanggaan untuk graf tak sederhana merupakan matriks bujur

sangkar yang unsur-unsurnya hanya terdiri dari bilangan 0, 1, dan 2. Baris

dan kolom pada matriks ini, masing-masing merupakan representasi dari

setiap simpul pada graf tersebut. Misalkan aij merupakan unsur pada matriks

tersebut, maka :

Jika aij = n maka hal ini berarti simpul i dan simpul j bertetangga oleh n buah

sisi.

Jika aij = 0 maka hal ini berarti simpul i dan simpul j tidak bertetangga.

Contoh:

Perhatikan graf di bawah ini:

Matriks ketetanggan dari graf tersebut adalah sebagai berikut:

6

b. Matriks bersisian

Suatu sisi e dapat dikatakan bersisian dengan simpul v1 dan simpul v2 jika

e menghubungkan kedua simpul tersebut, dengan kata lain e = (v1, v2). Seperti

halnya matriks ketetanggaan, unsur-unsur matriks bersisian pun hanya terdiri dari

dua bilangan yaitu 0 dan 1, tapi tidak dalam bujur sangkar. Hal ini disebabkan

baris dan kolom pada matriks bersisian, masing-masing merepresentasikan simpul

dan sisi pada graf yang dimaksud. Misalkan aij merupakan unsur pada matriks

tersebut, maka :

Jika aij = 1 maka hal ini berarti simpul ke-i dan sisi ke-j adalah bersisian.

Jika aij = 0 maka hal ini berarti simpul ke-i dan sisi ke-j tidak bersisian.

Contoh:

Perhatikan graf berikut ini :

Bentuk matriks bersisian dari graf ini adalah :

7

2.3 Graf Isomorfik

Dua buah graf yang sama tetapi secara geometri berbeda disebut dengan

graf yang saling isomorfik.

Dua buah graf, G1 dan G2 dapat dikatakan sebagai graf yang saling isomorfik

jika terjadi hubungan timbal balik satu-satu antara simpul-simpul kedua graf

tersebut dan antara sisi-sisi keduanya sedemikian hingga hubungan

kebersisian terjaga. Dengan kata lain, misalkan e bersisian dengan simpul u

dan v di G1, maka sisi e’ yang terdapat di G2 harus bersisian dengan simpul u’

dan v’ yang terdapat pada G2.

Dua buah graf yang isomorfik adalah graf yang sama, hanya saja penamaan

simpul dan sisinya saja yang berbeda. Ini terbukti benar karena graf

digambarkan dengan berbagai macam cara.

G1 isomorfik dengan G2, tetapi G1 tidak isomorfik dengan G3.

Dari definisi graf isomorfik dapat dikemukakan bahwa 2 buah graf isomorfik

memenuhi ketiga syarat berikut :

Mempunyai jumlah simpul yang sama.

Mempunyai jumlah sisi yang sama.

Mempunyai jumlah simpul yang sama berderajat tertentu.

Akan tetapi, ketiga syarat di atas belum menjamin bahwa 2 buah graf pasti

isomorfik. Jadi, pemeriksaan visual juga perlu dilakukan.

8

2.4 Graf Planar dan Graf Bidang

Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak

saling memotong (bersilangan) disebut graf planar, jika tidak maka ia disebut

dengan graf tak planar.

Contoh graf planar

Contoh graf tak planar

Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan

disebut juga dengan graf bidang (plane graph).

Contoh graf bidang

9

Beberapa hal tentang graf planar G(V, E), antara lain :

(Formula Euler) Misalkan G merupakan graf planar terhubung dengan e

buah sisi dan v buah simpul, dan r merupakan jumlah daerah pada graf

planar tersebut maka r = e – v + 2.

Jika G merupakan graf planar terhubung dengan e buah sisi dan v buah

simpul (v ≥3) maka e≤v – 6 (pertidaksamaan Euler).

Jika G merupakan graf planar terhubung dengan e buah sisi dan v buah

simpul (v≥3) dan tidak memuat sirkuit dengan panjang 3 maka e ≤ 2v – 4.

2.5 Teorema Kuratowski

Teorema ini berguna untuk menentukan dengan tegas keplanaran suatu

graf. (a) (b)

Gambar (a) Graf kuratowski pertama.

(b) Graf kuratowski kedua.

Sifat dari graf Kuratowski adalah :

Kedua graf Kuratowski adalah graf teratur.

Kedua graf Kuratowski adalah graf tidak-planar.

Penghapusan sisi atau simpul dari graf Kuratowski menyebabkannya

menjadi graf planar.

Graf kuratowski pertama adalah graf tidak-planar dengan jumlah simpul

minimum, dan graf kuratowski kedua adalah graf tidak-planar dengan

jumlah sisi minimum.

10

Pengertian dari Teorema Kuratowski yaitu sebuah graf G bersifat planar jika dan

hanya jika ia tidak mengandung upagraf yang isomorfik dengan salah satu graf

Kuratowski atau homeomorfik dengan salah satu dari kedua graf Kuratowski.

Contoh :

Perhatikan graf berikut :

Dengan menggunakan teorema Kuratowski, jelas bahwa graf G ini bukan

merupakan suatu graf planar, karena memuat subgraf dari graf G1 yang

merupakan graf Kuratowski.

11

2.6 Lintasan dan Sirkuit Euler

Lintasan Euler adalah lintasan yang melalui masing-masing sisi di dalam

graf sebanyak 1 kali. Maksudnya, jika lintasan tersebut kembali menuju simpul

awal sehingga membentuk suatu sirkuit tertutup maka lintasan inilah yang

dinamakan sebagai Sirkuit Euler. Graf yang memuat sirkuit Euler dinamakan

Graf Euler, sedangkan graf yang memuat lintasan Euler dinamakan graf semi

Euler.

G1

Dari gambar di atas, graf G1 merupakan graf Euler karena memiliki lintasan yang

membentuk lintasan tertutup (sirkuit), yaitu : pr – rt – ts – sq – qt – tp.

Semerntara itu,

G2

Terlihat bahwa graf G2 merupakan graf semi Euler karena graf tersebut memiliki

lintasan yang melalui masing-masing sisi di dalam graf tersebut tepat sebanyak 1

kali. Lintasan tersebut adalah : pq – qs – st – tp – pr – rt – tq.

12

Beberapa sifat dari Lintasan dan sirkuit Euler, yaitu :

Suatu graf G merupakan graf Euler (memiliki sirkuit Euler) jika dan hanya

jika setiap simpul pada graf tersebut berderajat genap.

Graf terhubung G merupakan graf semi Euler (memiliki lintasan Euler)

jika dan hanya jika di dalam graf tersebut dua simpul berderajat ganjil.

Suatu graf terhubung berarah G merupakan graf Euler jika dan hanya jika

setiap simpul pada graf tersebut memiliki derajat masuk dan derajat keluar

yang sama.

Suatu graf terhubung berarah G merupakan graf semi Euler jika dan hanya

jika G terhubung setiap simpul pada graf tersebut memiliki derajat masuk

dan derajat keluar yang sama, kecuali dua simpul yaitu simpul pertama

memiliki derajat keluar 1 lebih besar dari pada derajat masuk dan simpul

yang kedua memiliki derajat masuk satu lebih besar dari pada derajat

keluar.

13

2.7 Lintasan dan Sirkuit Hamilton

Ditemukan oleh Sir William Hamilton pada tahun 1859. Ketika itu dia

membuat sebuah permainan yang dinamakan dodecahedron yang ditawarkan

kepada pabrik mainan di Dubin. Permainan tersebut terdiri dari 12 buah

pentagonal dan ada 20 titik sudut dan setiap titik sudut diberi nama ibukota suatu

negara. Permainan ini membentuk perjalanan keliling dunia yang mengunjungi

setiap ibukota negara tepat 1 kali dan kembali lagi ke kota asal. Ini tak lain adalah

mencari sirkuit Hamilton.

Masalah tersebut dapat diilustrasikan dalam gambar di bawah ini :

Pada ilustrasi pada gambar di atas, lintasan yang dicetak tebal merupakan sirkuit

Hamilton. Lintasan Hamilton suatu graf merupakan lintasan yang melalui setiap

simpul dalam graf tersebut tepat satu kali. Jika lintasan tersebut kembali ke

simpul awal, maka lintasan ini dinamakan sirkuit Hamilton.

Dengan demikian, sirkuit Hamilton merupakan sirkuit yang melewati masing-

masing sisi tepat satu kali. Graf yang memuat sirkuit Hamilton dinamakan graf

Hamilton, sedangkan graf yang memuat lintasan Hamilton dinamakan graf semi

Hamilton.

14

2.8 Beberapa Aplikasi Graf

a. Lintasan Terpendek

Misalkan G merupakan graf berbobot, yaitu setiap sisi dari graf G

memiliki bobot tertentu, hal yang biasanya dilakukan aalah menentuka lintasan

terpendek dari graf tersebut. Dengan kata lain, menentukan lintasan yang

memiliki total bobot minimum, contohnya :

Untuk menentukan jarak terpendek/ waktu tempuh paling cepat/ biaya

termurah dari 2 kota.

Menentukan waktu tercepat pengiriman sebuah pesan antara 2 terminal

pada sebuah jaringan komputer.

b. Persoalan Perjalanan Pedagang (TSP)

Sama halnya dengan lintasan terpendek yang dibahas di atas. Tentukan

sirkuit terpendek yang harus dilalui oleh seorang pedagang bila pedagang itu

berangkat dari sebuah kota asal dan ia harus menyinggahi setiap kota tepat satu

kali dan kembali ke kota asal keberangkatan. Ini merupakan masalah untuk

mencari sirkuit Hamilton yang memiliki bobot minimum.

Contoh:

Graf di atas memiliki (4 – 1)!/2 = 3 sirkuit Hamilton, yaitu:

• I1 = (a, b, c, d, a) atau (a, d, c, b, a) ==> panjang = 10 + 12 + 8 + 15 = 45

• I2 = (a, c, d, b, a) atau (a, b, d, c, a) ==> panjang = 12 + 5 + 9 + 15 = 41

15

• I3 = (a, c, b, d, a) atau (a, d, b, c, a) ==> panjang = 10 + 5 + 9 + 8 = 32

Jadi sirkuit Hamilton terpendek adalah I3 (a, c. b, d, a) dengan panjang sirkuit 32.

c. Persoalan Tukang Pos Cina (Chinese Postman Problem)

Permasalahan ini, pertama kali dikemukakan oleh Mei Gan (berasal dari

Cina) pada tahun 1962, yaitu : Seorang tukang pos akan mengantar surat ke

alamat-alamat sepanjang jalan di suatu daerah. Bagaimana ia merencanakan rute

perjalanannya supaya ia melewati setiap jalan tepat sekali dan kembali lagi ke

tempat awal keberangkatan. Permasalahan tersebut merupakan masalah

menentukan sirkuit Euler di dalam suatu graf.

Contoh :

Jadi, lintasan yang dilalui tukang pos adalah A, B, C, D, E, F, C, E, B, F, A.

16

BAB III

PENUTUP

3.1 Kesimpulan

Graf adalah pasangan dari himpunan (V,E) dimana V adalah sebuah

himpunan tak kosong yang memiliki elemen yang disebut simpul (verticles) dan E

adalah kumpulan dari 2 elemen subset V yang disebut dengan busur (Edges).

Graf memiliki banyak kegunaan dalam kehidupan manusia, misalnya dalam

pemasangan listrik, IC, dan lainnya. Graf juga memiliki banyak bentuk, dari yang

berbentuk sederhana hingga yang tak sederhana. Graf juga banyak diaplikasikan

dalam berbagai macam masalah dalam kehidupan manusia, seperti dalam

pencarian lintasan terpendek untuk perjalanan. Jadi graf memilki peranan yang

penting dalam kehidupan manusia.

3.2 Saran

Dari hasil makalah ini perlu kiranya di kemukakan beberapa saran yang

mungkin akan bermanfaat bagi pembaca, guru dan pihak yang ada hubungannya

dengan bidang studi matematika. Adapun saran-saran yang dikemukakan adalah:

Semoga dapat bermanfaat bagi para pembaca terutama kepada pembuat

makalah sendiri untuk menambah wawasan bahwa dalam mencapai suatu

tujuan tertentu maka dicari lintasan terpendeknya sehingga dapat

menghemat waktu dan biaya.

Semoga makalah ini juga dapat bermanfaat padda mahasiswa yang sedang

menempuh bangku perkuliahan.

17

DAFTAR PUSTAKA

http://www.scribd.com/doc/79785736/Pengertian-Graf

www.wikipedia.org

http://delonge.students-blog.undip.ac.id

http://risma0802030140.blogspot.com/2011/04/matematika-diskrit.html

iv