LAPORAN TUGAS AKHIR Topik Tugas Akhir : Kajian Matematika
Perumuman Bilangan Ramsey untuk Gabungan Graf Bintang dan Graf Bipartit Lengkap πΉ(πΊπ , π²π,π ) untuk π < π < ππ
TUGAS AKHIR Diajukan Kepada Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang Sebagai Salah Satu Prasyarat untuk Mendapatkan Gelar Sarjana Pendidikan Matematika
Oleh : Mega Suliani NIM : 201110060311005
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH MALANG 2015 i
LEMBAR PERSETUJUAN
Tugas Akhir dengan Judul :
PERUMUMAN BILANGAN RAMSEY UNTUK GABUNGAN GRAF BINTANG DAN GRAF BIPARTIT LENGKAP πΉ(πΊπ , π²π,π) UNTUK π < π < ππ
Oleh : MEGA SULIANI NIM : 201110060311005
telah memenuhi persyaratan untuk dipertahankan di depan Dewan Penguji dan disetujui pada tanggal 1 April 2015
Menyetujui, Pembimbing I
Dr. Yus Mochamad Cholily, M.Si
Pembimbing II
Drs. Hendarto Cahyono, M.Si
ii
LEMBAR PENGESAHAN
Dipertahankan di depan Dewan Penguji Tugas Akhir Program Studi Pendidikan Matematika Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang Dan Diterima untuk Memenuhi Persyaratan Memperoleh Gelar Sarjana (S1) Pendidikan Matematika Pada Tanggal : 25 April 2015
Mengesahkan : Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang
Dekan,
Dr. Poncojari Wahyono, M.Kes
Dewan Penguji :
1. Dr. M. Mahfud Effendi, M.M
Tanda Tangan 1. β¦β¦β¦β¦β¦β¦β¦.. 2. β¦β¦β¦β¦β¦β¦
2. Alfiani Athma Putri R., M.Pd 3. Dr. Yus Mochamad Cholily, M.Si 4. Drs. Hendarto Cahyono, M.Si
3. β¦β¦β¦β¦β¦β¦β¦.. 4β¦β¦β¦β¦β¦β¦...
iii
SURAT PERNYATAAN Saya yang bertanda tangan di bawah ini: Nama
: Mega Suliani
Tempat tanggal lahir
: Tarakan. 03 Mei 1993
NIM
: 201110060311005
Fakultas
: Keguruan dan Ilmu Pendidikan
Program Studi
: Pendidikan Matematika
Dengan ini menyatakan dengan sebenar-benarnya bahwa: 1. Skripsi dengan berjudul βPerumuman Bilangan Ramsey untuk Gabungan Graf Bintang dan Graf Bipartit Lengkap π
(ππ , πΎ2,2 ) untuk 6 < π < 10β adalah hasil karya saya, dan dalam naska skripsi ini tidak terdapat karya ilmiah yang pernah diajukan oleh orang lain untuk memperoleh gelar akademik di suatu Perguruan Tinggi, dan tidak terdapat karya atau pendapat yang pernah ditulis atau diterbitkan oleh orang lain, baik sebagian atau keseluruhan, kecuali secara tertulis dikutip dalam naskah ini dan disebutkan dalam sumber kutipan atau daftar pustaka. 2. Apabila ternyata di dalam naskah skripsi ini dapat dibuktikan terdapat unsurunsur plagiasi, saya bersedia skripsi ini digugurkan dan gelar akademik yang telah saya peroleh dibatalkan, serta diproses dengan ketentuan hokum yang berlaku. 3. Skripsi ini dapat dijadikan sumber pustaka yang merupakan hak bebas royalty non eksklusif Demikian pernyataan ini saya buat dengan sebenar-benarnya untuk dipergunakan sebagaimana mestinya. Malang, 1 April 2015 yang menyatakan, MEGA SULIANI NIM: 201110060311005
iv
PERSEMBAHAN
Syukur alhamdulillah kepada Allah SWT yang telah memberikan rahmat dan hidayah-Nya serta Rosulullah SAW yang memberikan petunjuk ke jalan terang dan benar sehingga penulis dapat menyelesaikan Tugas Akhir ini. Kupersembahkan skripsi ini untuk Bapak dan Ibuku yang aku sayangi dan aku patuhi, terima kasih atas semua yang telah beliau berikan dan dengan Tulus Ikhlas, Membesarkan, Menyayangi, Membimbing, Mendoβakan, serta Mendukung dan Berkorban untuk masa depan ku. Kalian selalu hadir dalam setiap Doβaku, saudaraku yang selalu memberikan motivasi dan masukkan dalam penyusunan tugas akhir ini. Sahabatsahabatku di Basecamp terima kasih atas motivasi dan dukungan kalian selama ini, peluk sayang untuk kalian.
v
KATA PENGANTAR
Puji syukur Alhamdulillah kepada Allah SWT atas rahmat, hidayah, dan inayah-Nya sehingga penulis dapat menyelesaikan Skripsi dengan judul βPerumuman Bilangan Ramsey untuk Gabungan Graf Bintang dan Graf Bipartit Lengkap π
(ππ , πΎ2,2 ) untuk 6 < π < 10β.
Sholawat serta salam tercurahkan kepada
Rasulullah Muhammad SAW, keluarga serta sahabatnya. Penulis menyadari bahwa Skripsi ini dapat terselesaikan berkat bimbingan, bantuan, dan motivasi dari berbagai pihak. Oleh karena itu dengan hati yang tulus penulis menghanturkan rasa hormat dan terima kasih kepada Dr. Yus Mochamad Cholily, M.Si selaku dosen pembimbing I yang telah meluangkan waktu dan kesabaran dalam memberi bimbingan, pengarahan serta nasihat kepada penulis sehingga skripsi ini dapat terselesaikan, dan Drs. Hendarto Cahyono, M.Si selaku dosen pembimbing II yang telah meluangkan waktu dan kesabaran dalam member bimbingan, pengarahan serta nasihat kepada penulis sehingga skripsi ini dapat terselesaikan. Semoga Allah SWT menunjukan jalan dan memberikan cahaya-Nya, serta melapangkan dada kita dengan limpahan iman dan keindahan tawakkal kepada-Nya. Penulis berharap semoga skripsi ini bermanfaat bagi semua pihak yang berkepentingan. Namun demikian tiada manusia yang sempurna, oleh karena itu kritik dan saran yang membangun sangat kami harapkan untuk menjadikan skripsi ini lebih sempurna.
Malang, 1 April 2015
Penulis
vi
DAFTAR ISI
Halaman Judul ............................................................................................................. i Lembar Persetujuan ................................................................................................... ii Lembar Pengesahan ...................................................................................................iii Halaman Pernyataan Keaslian ................................................................................. iv Halaman Persembahan ............................................................................................... v Kata Pengantar........................................................................................................... vi Abstrak ....................................................................... Error! Bookmark not defined. DAFTAR ISI ............................................................................................................... ix DAFTAR GAMBAR .................................................................................................. xi BAB I PENDAHULUAN ............................................................................................ 1 1.1.
Latar Belakang................................................................................................ 1
1.2.
Rumusan Masalah .......................................................................................... 3
1.3.
Pembatasan Masalah ...................................................................................... 4
1.4.
Tujuan Kajian ................................................................................................. 4
1.5.
Manfaat Kajian ............................................................................................... 5
BAB II TINJAUAN PUSTAKA ................................................................................. 7 2.1.
Graf ................................................................................................................. 7
2.2.
Berdekatan dan Terkait................................................................................... 9
2.3.
Derajat Titik.................................................................................................. 10
2.4.
Isomorfik ...................................................................................................... 12
2.5.
Subgraf ......................................................................................................... 13
2.6.
Komplemen Suatu Graf ................................................................................ 13
2.7.
Gabungan graf .............................................................................................. 14
2.8.
Graf Khusus .................................................................................................. 14
2.9.
Pewarnaan Graf ............................................................................................ 17
2.10.
Bilangan Kromatik.................................................................................... 20
vii
2.11.
Bilangan Ramsey ...................................................................................... 23
BAB III PEMBAHASAN ......................................................................................... 29 3.1.
Bilangan Ramsey untuk Gabungan Graf Bintang dan Graf Bipartit Lengkap 29
BAB IV KESIMPULAN DAN SARAN................................................................... 37 4.1.
Kesimpulan ................................................................................................... 37
4.2.
Saran ............................................................................................................. 37
DAFTAR PUSTAKA ................................................................................................ xii
viii
DAFTAR GAMBAR Gambar 2.1 Graf πΊ ...........................................................................................
7
Gambar 2.2 Contoh graf sederhana, terhubung, rangkap, dan terpisah ...........
8
Gambar 2.3 Contoh graf berdekatan dan terkait ..............................................
9
Gambar 2.4 Contoh graf πΊ (derajat titik) .........................................................
10
Gambar 2.5 Graf beraturan ..............................................................................
10
Gambar 2.6 Graf dan komplemennya ..............................................................
12
Gambar 2.7 Gabungan graf ..............................................................................
13
Gambar 2.8 Graf bipartit ..................................................................................
14
Gambar 2.9 Graf bipartit lengkap πΎ3,3 ............................................................
14
Gambar 2.10 Graf bintang π5 ...........................................................................
15
Gambar 2.11 Graf sikel ....................................................................................
15
Gambar 2.12 Graf kincir π4 ............................................................................
16
Gambar 2.13 Pewarnaan titik ...........................................................................
17
Gambar 2.14 Graf bipartit lengkap order π......................................................
20
Gambar 2.15 Ilustrasi bukti π
(πΎ3 , πΎ3 ) = 6 .....................................................
23
Gambar 3.1 Ilustrasi graf untuk bilangan Ramsey π
(π7 , πΎ2,2 ) .......................
32
Gambar 3.2 Ilustrasi graf untuk bilangan Ramsey π
(π8 , πΎ2,2 ) .......................
33
Gambar 3.3 Ilustrasi graf untuk bilangan Ramsey π
(π9 , πΎ2,2 ) .......................
35
ix
DAFTAR PUSTAKA
Abdussakir, dkk. 2009. Teori Graf. Malang: UIN-Malang Press. Baskoro, E.T., Surahmat, Nababan, S. M., dan Miller, M.. 2002. On Ramsey Numbers for Tree Versus Wheels of Five or Six vertices. Graph Combin., Vol. 18, 717-712. Cahyono, Hendarto. 2000. Pengantar Teori Graph. Jurusan Pendidikan Matematika dan Komputasi FKIP UMM. Chartrand, Gary dan Lesniak, L.. 2000. Graphs and Diagraphs. California: Originally published by Chapman & Hall. Chartrand, Gary dan Ping Zhang. 2009. Chromatic graph theory. (Discrete mathematics and its applications). Chapman & Hall_CRC. Dickson, James Odziemiec. 2011. An Introduction to Ramsey Theory on Graphs. (Thesis). Virginia. Gross, Jonathan L., Jay Yellen, dan Ping Zhang. (2013). Handbook of Graph Theory, Second Edition. (Discrete Mathematics and Its Applications). Chapman and Hall_CRC. Harris, John, Jeffry L. Hirst, dan Michael Mossinghoff. 2010. Combinatorics and Graph Theory.(Undergraduate Texts in Mathematics).Springer. Hasmawati. 2007. Bilangan Ramsey untuk Graf Gabungan Bintang. Disertasi. Bandung: ITB Landman, B. dan A. Robertson. 2003. Ramsey Theory on the Integers. AMS. Munir, Rinaldi. 2003. Matematika Diskrit. Bandung: Informatika. Radziszowski, S.P.. 2014. Small Ramsey Numbers. The Electronic Journal of Combinatorics. Rosyida, Isnaini. 2004. Batas Atas Bilangan Ramsey untuk Graf Bintang dan Graf Bipartit Lengkap. Jurusan Matematika FMIPA UNNES. Sari, Widya Rahmah. 2012. Batas Atas π
(πΆ4 , ππ ) untuk π β₯ 6. Jurnal Matematika UNAND, Vo. 1. No. 1. Surahmat. 2003. Bilangan Ramsey Untuk Graph Roda. Disertasi. Departemen Matematika. FMIPA ITB. Suryadi, 2012. Bilangan Ramsey Bipartit untuk Lingkaran Genap dan Graf πΎ2,2. Padang: Pascasarjana Program Studi Matematika Universitas Andalas. Wallis, W.D. (auth.). 2012. A Beginner's Guide to Discrete Mathematics. BirkhΓ€user Boston.
x
