teori dasar graf
DESCRIPTION
Makalah Tentang Teori Graff dan Teorema LagrangeTRANSCRIPT
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