ANALISIS TEORI GRAF PADA PERSOALAN KNIGHT’S TOUR
SKRIPSI
ERWIN 060803018
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
ANALISIS TEORI GRAF PADA PERSOALAN KNIGHT’S TOUR
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
ERWIN 060803018
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PERNYATAAN
ANALISIS TEORI GRAF PADA PERSOALAN KNIGHT’S TOUR
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 04 Agustus 2010
ERWIN 060803018
Universitas Sumatera Utara
PENGHARGAAN
Puji dan syukur penulis panjatkan kepada Tuhan yang Maha Penyayang, atas kemurahan dan berkat yang telah diberikan sehingga penulis dapat menyelesaikan skripsi dengan judul ”Analisis Teori Graf Pada Persoalan Knight’s Tour” guna melengkapi syarat memperoleh gelar sarjana Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam di Universitas Sumatera Utara. Pada kesempatan ini, penulis menyampaikan terima kasih yang sedalam – dalamnya kepada : 1. Bapak Dr. Sutarman, M.Sc selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 2. Bapak Dr. Saib Suwilo, M.Sc, Bapak Drs. Henry Rani Sitepu, M.Si selaku Ketua dan sekretaris Departemen Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 3. Bapak Prof. Dr. Herman Mawengkang, Phd selaku Dosen Pembimbing I dan Bapak Prof. Dr. Drs. Iryanto, M.Si selaku Dosen Pembimbing II yang telah membimbing, mengarahkan dan meluangkan waktunya untuk penulis dalam menyelesaikan skripsi. 4. Seluruh Staf Pengajar dan Pegawai Departemen Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 5. Kedua orang tua serta kedua abang penulis yang telah memberikan doa, bimbingan dan dorongan serta bantuan baik material maupun nonmaterial kepada penulis sehingga selesainya skripsi ini. 6. Senior matematika Hindra, Ivy, Darwin, Alice, Josephine dan teman – teman ’06 terutama Meidiana, yang senantiasa memberikan doa dan semangat kepada penulis untuk menyelesaikan skripsi ini.
Universitas Sumatera Utara
ABSTRAK
Skripsi ini membahas tentang aplikasi dari teori graf pada permainan catur. Permasalahan menarik yang dibahas disini adalah membuat siklus hamilton dengan menggunakan kuda pada permainan catur
(Knight’s
Tour).
Suatu
Knight’s Tour pada papan catur adalah rangkaian perjalanan kuda catur pada papan catur sehingga seluruh kotak terlewati oleh kuda catur tepat satu kali. Setelah mempelajari tulisan ini akan mendapatkan cara yang lebih mudah untuk menyelesaikan Knight’s Tour.
Kata Kunci :teori graf, siklus hamilton, knight’s tour, papan catur.
Universitas Sumatera Utara
ANALYSIS GRAPH TEORI ON KNIGHT’S TOUR PROBLEM
ABSTRACT
On this paper is talking about aplication from graph teori on the chess board. The interesting problem is making hamiltonian cyclus with the knight at chess board (Knight’s Tour). A Knight’s Tour at chess board is a travelling of the knights at chess board with every box just once travell. After you learn this paper, you can more easier to solve the Knight’s Tour problem.
Universitas Sumatera Utara
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Gambar
ii iii iv v vi vii viii
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Pembatasan Masalah 1.4 Tinjauan Pustaka 1.5 Tujuan Penulisan 1.6 Manfaat Penelitian 1.7 Metodologi Penelitian Bab 2 Landasan Teori 2.1 Sejarah Graf 2.2 Konsep Dasar Graf 2.3 Jenis – Jenis Graf 2.4 Lintasan (Walk) 2.5 Siklus (Cycle) atau Sirkuit (Circuit) 2.6 Terhubung (Connected) 2.7 Upagraf (SubGraf) dan Komplemen Upagraf 2.8 Deletion 2.9 Contraction 2.10 Cut Set 2.11 Beberapa Operasi Dalam Graf 2.12 Beberapa Graf Sederhana Khusus 2.13 Lintasan Dan Sirkuit Euler 2.14 Lintasan Dan Sirkuit Hamilton 2.15 Knight’s Tour Bab 3 Pembahasan Bab 4 Kesimpulan dan Saran 4.1 Kesimpulan 4.2 Saran Lampiran Daftar Pustaka
2 1 5 5 5 6 6 7 8 9 12 13 14 14 15 17 17 17 18 18 20 22 24 26 32 33
Universitas Sumatera Utara
DAFTAR GAMBAR
GAMBAR 2.1 Jembatan Konigzberg
8
2.2
Representasi Graf Dari Jembatan Konigzberg
9
2.3
Graf Sederhana
9
2.4
Graf dengan isolated verteks dan loop
10
2.5
Digraf dengan din dan dout
11
2.6
Digraf
13
2.7
Disconnected Graf
14
2.8
Graf Berarah Terhubung lemah dan kuat
15
2.9
Upagraf dan komplemen
16
2.10 Strongly Connected Component
16
2.11 Cut Set
17
2.12 Graf Lengkap
18
2.13 Graf Lingkaran
19
2.14 Graf Teratur
19
2.15 Graf Bipartite
20
2.16 Graf Bipartite dengan verteks
20
2.17 Euler Digraf
22
2.18 Hamiltonian Graf
23
2.19 Prominent Cities Dalam Graf
23
Universitas Sumatera Utara
