LAPORAN TUGAS AKHIR
Topik Tugas Akhir Kajian Matematika Murni
APLIKASI TEOREMA POLYA DALAM MENENTUKAN BANYAK GRAF SEDERHANA YANG TIDAK ISOMORFIK
TUGAS AKHIR Diajukan Kepada Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang sebagai Salah Satu Prasyarat untuk Mendapatkan Gelar Sarjana Pendidikan Matematika
Oleh: FIKI ROUDLOTUL JANNAH NIM: 201010060311047
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH MALANG 2014
MOTTO
“Dan mintalah pertolongan (kepada Allah SWT) dengan sabar dan shalat. Dan sesungguhnya yang demikian itu sungguh berat, kecuali bagi orang-orang yang khusyu’.” (QS: Al-Baqarah: 45) “Barang siapa menempuh jalan untuk mendapatkan ilmu, Allah akan memudahkan baginya jalan menuju surga.” (HR Muslim) “Berangkat dengan penuh keyakinan. Berjalan dengan penuh keikhlasan. Istiqomah dalam menghadapi cobaan.” “YAKIN, IKHLAS, ISTIQOMAH.” “Banyak kegagalan dalam hidup ini dikarenakan orang-orang tidak menyadari betapa dekatnya mereka dengan keberhasilan saat mereka menyerah.” (Thomas Alfa Edison)
PERSEMBAHAN
Syukur alhamdulillah kepada Allah SWT. yang telah memberikan rahmat dan karunia-Nya serta Rosulullah SAW. yang telah memberikan petunjuk ke jalan yang terang dan benar sehingga penulis bisa menyelesaikan Tugas Akhir ini. Dengan tulus ku persembahkan Tugas Akhir ini untuk: 1. Ayahanda Warsito dan Ibunda Tumini (Almh), terima kasih banyak atas do’a, nasihat, semangat, dan kasih sayang kepadaku setiap waktu. 2. Adik-adikku tercinta Syaifullah Ahmad, M. Miftahul Huda, dan Nahdliyah S. Jamilah, dengan candaan dan ulah mereka yang mampu membangkitkan semangatku lagi. 3. Dosen-dosen program studi Pendidikan Matematika FKIP UMM yang telah mendidik, membimbing dan memberikan arahan kepadaku selama ini. 4. Sahabat Seperjuanganku Ida Prawati, Mba Anggi, Mba Feni, Yoni Oktavia, Devi Yolanda, Erni MS dan Frimadana S. Terima kasih atas kebersamaan, candaan, motivasi, masukan ide serta dukungan yang kalian berikan. 5. Terimakasih juga untuk rekan-rekan sejawat (Matkom 2010, khususnya kelas A) yang telah banyak memberikan dukungan dan sumbangan pikiran yang bermanfaat dalam penulisan skripsi ini. 6. Sahabat Shohib Kos, Mba Umi, Mba Wiwik, Mba Devi, Mba Nika dan seluruh penghuni Salsabila Apartment yang selalu menghibur, memberi semangat dan menemani dengan candaan yang luar biasa. 7. Mamasku Dana YC beserta keluarga tercinta, terima kasih atas dukungan, semangat, nasihat, dan kehadiranmu yang mampu memberi warna di hidupku serta selalu mendengarkan keluh kesahku.
KATA PENGANTAR
Syukur Alhamdulillah penulis panjatkan kehadirat Allah SWT atas rahmat, hidayah, dan inayah-Nya sehingga penulis dapat menyelesaikan Skripsi dengan judul “Aplikasi Teorema Polya dalam Menentukan Banyak Graf Sederhana yang tidak Isomorfik”. 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 menghaturkan rasa hormat dan terima kasih kepada: 1. Dr. Yus M. 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. 2. Drs. Hendarto Cahyono, M.Si selaku dosen pembimbing II yang telah meluangkan waktu dan kesabaran dalam memberi bimbingan, pengarahan serta nasihat kepada penulis sehingga skripsi ini dapat terselesaikan. 3. Teman-teman tercinta yang selalu memberi semangat dan pihak-pihak lain yang tidak dapat disebutkan satu persatu yang juga turut mendukung terselesaikannya tugas akhir ini. Penulis menyadari tentunya tugas akhir ini masih jauh dari kesempurnaan. Oleh karena, itu kritik dan saran yang membangun sangat penulis harapkan demi menjadikan skripsi ini lebih sempurna. Penulis berharap semoga skripsi ini dapat memberikan manfaat bagi pembaca pada umumnya dan bagi penulis pada khususnya. Amin. Malang, 14 Oktober 2014
Penulis
DAFTAR ISI
HALAMAN JUDUL ........................................................................................ i LEMBAR PERSETUJUAN ............................................................................ ii LEMBAR PENGESAHAN ............................................................................. iii SURAT PERNYATAAN ................................................................................. iv MOTTO ............................................................................................................ v LEMBAR PERSEMBAHAN .......................................................................... vi KATA PENGANTAR ...................................................................................... vii ABSTRAK ........................................................................................................ viii DAFTAR ISI ..................................................................................................... x DAFTAR GAMBAR ........................................................................................ xii DAFTAR LAMPIRAN .................................................................................... xiii BAB I PENDAHULUAN 1.1. Latar Belakang .................................................................................... 1 1.2. Rumusan Masalah ............................................................................... 4 1.3. Batasan Masalah ................................................................................. 5 1.4. Tujuan Penelitian ................................................................................ 5 1.5. Manfaat Penelitian .............................................................................. 5 BAB II TINJAUAN PUSTAKA 2.1. Konsep Dasar Graf .............................................................................. 6 2.2. Macam-macam Graf ........................................................................... 12 2.3. Graf Isomorfik (Isomorphic Graph) ................................................... 13 2.4. Definisi dan Teorema Aljabar yang Mendukung Teorema Polya ...... 15 2.5. Teorema Polya .................................................................................... 23 2.6. Aplikasi Teorema Polya pada Graf Sederhana dengan Banyak Titik ........................................................................................... 27 BAB III PEMBAHASAN 3.1. Teorema Polya pada Graf Sederhana .................................................. 34 3.1.1. Aplikasi Teorema Polya I .......................................................... 39
3.1.2. Aplikasi Teorema Polya II ......................................................... 39 BAB IV PENUTUP 4.1. Kesimpulan ......................................................................................... 41 4.2. Saran ................................................................................................... 42 DAFTAR PUSTAKA ....................................................................................... 44 LAMPIRAN-LAMPIRAN .............................................................................. 45
DAFTAR GAMBAR
Gambar 1.1 Contoh graf .................................................................................... 3 Gambar 1.2 (a) isomorfik dengan (b), tetapi (a) tidak isomorfik dengan (c) ..... 3 Gambar 2.1 Graf kosong
.............................................................................. 6
Gambar 2.2 Contoh representasi graf ................................................................ 7 Gambar 2.3 Contoh graf (a) graf dengan loop dan (b) graf sederhana .............. 7 Gambar 2.4 Contoh adjancent dan incident ...................................................... 8 Gambar 2.5 Contoh derajat titik ......................................................................... 8 Gambar 2.6 Contoh jalan, jejak, lintasan, dan sikel ........................................... 10 Gambar 2.7 Contoh graf terhubung dan graf tidak terhubung ........................... 11 Gambar 2.8 Graf lengkap
.......................................................... 12
Gambar 2.9 Graf teratur (a) Derajat 0, (b) Derajat 1, dan (c) Derajat 2 ............ 12 Gambar 2.10 Graf lingkaran Gambar 2.11
isomorfik dengan
...................................................... 13 , tetapi
tidak isomorfik dengan
.... 13
Gambar 2.12 Dua buah graf yang tidak isomorfik ............................................. 14
DAFTAR LAMPIRAN
Lampiran 1: Elemen-elemen
......................................................................... 46
Lampiran 2: Pembangkit indeks sikel Lampiran 3: Elemen-elemen
.......................................................................... 48
Lampiran 4: Pembangkit indeks sikel Lampiran 5: Elemen-elemen
........................................................... 49
.......................................................................... 51
Lampiran 6: Pembangkit indeks sikel Lampiran 7: Elemen-elemen
........................................................... 47
........................................................... 53
.......................................................................... 55
Lampiran 8: Bentuk-bentuk Graf Sederhana yang tidak saling Isomorfik ........ 64
DAFTAR PUSTAKA
Abdussakir, Azizah, Nilna Niswatin., dan Nofandika, Fifi Framelia. 2009. Teori Graf Topik Dasar untuk Tugas Akhir/Skripsi. Malang: UIN-Malang Press. Aldous, Joan M. dan Wilson, Robin J. 2004. Graphs and Applications an Introductory Approach. London: Springer. Beachy, John A. dan Blair, William D. 2006. Abstract Algebra Third Edition. Long Grove: Waveland Press. Cahyono, Hendarto. 2000. Pengantar Teori Graph. Malang: Universitas Muhammadiyah Malang. Gutman, Ivan. 2008. The Chemical Formula and Its Mathematical background. The Teaching of Mathematics Vol. XI No. 2 Hal. 53-61. Harris, John, Hirst, Jeffry L., dan Mossinghoff, Michael. 2008. Combinatorics and Graph Theory. New York: Springer. Judson, Thomas W. 2009. Abstract Algebra Theory and Applications. Boston: GNU Free Documentation Lisence. Lipschutz, Seymour, dan Lipson, Marc. 2007. Schaum’s Outlines of Theory and Problems of Discrete Mathematics. New York: McGRAW-HILL. Munir, Rinaldi. 2012. Matematika Diskrit. Bandung: Informatika. Ni’mah, Khomsiatun. 2013. Aplikasi Teorema Polya untuk Menghitung Banyaknya Graf Sederhana yang Tidak Isomorfik. Cakrawala Pendidikan Vol. 15, No. 2 Oktober 2013, Hal. 184-193. Riyanto, M. Zaki. 2011. Pengantar Aljabar Abstrak I: Pendahuluan Teori Grup. Hal. 18-23. Rotman, Joseph J. 2005. A First Course in Abstract Algebra Third Edition. Urbana: Prentice Hall. Vasudev, C. 2006. Graph Theory with Applications. New Delhi: New Age International Publishers.
