MAKALAH MATEMATIKA DISKRIT

DOSEN : USEP RAHMAT M.Si

Kelompok VIII

Arif Winarso

Dewi Sartika

Nesti Elvia Yurina

Selfiyanah

FAKULTAS KEGURUAN ILMU DAN PENDIDIKAN

UNIVERSITAS MUHAMMADIYAH TANGERANG

2012/2013

1

KATA PENGANTAR

Puji syukur kita haturkan kepada Allah SWT, Yang Esa yang menciptakan alam

semesta.Sholawat dan salam selalu dilimpahkan kepada panutan kita Nabi

Muhammad Saw beserta keluarga dan sahabatnya.

Alhamdulilah, penyusunan makalah ini sebagai tugas kelompok yang diberikan

dosen antara kuliah Matematika Diskrit pada semester kelimapada tahun

akademik 2012/2013 telah selesai pada waktunya yang sudah ditetapkan.Ucapan

terimakasih kepada yth :

1. Drs.Usep rahmat ,Mpd sebagai dosen matakuliah Matematika Diskrit di

Universitas Muhammadiyah Tangerang yang kami hormati.

2. Teman-teman FKIP Prodi Matematika B1 Universitas Muhammmadiyah

Tangerang Atas segala bantuannya baik moril dan spiritual sehingga dapat

terselesaikan makalah ini.

Atas ada saran dan segenap kritikan bagi kami demi lebih baiknya makalah ini.

Kami ucapkan terimakasih.Semoga makalah ini bermanfaat bagi kita semua

khususnya menambah wawasan bagi kita.

Tangerang,Desember 2012

Penyusun

Kelompok VIII

2

DAFTAR ISI

I. Kata Pengantar............................................................................ 2

II. Daftar Isi.................................................................................... 3

III. Teori Dasar Graf.......................................................................... 4

a. Kelahiran Teori Graf............................................................ 4

b. Problema dan Model Graf..................................................... 5

c. Graf Secara Formal............................................................... 7

d. Sub Graf................................................................................ 9

e. Graf Berlabel....................................................................... 10

f. Homomorfis.......................................................................... 11

g. Operasi Pada Graf................................................................. 12

IV. Teori Dasar Graf Lanjutan.......................................................... 14

a. Matriks dan Graf................................................................... 14

b. Graf Planar............................................................................ 15

c. Pewarnaan Graf..................................................................... 16

V. Terminologi Dasar..................................................................... 17

a. Graf Isomorfik...................................................................... 17

b. Alogaritma Pewarnaan Graf................................................. 18

VI. Penutup....................................................................................... 27

VII. Daftar Pustaka............................................................................ 28

3

Teori Dasar Graf

Kelahiran Teori Graf

Teori Graf mulai dikenal pada saat seorang matematikawan bangsa Swiss,

bernama Leonhard Euler, berhasil mengungkapkan Misteri Jembatan Konigsberg

pada tahun 1736. Di Kota Konigsberg (sekarang bernama Kalilingrad, di Uni

Soviet) mengalir sebuah sungai bernama sungai Pregel. Di tengah sungai tersebut

terdapat dua buah pulau. Dari kedua pulau tersebut terdapat jembatan yang

menghubungi ke tepian sungai dan diantara kedua pulau. Jumlah jembatan

tersebut adalah 7 buah seperti gambar berikut :

Konon kabarnya, penduduk kota Konigsberg sering berjalan-jalan ke tempat

tersebut pada hari-hari libur. Kemudian muncul suatu keinginan untuk dapat

menikmati daerah tersebut dengan melalui ketujuh jambatan tepat satu kali, yakni

bermula dari satu tempat (A, B, C atau D) dan kembali ke tempat semula. Mereka

berusaha untuk memperoleh rute yang sesuai dengan keinginan tersebut, dengan

selalu mencoba menjalaninya. Setelah mencoba berkali-kali dan karena sudah

cukup lama tidak diperoleh rutenya, akhirnya penduduk tersebut mengirim surat

4

Sungai Pregeldi Kalilingrad (Uni Soviet)

A

B

CD

A

C D

B

kepada Euler. Euler dapat memecahkan masalah tersebut, yakni bahwa

perjalanan / rute yang diinginkan (yakni berawal dari suatu tempat, melalui

ketujuh jembatan tepat satu kali, dan kembali ke tempat semula) tidak mungkin

dicapai.

Secara singkat, dalam tulisannya, Euler menyajikan keadaan jembatan Konigsberg

tersebut seperti gambar berikut :

Dalam masalah di atas, daratan (tepian A dan B, serta pulau C dan D) disajikan

sebagai titik dan jembatan disajikan sebagai ruas garis. Euler mengemukakan

teoremanya yang mengatakan bahwa perjalanan yang diinginkan di atas (yang

kemudian dikenal sebagai perjalanan Euler) akan ada apabila graf terhubung dan

banyaknya garis yang datang pada setiap titik (derajat simpul) adalah genap.

Problema & Model Graf

Secara umum, langkah-langkah yang perlu dilalui dalam penyelesaian suatu

masalah dengan bantuan komputer adalah sebagai berikut :

Problema Model Yang Tepat Algoritma Program Komputer

Contoh problema graf :

5

8

7

12 9 11 9 11 10 8

1

4

1. Petugas kantor telepon yang ingin mengumpulkan koin-koin dari telepon

umum. Berangkat dari kantor & kembali ke kantornya lagi.

Yang diharapkan suatu rute perjalanan dengan waktu minimal.

Masalah di atas dikenal sebagai Travelling Salesman Problem

Sebagai contoh :

Untuk menyelesaikan masalah di atas dapat dipakai Algoritma Tetangga Terdekat

(yakni menggunakan Metode Greedy)

6

B E

A

F

A

A

B

B

A

D

D

FB

F

FC

E

C

E

C

E

B

C

E

2. Perancangan Lampu Lalu Lintas.

Yang diharapkan pola lampu lalu lintas dengan jumlah fase minimal.

Sebagai contoh :

Untuk menyelesaikan masalah di atas dapat dipakai Algoritma Pewarnaan Graf

(juga dikenal sebagai Graph Coloring, yakni menggunakan Metode Greedy)

Graf Secara Formal

Sebuah Graf G mengandung 2 himpunan :

(1). Himp. V, yang elemennya disebut simpul

Vertex / point / titik / node

(2). Himp. E, yang merupakan pasangan tak terurut dari simpul-simpul, disebut

ruas

7

C D

e2

e3e1 e5

e4CD

AB

C

A

D B

Edge / rusuk / sisi

Sehingga sebuah graf dinotasikan sebagai G ( V, E )

Contoh :

G ( V, E )

V = { A, B, C, D }

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

Secara Geometri :

Tidak

ada

ketentuan khusus dalam penyajian graf secara geometri, seperti dimana dan

bagaimana menyajikan simpul dan ruas. Berikut contoh penyajian Graf yang

sama, tetapi disajikan berbeda.

Beberapa istilah lain dalam graf :

Berdampingan

simpul U dan V disebut berdampingan bila terdapat ruas (U,V)

Order

banyaknya simpul

Size

8

terdiri dari 4 simpul dan 5 ruas

A

AA

e2w12

Ae3

e4e1

e5

e6

banyaknya ruas

Self-loop (loop) / Gelung

ruas yang menghubungkan simpul yang sama ( sebuah simpul )

Ruas sejajar / berganda

ruas-ruas yang menghubungkan 2 simpul yang sama

Sebuah graf dikatakan multigraf bila graf tersebut mengandung ruas sejajar atau

gelung. Sedangkan graf yang tidak mengandung ruas sejajar atau gelung dikenal

sebagai graf sederhana, atau yang disebut graf. Adapun contoh multigraf adalah

sebagai berikut.

Subgraf

G‘(V‘, E‘) adalah Subgraf dari G (V, E) bila : V‘ V dan E‘ E

Apabila E‘ mengandung semua ruas di E yang kedua ujungnya di V‘ , maka

G‘ adalah Subgraf yang dibentuk oleh V‘ (Spanning Subgraph)

Contoh :

9

Multigraf

e2

e3e1 e5

e4CD

AB

G :

e5e1

A B

D

G’ :

G’ subgraf dari G

e2

e5e1

A B

D

G’ :

G’ spanning subgrapf dari G

B D F

C GE

HA

3

19

8

13

3

3

4

222

12

6

3

Graf berlabel

Graf berlabel/ berbobot adalah graf yang setiap ruasnya mempunyai nilai/bobot

berupa bilangan non negatif.

Contoh :

Homomorfis

Jika G* dan G** diperoleh dari G dengan membagi beberapa ruas dari G oleh

penambahan beberapa simpul pada ruas tersebut, maka kedua graf G* dan G**

disebut homomorfis

10

G G* G**

Contoh :

Operasi pada Graf

Berdasarkan definisi graf (yang terdiri dari 2 himpunan) dan operasi pada

himpunan, maka pada graf juga dapat dilakukan operasi-operasi. Bila diketahui 2

buah graf : G1(V1,E1) dan G2(V2,E2), maka :

1. Gabungan G1 G2 adalah graf dengan himpunan V nya = V1 V2 dan

himpunan E nya = E1 E2

2. Irisan G1 G2 adalah graf dengan himpunan V nya = V1 V2 dan himpunan E

nya = E1 E2

3. Selisih G1 - G2 adalah graf dengan himpunan V nya = V1 dan himpunan E nya

= E1 - E2

Sedangkan Selisih G2 – G1 adalah graf dengan himpunan V nya = V2 dan

himpunan E nya = E2 – E1

4. Penjumlahan Ring G1 G2 adalah graf yang dihasilkan dari

(G1 G2) – (G1 G2) atau (G1 - G2) (G2 - G1)

11

CD

BA

E

e2e4

e1

e3

e6e5

e7e8

A

F

D

e1 B

C

e4 e2

e10

e3

e9

D

A e1 B

C

e4 e2

e3CD

BA

E

e2e4

e1

e3

e6e5

e7e8

e10 e9

CD

BA

E

e6e5

e7e8

CD

e10 e9

CD

BA

E

e6e5

e7e8

e10 e9

G1 G2

G1 G2G1 G2

G1 G2

G1 - G2 G2 – G1

Contoh :

12

V4V5

V2 V3

V1

e6

e5

e4

e3

e2

e1

e8

e7

Teori Dasar Graf (Lanjutan)

Matriks dan Graf

Untuk menyelesaikan suatu permasalahan model graf dengan bantuan komputer,

maka graf tersebut disajikan dalam bentuk matriks. Matriks-matriks yang dapat

menyajikan model graf tersebut antara lain :

Matriks Ruas

Matriks Adjacency

Matriks Incidence

Sebagai contoh, untuk graf seperti di bawah ini :

Maka,

Matriks Ruas :

Atau :

Matriks Adjacency :

13

Matriks Incidence :

Graf Planar

Sebuah graf dikatakan graf planar bila graf tersebut dapat disajikan (secara

geometri) tanpa adanya ruas yang berpotongan. Sebuah graf yang disajikan tanpa

adanya ruas yang berpotongan disebut dengan penyajian planar/map/peta.

Contoh :

Pewarnaan Graf

Pewarnaan graf adalah pemberian warna terhadap simpul-simpul graf dimana 2

buah simpul yang berdampingan tidak boleh mempunyai warna yang sama.

G berwarna n artinya graf tersebut menggunakan n warna.

Bilangan kromatis dari G = K(G) adalah jumlah minimum warna yang

dibutuhkan.

14

Graf Planar

K4

Penyajian Planar

Algoritma yang dapat digunakan untuk mendapatkan bilangan kromatis dari

sebuah graf adalah Algoritma Welch-Powell.

Adapun langkah-langkahnya adalah :

1. Urutkan simpul-simpul berdasarkan derajatnya.

Dari besar ke kecil.

2. Warnai.

Contoh :

Langkah 1 :

urutan simpulnya dari besar ke kecil adalah : E, C, G, A, B, D, F, H

Langkah 2 :

mewarnai :

warna Merah : E, A

warna Putih : C, D, H

warna Biru : G, B, F

Sehingga bilangan kromatis graf di atas adalah 3.

Teorema :

Pernyataan berikut adalah ekivalen :

15

G

A B C

D

EF

H

(1) G berwarna 2

(2) G adalah bipartisi

(3) Setiap sirkuit dalam G mempunyai panjang genap

Graf Lengkap k dengan n simpul membutuhkan n warna

Teorema :

Suatu graf planar G adalah berwarna 5

Terminologi Dasar

8.6 Beberapa Graf Sederhana Khusus

A. Graf Lengkap (Complete Graph)

Ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua

simpul lainnya.Graf lengkap dengan n buah simpul dilambangkan dengan

Kn.Setiap simpul pada Kn berderajat n -1.

B. Graf Lingkaran

Adalah graf sederhana yang setiap simpulnya berderajat dua.Graf

lingkaran dengan n simpul dilambangkan dengan Cn.Jika simpul-simpul pada Cn

adalah v1,v2,…,vn,maka sisi-sisinya adalah (v1,v2),(v2,v3),…(vn-1,vn), dan

(vn,v1).

C. Graf Teratur (Regular Graph)

Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf

teratur.

Contoh :

Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang

mempunyai 12 buah sisi dan setiap simpul berderajat sama yang ≥3 ?

Penyelesaian:

Tiap simpul berderajat sama,berarti graf teratur.

Jumlah sisi pada graf teratur berderajat r adalah e = nr/2.Jadi, n = 2e/r =(2)(12)/r =

24/r

16

Untuk r = 3,jumlah simpul yang dapat dibuat adalah maksimum, yaitu n = 24/3 =8

Untuk r yang lain (r¿ 3 dan r merupakan pembagi bilangan bulat dari 24).

r= 4 maka n = 24/4 = 6

r=6 maka n = 24/6 = 4 maka tidak mungkin membentuk graf sederhana

r=8 maka n = 24/8 = 3 maka tidak mungkin membentuk graf sederhana

r=12 maka n = 24/12 = 2 maka tidak mungkin membentuk graf sederhana

r=24 maka n = 24/24 = 1 maka tidak mungkin membentuk graf sederhana

Jadi, jumlah simpul paling sedikit 6 buah dan paling banyak 8 buah.

D. Graf Bipartit (Bipartite Graph)

Graf G yang himpunan simpulnya dapat dikelompokkan menjadi dua himpunan

bagian V1 dan V2,sedemikian sehingga setiap sisi di dalam G menghubungkan

sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan

sebagai G(V1,V2)

Graf Isomorfik (Isomorphic Graph)

Definisi

Dua buah graf, G1 dan G2 dikatakan isomorfik jika te

rdapat korespondensi satu – satu antara simpul – simpul keduanya dan antara sisi

– sisi keduanya sede

mikian sehingga jika sisi e bersisian dengan simpul u dan v di G1,maka sisi e”

yang berkorespon di G2 juga harus bersisian dengan simpul u” dan v” di G2.

8.13. Lintasan Terpendek

Lintasan pendek 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.

Contoh-contoh terapan pencarian lintasan terpendek misalnya

17

1. Misalkan simpul pada graf dapat merupakan kota, sedangkan sisi

menyatakan jalan yang menghubungkan dua buah kota. Bobot sisi graf

dapat menyatakan jarak antara dua buah kota atau rata-rata waktu

tempuh antara dua buah kota. Apabila terdapat lebih dari satu lintasan

dari kota A ke kota B, maka persoalan lintasan terpendek disini adalah

menentukan jarak terpendek atau waktu tersingkat dari kota A ke B.

2. Misalkan simpul pada graf dapat merupakan terminal komputer atau

simpul komunikasi dalam suatu jaringan, sedangkan sisi menyatakan

saluran komunikasi yang menghubungkan dua buah terminal. Bobot

pada graf dapat menyatakan biaya pemakaian saluran komunikasi

antara dua buah terminal,jarak antara dua buah terminal, atau waktu

pengiriman pesan ( message ) antara dua buah terminal. Persoalan

lintasan terpendek di sini adalah menentukan jalur komunikasi

terpendek antara dua buah terminal komputer. Lintasan terpendek akan

menghemat waktu pengiriman pesan dan biaya komunikasi.

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 simpulyang melalui beberapa

simpul tertentu.

Pada dasarnya, jenis persoalan a. Mirip dengan jenis persoalan c,

karena pencarian lntasan terpendek pada jenis persoalan c dapat

dihentikan bila simpul tujuan yang dikehendaki sudah ditemukan

lintasan terpendeknya. Di dalam buku ini kita akan hanya

membahas jenis persoalan c.

Deskripsi persoalan lintasan terpendek pada jenis persoalan c

adalah sebagai berikut :

Diberikan graf berbobot G = ( V , E ) dan sebuah simpul awal a.

Tentukan lintasan terpendek dari a ke setiap simpul lainnya di

dalam G ?

18

Sebagai ilustrasi, tinjau graf berarah pada gambar 8.64. litasan

terpendek dari simpul 1 ke semua simpul lain pada tabel dibawah

ini ( di urut dari lintasan terpendek pertama,kedua,ketiga dst.)

Simpul Asal Simpul Tujuan Lintasan

Terpendek

Jarak

1 3 1,3 10

1 4 1,3,4 25

1 2 1,3,4,2 45

1 5 1,5 45

1 6 Tidak ada _

Dari tabel diatas, bahwa lintasan terpendek dari 1 ke 2 berarti juga

melalui lintasan terpendek dari 1 ke 3 dan dari 1 ke 4.

Sampai saat ini sudah banyak algoritma mencari lintasan terpendek

yang pernah ditulis orang. Algoritma lintasan terpendek yang

paling terkenal adalah algoritma dijkstra ( sesuai dengan nama

penemunya, Edsger W. Dijkstra ). Dalam naskah aslinya, algoritma

dijkstra diterapkan pada untuk mencari lintasan terpendek pada

graf berarah. Namun, algoritma ini juga benar untuk graf tak

berarah.

Algoritma dijkstra mencari lintasan terpendek dalam sejumlah

langkah. Algoritma ini menggunakan prinsip greedy. Prinsip

greedy pada algoritma dijkstra menyatakan bahwa pada setiap

langkah kita memilih sisi yang berbobot minimum dan

memasukkannya ke dalam himpunan solusi.

Ada beberapa versi algoritma dijkstra yang ditulis pada berbagai

pustaka. Algoritma yang dibahas di bawah ini adalah salah satu

versinya.

Misalkan sebuah graf berbobot dengan n buah simpul dinyatakan

dengan matriks

Ketetanggaan M = ( mij ) yang dalam hal ini,

mij = bobot sisi ( i, j ) ( pada graf tak berarah mij =

mij )

19

mij = 0

mij =∞, jika tidak ada sisi dari simpul i ke simpul j.

Selain matrik M, Kita juga menggunakan tabel S = [ sᵢ ] yang

dalam hal ini,

sᵢ = 1 , jika simpul i termasuk ke dalam lintasan

terpendek.

sᵢ = 0, jika simpul i tidak termasuk ke dalam lintasan

terpendek.

Dan tabel D = [di ] yang dalam hal ini

di = panjang lintasan dari simpul awal a ke simpul i

Algoritma Pewarnaan Graf

Algoritma Welch-powell dapat digunakan untuk mewarnai sebuah graf G secara

mangkus. Algoritma ini hanya memberikan batas atas untuk x(G ), yaitu bahwa

algoritma tidak selalu memberikan jumlah warna minimum yang diperlukan untuk

mewarnai G [ LIP92]. Algoritma Welch-powell adalah sebagai berikut:

Algoritma Welch-powell

1. Urutkan simpu-simpul dari G dalam derajat yang menurun ( urutan seperti

ini mungkin tidak unik karena beberapa simpul mungkin berderajat sama ).

2. Gunakan satu warna untuk mewarnai simpul pertama ( yang mempunyai

derajat tertinggi ) dan simpul-simpul lain ( dalam urutan yang berurut )

yang tidak bertetangga dengan simpul pertama ini.

3. Mulai lagi dengan simpul derajat tertinggi berikutnya didalam daftar

terurut yang belum diwarnai dan ulangi proses pewarnaan simpul dengan

menggunakan warna kedua.

4. ulangi penambahan warna-warna sampai semua simpul telah diwarnai.

Contoh

Gunakan algoritma Welch-powell untuk mewarnai graf di bawah ini.

Penyelesaian :

Urutkan simpul-simpul di dalam graf berdasarkan drajat yang menurun.

Warnai simpul 1 dengan warna a. Simpul yang tidak bertetangga dengan 1

adalah simpul 5, warnai simpul 5 ini dengan warna a. Simpul berikutnya di

20

dalam daftar yang belum diwarnai adalah simpul 3. warnai simpul 3 dengan

warna b, dan simpul yang tidak bertetangga dengan 3 adalah simpul 6, warna

simpul 6 ini juga dengan warna b. simpul berikutnya yang belum diwarnai

adalah simpul 4. warnai simpul 4 dengan warna c, begitu juga simpul yang

tidak bertetangga dengan simpul 4 diberi warna c. sekarang semua simpul

sudah diwarnai.

Simpul 1 3 6 4 2 5

Derajat 4 4 3 3 2 2

Warna a b b c c a

8.17. Ragam Soal dan Penyelesaian.

Contoh 8.46

Dapatkah kita menggambar graf teratur berderajat 3 dengan 7 buah simpul ?

mengapa ?

Penyelesaian :

Tidak, karena menurut aturan lemma jabat tangan, jumlah derajat semua simpul

pada suatu graf adalah genap, yaitu 2 kali jumlah sisi di dalam graf tersebut. Pada

graf tersebut :

Ҽ = nr/2

↔ 2ҽ = nr

↔ 2ҽ = 3.7

↔ 2ҽ = 21 jelas tidak memenuhi syarat karena 2 kali jumlah sisi pada graf

tersebut ganjil.

Pendekatan lain :

ҽ = 21/2 jelas bahwa jumlah sisi dari suatu graf tidak mungkin berupa

pecahan, maka tidak mungkin menggambar graf teratur berderajat

3 dengan 7 buah simpul.

Contoh 8.47.

Tentukan jumlah simpul pada graf sederhana bila mempunyai 20 buah sisi dan

tiap simpul berderajat sama.

21

Penyelesaian:

Pada graf teratur derajat r dengan n buah simpul, jumlah sisinya adalah

ҽ = nr/2

sehingga

ҽ = 2e/r = 2.20/r = 40/r

tinjau kasus-kasus nilai r sebagai berikut :

a. Untuk r = 1, maka n = 40, akan terbentuk graf tidak terhubung yang

masing-masing simpulnya berderajat 1, jumlah sisinya adalah 40/2 = 20

memenuhi.

b. Untuk r = 2, maka n = 20, akan terbentuk graf lingkaran dengan sisi 20

( memenuhi ).

c. Untuk r = 3.6.7.9 tidak mungkin sebab hasil pembagian 40/r tidak bulat.

d. Untuk r yang lebih besar lagi tidak akan mungkin lagi terbentuk graf

sederhana sebab jumlah simpulnya akan lebih kecil sehingga maksimum

sisi yang diizinkan juga semakin kecil.

Jadi r yang memenuhi adalah ( 1,2,4,5 ), dan jumlah simpul di dalam graf

adalah ( 40,20,10,8 ).

Contoh 8.48

Berapa jumlah minimum simpul yang diperlukan agar sebuah graf dengan

6 buah sisi menjadi planar ? ulangi soal yang sama untuk 11 buah sisi.

Penyelesaian:

Gunakan ketidaksamaan euler e≤3n-6

Untuk e = 6,

e≤3n-6

6 ≤3n-6

12≤3n

4 ≤n

Berarti jumlah minimum simpul adalah 4.

Untuk e = 11,

e≤3n-6

22

11≤3n-6

17≤3n

17/3≤3n

Berarti jumlah minimum simpul adalah 6.

Contoh 8.50

Berapa bilangan kromatis graf pada soal 8.49 diatas?

Penyelesaian:

Bilangan kromatis graf tersebut adalah 4. Sebagai contoh simpul dapat

dibagi menjadi 4 warna berbeda (D,A,H ),(C, E ),(B,G ),( F )

8.14 Persoalan Pedagang Keliling

Persoalan pedagang keliling (Travelling Salesperson Problem -TSP)

termasuk kedalam persoalan yang sangat terkenal didalam teori graf. Nama

persoalan ini diilhami dari masalah seorang pedagang yang berkeliling

mengunjungi sejumlah kota. Deskripsi persoalannya adalah sebagai berikut :

misalkan diberikan sejumlah kota dan jarak antar kota. 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 lagi ke

kota asal keberangkatan.

Ini merupakan masalah menentukan sirkuit Hamilton yang memiliki bobot

minimum.

Contoh 1 :

Pak Pos akan mengambil surat di bis surat yang tersebar pada n buah

lokasi di berbagai sudut kota.

Contoh 2 (Munir, 2012) :

Jumlah sirkuit Hamilton di dalam graf lengkap dengan n simpul: (n - 1)!/2.

23

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

S1 = (a, b, c, d, a) atau (a, d, c, b, a) dengan panjang rute = 10 + 12 + 8 + 15 = 45

S2 = (a, c, d, b, a) atau (a, b, d, c, a) dengan panjang rute = 12 + 5 + 9 + 15 = 41

S3 = (a, c, b, d, a) atau (a, d, b, c, a) dengan panjang sirkuit = 10 + 5 + 9 + 8 = 32

8.15 Persoalan Tukang Pos Cina (chinese Postman Problem)

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

Cina) pada tahun1962, 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 Eulerdi dalam

suatu graf.

Contoh (Munir, 2012)

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

24

8.16 Pewarnaan Graf

Ada tiga macam persoalan pewarnaan graf (graph colouring), yaitu pewarnaan

simpul, pewarnaan sisi, dan pewarnaan wilayah (region).

Definisi 8.20 Pewarnaan simpul adalah memberi warna pada simpul-simpul di

dalam graf sedemikian sehingga setiap dua simpul bertetangga mempunyai warna

yang berbeda.

Didalam persoalan mewarnai graf, kita tidak hanya sekedar mewarnai simpul-

simpul dengan warna berbeda dari warna simpul tetangganya saja, namun kita

juga menginginkan jumlah macam warna yang digunakan sedikit mungkin.

Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut

bilangan kromatik graf G, disimbolkan dengan x(G) yang mempunyai bilangan

kromatis k dilambangkan dengan x(G) = k.

8.17 Ragam soal dan penyelesaian

Contoh 1 :

Dapat kah kita menggambar graf teratur berderajat 3 dengan 7 buah simpul?

Mengapa?

Jawab :

tidak karena menurut aturan Lemma jabat tangan, jumlah derajat semua simpul

pada suatu graf adalah genap, yaitu 2 kali jumlah sisi di dalam graf tersebut. Pada

graf tersebut:

e=nr2

2 e=nr

2 e=3 .7

2 e=21 jelas tidak memenuhi syarat karena 2 kali jumlah sisi pada graf tersebut

ganjil.

Contoh 2 :

Berapa jumlah minimum simpul yang diperlukan agar sebuah graf dengan 6 buah

sisi menjadi planar?

Jawab :

25

e=6

e≤ 3 n−6

6 ≤ 3n−6

12 ≤3n

4 ≤ n

Contoh 3 :

Gambarkan 2 buah graf yang isomorfik dengan graf teratur berderajat 3 yang

mempunyai 8 buah simpul.

Jawab :

Jawaban untuk soal ini tidak unik. Ada banyak graf teratur dengan 8 simpul yang

saling isomorfiksatu sama lain. Sepasang diantaranya adalah seperti berikut ini:

PENUTUP

Tugas Matematika Diskrit Apabila dalam penyusunan tugas ini masih

banyak kesalahan dan kekurangan, saya mengharapkan kritik dan saran yang

membangun dari pembaca, agar saya dapat membuat tugas selanjutnya yang lebih

baik lagi. Dan dapat berguna bagi kita semua khususnya dan yang lain pada

umumnya.

26

DAFTAR PUSTAKA

Doerr, Alan & Kenneth Levasseur, Applied Discrete Structures for Computer

Science, SRA Associates, 1985

27