FACE COLOURING PADA LIMAS, PRISMA, DAN GABUNGAN LIMAS DAN PRISMA
SKRIPSI
Oleh:
RIRIN SALUSININGSIH NIM: 04510002
JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI (UIN) MAULANA MALIK IBRAHIM MALANG MALANG 2009
2
HALAMAN PENGAJUAN FACE COLOURING PADA LIMAS, PRISMA, DAN GABUNGAN LIMAS DAN PRISMA
SKRIPSI
Diajukan Kepada: Universitas Islam Negeri Maulana Malik Ibrahim Malang Untuk Memenuhi Salah Satu Persyaratan Dalam Memperoleh Gelar Sarjana Sains (S.Si)
Oleh: RIRIN SALUSININGSIH NIM. 04510002
JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI (UIN) MAULANA MALIK IBRAHIM MALANG MALANG 2009
3
HALAMAN PERSETUJUAN
FACE COLOURING PADA LIMAS, PRISMA, DAN GABUNGAN LIMAS DAN PRISMA
SKRIPSI Oleh: RIRIN SALUSININGSIH NIM. 04510002
Telah Diperiksa dan Disetujui untuk Diuji Tanggal: 23 Juli 2009
Dosen Pembimbing I
Dosen Pembimbing II
Evawati Alisah, M.Pd NIP. 150 291 271
Ahmad Barizi, M.A NIP. 150 283 991
Mengetahui, Ketua Jurusan Matematika
Sri Harini, M. Si NIP. 150 318 321
4
FACE COLOURING PADA LIMAS, PRISMA, DAN GABUNGAN LIMAS DAN PRISMA
SKRIPSI Oleh: RIRIN SALUSININGSIH NIM. 04510002
Telah Dipertahankan di Depan Dewan Penguji Skripsi dan Dinyatakan Diterima sebagai Salah Satu Persyaratan untuk Memperoleh Gelar Sarjana Sains (S.Si) Tanggal 28 Juli 2009 Susunan Dewan Penguji
Tanda Tangan
1. Penguji Utama
: Wahyu H. Irawan, M. Pd NIP. 150 300 415
(
)
2. Ketua
: Abdussakir, M. Pd NIP. 150 327 247
(
)
3. Sekretaris
: Evawati Alisah, M. Pd NIP. 150 291 271
(
)
4. Anggota
: Ahmad Barizi, M. A NIP. 150 283 991
(
)
Mengetahui dan Mengesahkan, Ketua Jurusan Matematika
Sri Harini, M. Si NIP. 150 318 321
5
SURAT PERNYATAAN Yang bertanda tangan di bawah ini: Nama : Ririn Salusiningsih NIM : 04510002 Fakultas : Sains dan Teknologi Judul Skripsi : Face Colouring pada Limas, Prisma, dan Gabungan Limas dan Prisma Menyatakan bahwa skripsi tersebut adalah karya saya sendiri dan bukan karya orang lain, baik sebagian maupun keseluruhan, kecuali dalam bentuk kutipan yang telah disebutkan sumbernya. Selanjutnya apabila dikemudian hari ada “klaim” dari pihak lain, bukan menjadi tanggung jawab Dosen Pembimbing atau Pengelola Fakultas Sains dan Teknologi Universitas Islam Negeri (UIN) Malang, tetapi menjadi tanggung jawab saya sendiri. Demikian surat pernyataan ini saya buat dengan sebenar-benarnya dan apabila pernyataan ini tidak benar, saya bersedia mendapat sanksi akademis. Malang, 23 Juli 2009 Menyatakan,
Ririn Salusiningsih
6
MOTTO
“Orang yang cerdas adalah yang berpikir setiap kali berzikir dan berzikir setiap kali berpikir. Dengan demikian, kalbu mereka bersih, sehingga semua ucapan yang keluar dari lidah, pasti mengandung hikmah.” (Hasan al-Bashri)
7
PERSEMBAHAN
Untuk Ibunda Masturoh dan Ayahanda Parmin serta kakak-kakak (Yuni, Agus, Nurrahim, Aminatun).
8
KATA PENGANTAR
ÉΟŠÏm§9$# Ç⎯≈uΗ÷q§9$# «!$# ÉΟó¡Î0 Syukur Alhamdulillah ke hadirat Allah SWT, yang telah melimpahkan rahmat dan hidayahNya kepada penulis sehingga dapat menyelesaikan skripsi dengan judul Face Colouring pada Limas, Prisma, dan Gabungan Limas dan Prisma. Shalawat serta salam semoga tercurahkan kepada Nabi besar Muhammad SAW yang telah menunjukkan dari jalan yang gelap gulita menuju jalan yang terang benderang yaitu ad-Dinul Islam. Dalam penulisan skripsi ini, penulis menyadari bahwa tidak akan mendapatkan hasil yang baik tanpa adanya bimbingan, bantuan, dorongan, saran serta do’a dari berbagai pihak. Maka dalam kesempatan ini, penulis menyampaikan terima kasih kepada: 1. Prof. Dr. H. Imam Suprayogo selaku Rektor Universitas Islam Negeri (UIN) Maulana Malik Ibrahim malang. 2. Prof. Drs. Sutiman Bambang Sumitro, SU., DSc selaku Dekan Fakultas Saintek Universitas Islam Negeri (UIN) Maulana Malik Ibrahim malang. 3. Sri Harini, M.Si selaku Ketua Jurusan matematika Universitas Islam Negeri (UIN) Maulana Malik Ibrahim malang. 4. Evawati Alisah, M.Pd selaku dosen pembimbing yang selalu memberikan bimbingannya kepada kami. 5. Ahmad Barizi, M.A selaku dosen pembimbing Integrasi Sains dan Agama.
i
9
6. Abdussakir, M. Pd yang telah memberikan masukan-masukan untuk penulis. 7. Bapak dan Ibu tercinta dan seluruh keluarga besar yang tiada lelah memberikan do’a dan kasih sayang serta kepercayaan. 8. Teman-teman Matematika angkatan 2004 yang telah mewarnai hari-hariku dan selalu memberikan keceriaan selama kuliah di UIN Malang. 9. Teman-teman kost Kerto Pamuji IA yang telah memberikan motivasi dan bantuan. 10. Semua pihak yang tidak bisa disebutkan satu persatu, terima kasih sudah bersedia mendengarkan keluhan penulis dan telah membantu dalam menyelesaikan laporan ini. Semoga Allh SWT membalas kebaikan mereka semua. Penulis berharap, semoga skripsi ini bermanfaat. Amin…. Malang, 30 Juli 2009
Penulis
ii
10
DAFTAR ISI
HALAMAN JUDUL HALAMAN PENGAJUAN HALAMAN PERSETUJUAN HALAMAN PENGESAHAN HALAMAN PERNYATAAN KEASLIAN TULISAN HALAMAN MOTTO HALAMAN PERSEMBAHAN KATA PENGANTAR ...................................................................................... i DAFTAR ISI ..................................................................................................... iii DAFTAR GAMBAR ........................................................................................ v ABSTRAK ........................................................................................................ vii BAB I : PENDAHULUAN ...............................................................................
1
1. 1 Latar Belakang ................................................................................................... 1
1.2 Rumusan Masalah ...................................................................................
5
1.3 Tujuan Masalah .......................................................................................
6
1.4 Manfaat Penelitian ..................................................................................
6
1.5 Metode Penelitian ...................................................................................
7
1.6 Sistematika Pembahasan .........................................................................
8
BAB II : KAJIAN PUSTAKA.......................................................................... 10 2.1 Konsep Graf dalam Islam........................................................................ 10 2.2 Definisi Graf ........................................................................................... 12 2.3 Derajat Suatu Titik .................................................................................. 14 2.4 Graf Terhubung ....................................................................................... 18 2.5 Graf dengan Nama Tertentu .................................................................... 20 2.5.1 Graf Komplit ........................................................................ 20 2.5.2 Graf Bipartisi........................................................................ 21 2.5.3 Graf Bipartisi Komplit ......................................................... 22 iii
11
2.5.4 Graf Sikel ............................................................................... 22 2.5.5 Graf Lintasan .......................................................................... 23 2.5.6 Graf Kubus ............................................................................. 23 2.5.7 Hutan (forest) ......................................................................... 24 2.6 Macam-macam Bangun Ruang ............................................................... 25 2.6.1 Prisma..................................................................................... 25 2.6.2 Limas ...................................................................................... 27 2.6.3 Bola ........................................................................................ 29 2.7 Pewarnaan Pada Graf .............................................................................. 29 2.7.1 Pewarnaan Titik (Vertex Colouring) ...................................... 29 2.7.2 Pewarnaan Sisi (Edge Colouring) .......................................... 31 2.7.3 Pewarnaan Permukaan (Face Colouring) .............................. 32
BAB III : PEMBAHASAN 3.1 Pewarnaan Permukaan (Face colouring) pada Limas Segi- ................ 35 3.2 Pewarnaan Permukaan (Face colouring) pada Prisma Segi- ............... 42 3.3 Pewarnaan Permukaan (Face colouring) pada Gabungan Limas Segidan Prisma Segi- ................................................................................... 51
BAB IV : PENUTUP 4.1 Kesimpulan ............................................................................................. 63 4.2 Saran........................................................................................................ 64
DAFTAR PUSTAKA
iv
12
DAFTAR GAMBAR Gambar 2.1.1 Representasi Graf Hubungan antara Allah, Manusia, dan Alam ..10 Gambar 2.2.1 Graf dan Multigraf ....................................................................... 13 Gambar 2.2.2 Graf dan Subgraf .......................................................................... 14 Gambar 2.3.1 Derajat Suatu Titik Graf .............................................................. 15 Gambar 2.3.2 Graf Beraturan .............................................................................. 16 Gambar 2.3.3 Ilustrasi Graf dari suatu Barisan/Formasi Orang-orang mukmin yang berperang ............................................................................ 16 Gambar 2.4.1 Jalan pada Graf ........................................................................... 19 Gambar 2.4.2 Graf Terhubung dan Graf Takterhubung ..................................... 20 Gambar 2.5.1 Graf Komplit ................................................................................ 21 Gambar 2.5.2 Graf Bipartisi ................................................................................ 21 Gambar 2.5.3 Graf Bipartisi Komplit ................................................................. 22 Gambar 2.5.4 Graf Sikel ..................................................................................... 22 Gambar 2.5.5 Graf Lintasan ................................................................................ 23 Gambar 2.5.6 Graf Kubus ................................................................................... 24 Gambar 2.5.7 Hutan (forest) dan pohon (tree).................................................... 24 Gambar 2.6.1 Prisma Segitiga ABCDEF ............................................................ 25 Gambar 2.6.2 Ilustrasi Rukun Iman .................................................................... 26 Gambar 2.6.3 Limas Segiempat T. ABCD .......................................................... 28 Gambar 2.6.4 Ilustrasi Rukun Islam ................................................................... 28 Gambar 2.7.1 Pewarnaan Titik pada G1, G2, dan G3........................................... 30 Gambar 2.7.2 Pewarnaan Sisi pada G1, G2, dan G3 ............................................ 31 Gambar 2.7.3 Face Colouring graf G ................................................................. 32 Gambar 2.8.4 Representasi Graf dari Pewarnaan untuk Suatu Identitas Manusia.33 Gambar 3.1.1 Limas Segitiga T. ABC ................................................................ 35 Gambar 3.1.2 Face Colouring pada Limas Segitiga T. ABC ............................. 36 Gambar 3.1.3 Limas Segiempat T. ABCD ......................................................... 36 Gambar 3.1.4 Face Colouring pada Limas Segiempat T. ABCD ....................... 37 Gambar 3.1.5 Limas Segilima T. ABCDE ......................................................... 37 v
13
Gambar 3.1.6 Face Colouring pada Limas Segilima T. ABCDE ....................... 38 Gambar 3.1.7 Limas Segienam T. ABCDEF ...................................................... 38 Gambar 3.1.8 Face Colouring pada Limas Segienam T. ABCDEF.................... 39 Gambar 3.2.1 Prisma Segitiga ABCDEF ........................................................... 43 Gambar 3.2.2 Face Colouring pada Prisma Segitiga ABCDEF ......................... 43 Gambar 3.2.3 Prisma Segiempat ABCDEFGH .................................................. 44 Gambar 3.2.4 Face Colouring pada Prisma Segiempat ABCDEFGH ................ 44 Gambar 3.2.5 Prisma Segilima ABCDEEFGHIJ ............................................... 45 Gambar 3.2.6 Face Colouring pada Prisma Segilima ABCDEFGHIJ ............... 46 Gambar 3.2.7 Prisma Segienam ABCDEFGHIJKL ........................................... 46 Gambar 3.2.8 Face Colouring pada Prisma Segienam ABCDEFGHIJKL ......... 47 Gambar 3.3.1 Limas Segitiga T. DEF dan Prisma Segitiga ABCDEF ............... 51 Gambar 3.3.2 Gabungan Limas Segitiga T. DEF dan Prisma Segitiga ABCDEF 51 Gambar 3.3.3 Face Colouring pada Bangun Ruang T. ABCDEF ...................... 52 Gambar 3.3.4 Limas Segiempat T. EFGH dan Prisma Segiempat ABCDEFGH 53 Gambar 3.3.5 Gabungan Limas Segiempat T. EFGH dan Prisma Segiempat ABCDEFGH ....................................................................................................... 53 Gambar 3.3.6 Face Colouring pada Bangun Ruang T. ABCDEFGH................. 54 Gambar 3.3.7 Limas Segilima T. FGHIJ dan Prisma Segilima ABCDEFGHIJ . 55 Gambar 3.3.8 Gabungan Limas Segilima T. FGHIJ dan Prisma Segilima ABCDEFGHIJ .................................................................................................... 55 Gambar 3.3.9 Face Colouring pada Bangun Ruang T. ABCDEFGHIJ.............. 56 Gambar
3.3.10
Limas
Segienam
T.
GHIJKL
dan
Prisma
Segienam
ABCDEFGHIJKL................................................................................................ 57 Gambar 3.3.11 Gabungan Limas Segienam T. GHIJKL dan Prisma Segienam ABCDEFGHIJKL................................................................................................ 57 Gambar 3.3.12 Face Colouring pada Bangun Ruang T. ABCDEFGHIJKL ....... 58
vi
14
ABSTRAK Salusiningsih, Ririn. 2009. Face Colouring pada Limas, Prisma, dan Gabungan Limas dan Prisma. Skripsi, Jurusan Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri Maulana Malik Ibrahim Malang. Pembimbing: Evawati Alisah, M. Pd Ahmad Barizi, M.A Kata Kunci: Face Colouring, Limas, Prisma, Gabungan Limas dan Prisma.
Salah satu permasalahan dalam graf adalah face colouring. Face colouring pada graf bidang adalah permberian warna pada setiap permukaan di sedemikian hingga tidak ada dua permukaan yang dipisahkan atau dibatasi oleh sebuah sisi mempunyai warna sama. Penelitian ini dilakukan dengan tujuan untuk menentukan bilangan kromatik permukaan (face chromatic number) pada limas, prisma, dan gabungan limas dan prisma. Bilangan kromatik permukaan pada adalah bilangan terkecil sehingga permukaan di dapat diwarnai dengan warna, dan dilambangkan dengan . Langkah-langkah yang dilakukan adalah: a. Menentukan bilangan kromatik pada beberapa kasus; b. Mencari pola dari bilangan kromatik pada langkah (a); c. Pola yang diperoleh dinyatakan sebagai konjektur; d. Konjektur tersebut dinyatakan sebagai teorema dan dibuktikan. Berdasarkan hasil pembahasan dapat diperoleh bilangan kromatik permukaan (face chromatic number) pada limas adalah 4, untuk n ganjil ,
,
3
3, untuk n genap
Bilangan kromatik permukaan (face chromatic number) pada prisma adalah 4, untuk n ganjil ,
,
3
3, untuk n genap
Bilangan kromatik permukaan (face chromatic number) pada gabungan limas dan prisma adalah 4, untuk n ganjil ,
,
3
3, untuk n genap
Untuk penulisan skripsi selanjutnya diharapkan untuk mengkaji masalah face colouring pada graf-graf yang lain atau komputasi pemprograman sehingga hasil lebih cepat, akurat, dan tampilannnya bagus.
vii
15
BAB I PENDAHULUAN
1.1 Latar Belakang Matematika merupakan disiplin ilmu yang mempunyai sifat yang khas jika dibandingkan dengan ilmu yang lain. Hal ini sangat dimungkinkan karena matematika mempunyai struktur dengan keterkaitan yang kuat dan jelas antara satu dengan yang lainnya serta pola pikir yang bersifat deduktif dan konsisten. Matematika bukan hanya ilmu warisan dari para ahli matematika pada zaman dahulu melainkan ilmu yang berkembang mengikuti perkembangan zaman. Cabang dari ilmu matematika yang masih berkembang di antaranya adalah Matematika Diskrit, Numerik, Analisis Real, dan lain-lain. Dari berbagai cabang ilmu matematika, Matematika Diskrit adalah cabang ilmu yang mengkaji obyekobyek diskrit. Obyek diskrit merupakan obyek yang terdiri dari sejumlah berhingga elemen berbeda dan tidak bersambungan. Materi yang terkandung dalam Matematika Diskrit mencakup beberapa hal, salah satunya adalah teori graf. Teori graf adalah cabang matematika yang cukup penting karena mempunyai segi di banyak bidang ilmu, misalnya di bidang fisika, kimia, ilmu komunikasi, teknologi komputer, rekayasa listrik dan sipil, arsitektur, penelitian operasional (operational research) genetika, psikologi, sosiologi, ekonomi, antropologi, dan linguistik. Teori graf juga berkaitan erat dengan beberapa cabang matematika yang lain, misalnya teori “grup”, teori matriks, analisis numerik, teori peluang, topologi, dan kombinatorika (Suryanto,
1
16 2
1986:1). Representasi visual dari graf adalah dengan menyatakan obyek sebagai titik sedangkan hubungan antara obyek dinyatakan dengan garis/sisi. Dalam Islam, himpunan titik dapat dianalogikan sebagai himpunan orangorang mukmin sedangkan garis atau sisi yang menghubungkan titik-titik tersebut dianalogikan sebagai kesabaran. Adanya garis yang menghubungkan titik-titik tersebut adanya sifat kesabaran yaitu pada orang-orang mukmin tersebut. Jika orang-orang mukmin yang bersabar tersebut disatukan atau dikumpulkan maka mereka mampu menciptakan suatu kekuatan yang luar biasa sehingga mampu mengalahkan kekuatan orang kafir yang sepuluh kali lipat jumlahnya. Seperti yang tercantum dalam QS. al-Anfal ayat 65: 4 È⎦÷⎫tGs($ÏΒ (#θç7Î=øótƒ tβρçÉ9≈|¹ tβρçô³Ïã öΝä3ΖÏiΒ ⎯ä3tƒ βÎ) 4 ÉΑ$tFÉ)ø9$# ’n?tã š⎥⎫ÏΖÏΒ÷σßϑø9$# ÇÚÌhym ©É<¨Ζ9$# $pκš‰r'¯≈tƒ ∩∉∈∪ šχθßγs)øtƒ ω ×Πöθs% óΟßγ¯Ρr'Î/ (#ρãxx. š⎥⎪Ï%©!$# z⎯ÏiΒ $Zø9r& #( þθç7Î=øótƒ ×πs($ÏiΒ Νà6ΖÏiΒ ⎯ä3tƒ βÎ)uρ Artinya: Hai nabi, Kobarkanlah semangat para mukmin untuk berperang. jika ada dua puluh orang yang sabar diantaramu, niscaya mereka akan dapat mengalahkan dua ratus orang musuh. dan jika ada seratus orang yang sabar diantaramu, niscaya mereka akan dapat mengalahkan seribu dari pada orang kafir, disebabkan orang-orang kafir itu kaum yang tidak mengerti. (QS. al-Anfaal:65) Maksud dari orang-orang kafir yang tidak mengerti adalah mereka tidak mengerti bahwa perang itu haruslah untuk membela keyakinan dan mentaati perintah Allah. Mereka berperang hanya semata-mata mempertahankan tradisi Jahiliyah dan maksud-maksud duniawiyah lainnya. Para ahli matematika mulai mempelajari teori graf sejak diperkenalkan oleh Leonard Euler seorang matematikawan dari Swiss pada tahun 1736, saat dia mendiskusikan mungkin atau tidaknya melintasi semua jembatan Konisberg
17 3
(sebelah timur Prussia, Jerman) yang sekarang bernama Kaliningrad dengan hanya melewatinya satu kali. Di Kaliningrad terdapat sungai Pregal yang mengitari pulau Kneiphof, kemudian bercabang menjadi dua anak sungai. Ada tujuh jembatan yang menghubungkan daratan yang dibelah sungai tersebut. Permasalahannya adalah “apakah mungkin melintasi ketujuh jembatan tersebut masing-masing tepat satu kali dan kembali ke tempat semula?”. Eulerpun membuat model masalah tersebut dalam bentuk graf. Daratan dinyatakannya sebagai titik (vertex) dan jembatan dinyatakannya sebagai sisi (edge). Jawaban yang dinyatakannya adalah seseorang tidak mungkin melalui ketujuh jembatan tersebut masing-masing satu kali dan kembali ke tempat semula jika derajat setiap titik tidak seluruhnya genap yaitu banyaknya sisi pada setiap titik (Suryanto, 1986:2). Dalam kehidupan sehari-hari banyak permasalahan yang memerlukan pemecahan. Sering dengan bantuan matematika, permasalahan tersebut menjadi lebih mudah dipahami, lebih mudah dipecahkan, atau bahkan dapat ditunjukkan bahwa suatu persoalan tidak mempunyai penyelesaian. Untuk keperluan tersebut, perlu dicari pokok permasalahannya dan kemudian dibuat rumusan atau model matematikanya. Dengan menggunakan rumusan atau model teori graf yang tepat, suatu permasalahan menjadi lebih jelas, sehingga mudah menganalisanya. Permasalahan yang dirumuskan dengan teori graf dibuat sederhana, yaitu diambil aspek-aspek yang diperlukan dan dibuang aspek-aspek lainnya (Purwanto, 1998:1).
4 18
Salah satu permasalahan dalam teori graf adalah pewarnaan titik, sisi, dan permukaan pada suatu graf. Permasalahan pewarnaan pada graf muncul pada tahun 1852 ketika seorang mahasiswa di Inggris bernama Francis Guthrie menulis surat kepada saudaranya, yaitu Frederick Guthrie, untuk memberitahukan pendapatnya (pendapat Francis) bahwa cukup empat warna untuk mewarnai peta sedemikian sehingga setiap wilayah terhubung dari suatu negara mendapat satu warna, dan setiap dua wilayah yang bersekutu perbatasan mendapat warna yang berbeda. Francis minta kepada Frederick bukti matematis tentang kebenaran pendapatnya itu. Karena tidak dapat membuktikan kebenaran itu, maka Frederic menanyakan kepada dosennya, seorang ahli matematika pada abad itu yaitu de Morgan. Sejak saat itu telah banyak ahli matematika yang berusaha menyelidiki apakah pendapat Francis tadi benar. Baru pada tahun 1976 ada yang berhasil membuktikan bahwa pendapat Francis itu benar. Tetapi tidak setiap orang puas dengan bukti yang telah diperoleh itu, karena bukti itu sangat tergantung kepada bantuan komputer. Benar atau salahnya bukti itu tidak dapat diuji tanpa bantuan komputer (Suryanto, 1986:154). Suatu pewarnaan permukaan (face colouring) untuk graf bidang G adalah suatu penggunaan sebagian atau semua k warna untuk mewarnai semua permukaan di graf bidang G sehingga setiap ada dua permukaan dipisahkan oleh sebuah sisi diberi warna yang berbeda. Jika graf bidang G mempunyai pewarnaan permukaan k , maka dikatakan permukaan di graf bidang G diwarnai dengan k warna. Sedangkan bilangan kromatik didefinisikan sebagai banyaknya warna terkecil yang diberikan pada permukaan di graf bidang G sedemikian hingga
19 5
untuk dua permukaan dipisahkan oleh sebuah sisi diberi warna yang berbeda (Bondy, 1982:158). Pewarnaan permukaan dapat juga diberikan kepada bangun ruang, seperti limas dan prisma. Limas adalah suatu bangun ruang yang dibatasi oleh sebuah segitiga atau segibanyak sebagai alas dan beberapa buah bidang berbentuk segitiga sebagai bidang tegak yang bertemu pada satu titik puncak. Sedangkan prisma adalah suatu bangun ruang yang dibatasi oleh dua bidang berhadapan yang sama dan sebangun atau kongruen dan sejajar, serta bidang-bidang lain yang berpotongan menurut rusuk-rusuk yang sejajar. Ada beberapa pewarnaan dalam suatu graf, yaitu pewarnaan titik, pewarnaan sisi, dan pewarnaan permukaan. Dalam penulisan skripsi ini penulis akan mengambil salah satu topik dari pewarnaan-pewarnaan pada graf tersebut yaitu pewarnaan permukaan. Pewarnaan permukaan adalah salah satu masalah mendasar pada graf, sehingga tidak ada dua permukaan yang dipisahkan oleh sebuah sisi mempunyai warna sama. Pada pewarnaan ini akan ditentukan berapa minimal angka yang dapat digunakan dalam mewarnai permukaan suatu graf (bilangan kromatik). Permukaan yang akan diwarna adalah limas, prisma, dan gabungan limas dan prisma.
1.2 Rumusan Masalah Berdasarkan latar belakang di atas, maka rumusan masalah dalam penulisan skripsi ini adalah bagaimana face colouring pada limas, prisma, dan
20 6
gabungan limas dan prisma serta bagaimana menentukan bilangan kromatiknya dan membuktikannya? 1.3 Tujuan Penelitian Berdasarkan rumusan masalah tersebut maka, tujuan penulisan skripsi ini adalah mengetahui bagaimana face colouring pada limas, prisma, dan gabungan limas dan prisma, serta mengetahui bagaimana menentukan bilangan kromatiknya dan membuktikannya. 1.4 Batasan Masalah Agar pembahasan dalam skripsi ini tidak meluas maka penulis membatasi objek kajian pada limas segidan prisma segi- (
), dimana 3
, prisma segi-
, dan gabungan limas segi-
6.
1.5 Manfaat Penelitian Adapun manfaat dari penulisan skripsi ini adalah: 1.
Bagi penulis, sebagai sarana dan latihan untuk menambah pemahaman dan penguasaan tentang materi yang dibahas dalam penulisan skripsi ini.
2.
Bagi pembaca, sebagai tambahan pengetahuan pada bidang Matematika khususnya teori graf mengenai cara menentukan bilangan kromatik face colouring pada limas, prisma, dan gabungan limas dan prisma.
3.
Bagi lembaga UIN MMI Malang, untuk bahan kepustakaan yang dijadikan sarana pengembangan wawasan keilmuan khususnya di jurusan Matematika untuk mata kuliah Teori Graf.
21 7
1.6 Metode Penelitian Dalam penyusunan skripsi ini, penulis menggunakan penelitian perpustakaan, yaitu penelitian yang dilakukan dengan mengumpulkan data-data dan informasi dengan bantuan bermacam-macam material yang ada di perpustakaan, seperti buku-buku, dokumen, jurnal, catatan, artikel, dan sebagainya yang berkaitan dengan pembahasan skripsi ini. Adapun langkahlangkah umum yang dilakukan penulis adalah: a. Merumuskan masalah yang akan dibahas. b. Mengumpulkan sumber-sumber dan informasi dengan cara membaca dan memahami literatur yang berkaitan dengan pewarnaan graf khususnya pewarnaan permukaan. c. Menganalisa permasalahan yang telah diperoleh dengan menjabarkan definisi dan teorema yang berkaitan. d. Merumuskan kesimpulan dari hasil analisis contoh yang telah diberikan. e. Langkah terakhir dari penelitian ini adalah menyusun laporan dari penelitian dalam bentuk tugas akhir. Analisis data merupakan bagian yang sangat penting dalam metode ilmiah, karena dengan analisislah data tersebut dapat diberi arti dan makna yang berguna dalam memecahkan masalah penelitian. Adapun analisis isi (content analysis) dengan menelaah struktur pewarnaan graf yaitu face colouring pada limas, prisma, dan gabungan limas dan prisma. Langkah-langkahnya yaitu: 1. Menentukan bilangan kromatik dari face colouring pada limas, prisma, dan gabungan limas dan prisma.
22 8
2. Mencari pola bilangan kromatik face colouring pada limas, prisma, dan gabungan limas dan prisma. 3. Pola yang diperoleh dinyatakan sebagai konjektur 4. Konjektur tersebut dinyatakan sebagai teorema dan dibuktikan. 1.7 Sistematika Pembahasan Agar penulisan skripsi ini lebih terarah, mudah ditelaah dan dipahami, maka digunakan sistematika penulisan skripsi ini yang terdiri dari empat bab. Masing-masing bab dibagi ke dalam beberapa subbab dengan rumusan sebagai berikut: BAB I
PENDAHULUAN Pendahuluan meliputi: latar belakang, rumusan masalah, tujuan penelitian, batasan masalah, manfaat penelitian, metode penelitian, dan sistematika pembahasan.
BAB II
TINJAUAN PUSTAKA Bagian ini terdiri dari konsep-konsep atau teori-teori yang mendukung bagian pembahasan. Konsep-konsep tersebut antara lain membahas tentang pengertian graf, derajat suatu titik, graf terhubung, graf dengan nama tertentu, macam-macam bangun ruang, pewarnaan pada graf, dan teori graf dalam al-Qur’an.
BAB III
PEMBAHASAN Pembahasan berisi tentang bagaimana menentukan bilangan kromatik face colouring pada limas, prisma, dan gabungan limas dan prisma.
23 9
BAB IV
PENUTUP Pada bab ini akan berisi tentang kesimpulan dan saran.
24
BAB II KAJIAN PUSTAKA
2.1 Konsep Graf dalam Islam Graf merupakan himpunan titik-titik dan sisi-sisi. Titik-titik dalam suatu graf dapat diasumsikan menurut keperluan dalam menyelesaikan suatu benda dan dihubungkan dengan suatu sisi, maka hal ini memiliki artian bahwa dua benda tersebut mempunyai suatu hubungan tertentu. Jika dua titik dalam suatu graf diasumsikan sebagai kejadian dan dihubungkan dengan suatu sisi, maka dapat diambil suatu pengertian bahwa ada dua kejadian yang mempunyai hubungan. Dalam teori Islam elemen-elemen yang dimaksud meliputi pencipta (Allah), manusia, dan alam, sedangkan sisi atau garis yang menghubungkan elemenelemen tersebut adalah bagaimana hubungan antara Allah dengan manusia, Allah dengan alam, dan manusia dengan alam. Sehingga dengan demikian, hal ini menunjukkan adanya suatu hubungan atau keterkaitan antara titik yang satu dengan titik yang lain. Graf tiga hubungan tersebut digambarkan sebagai berikut: Keterangan: = makhluk (ciptaan Allah) = eksistensi Tuhan = pemanfaatan alam
Allah
Manusia Alam Gambar 2.1.1 Representasi Graf Hubungan antara Allah, Manusia, dan Alam Sisi
yang mengilustrasikan hubungan antara Allah dan manusia
menggambarkan bahwa Allah kedudukannya sebagai sang Khalik dan manusia sebagai makhluk yang diciptakan-Nya. Manusia diciptakan Allah dengan dua 10
25 11
tujuan yaitu sebagai khalifah Allah dan sebagai hamba Allah. Manusia sebagai khalifah Allah artinya manusia sebagai wakil-Nya yang memakmurkan bumi. Seperti yang tertulis dalam al-Qur’an surat al-Baqarah ayat 30 yaitu:
߉šøム⎯tΒ $pκÏù ã≅yèøgrBr& (#þθä9$s% ( Zπx‹Î=yz ÇÚö‘F{$# ’Îû ×≅Ïã%y` ’ÎoΤÎ) Ïπs3Íׯ≈n=yϑù=Ï9 š•/u‘ tΑ$s% ŒÎ)uρ Ÿω $tΒ ãΝn=ôãr& þ’ÎoΤÎ) tΑ$s% ( y7s9 â¨Ïd‰s)çΡuρ x8ωôϑpt¿2 ßxÎm7|¡çΡ ß⎯øtwΥuρ u™!$tΒÏe$!$# à7Ïó¡o„uρ $pκÏù ∩⊂⊃∪ tβθßϑn=÷ès? Artinya:
“Ingatlah ketika Tuhanmu berfirman kepada para malaikat: "Sesungguhnya Aku hendak menjadikan seorang khalifah di muka bumi." Mereka berkata: "Mengapa Engkau hendak menjadikan (khalifah) di bumi itu orang yang akan membuat kerusakan padanya dan menumpahkan darah, padahal kami senantiasa bertasbih dengan memuji Engkau dan mensucikan Engkau?" Tuhan berfirman: "Sesungguhnya Aku mengetahui apa yang tidak kamu ketahui." (QS. al-Baqarah : 30).
Manusia sebagai hamba Allah artinya manusia harus mengabdi dan tunduk kepada aturan-aturan yang diberikan oleh Allah kepada manusia. Bahwasanya manusia diciptakan di dunia ini hanya untuk mengabdi (menghambakan diri) kepada Allah SWT. Seperti dalam firmanNya dalam al-Qur’an surat adzDzariyaat ayat 56, yaitu:
∩∈∉∪ Èβρ߉ç7÷èu‹Ï9 ωÎ) }§ΡM}$#uρ £⎯Ågø:$# àMø)n=yz $tΒuρ Artinya : “Dan Aku tidak menciptakan jin dan manusia melainkan supaya mereka mengabdi kepada-Ku”.(QS. adz-Dzariyaat: 56). Yang dimaksud dengan “menciptakan mereka untuk beribadah” adalah menciptakan mereka memiliki potensi untuk beribadah yaitu menganugerahkan mereka kebebasan memilih, akal, dan kemampuan (Shihab, 2003:358).
26 12 12
Sisi
mengilustrasikan hubungan antara Allah dan alam. Tujuan utama
penciptaan alam semesta menurut hadis qudsi adalah untuk mengetahui adanya Allah. Artinya Allah tidak mungkin diketahui tanpa melalui ciptaan-Nya. Menurut al-Qur’an, alam semesta dan berbagai fenomena yang ada, adalah sebuah tanda, eksistensi, dan kebesaran penciptaNya. Alam ibarat sebuah buku, menjelaskan tentang penciptanya (Allah) (Masruri, 2007:44). Sisi
mengilustrasikan suatu hubungan antara manusia dan alam.
Hubungan manusia dan alam bertujuan untuk memanfaatkan alam, memakmurkan bumi, dan menyelenggarakan kehidupan pada umumnya. Dalam al-Quran surat Fushshilat ayat 10 disebutkan :
[™!#uθy™ 5Θ$−ƒr& Ïπyèt/ö‘r& þ’Îû $pκsE≡uθø%r& !$pκÏù u‘£‰s%uρ $pκÏù x8t≈t/uρ $yγÏ%öθsù ⎯ÏΒ z©Å›≡uρu‘ $pκÏù Ÿ≅yèy_uρ ∩⊇⊃∪ t⎦,Î#Í←!$¡¡=Ïj9 Artinya: “Dan Dia menciptakan di bumi itu gunung-gunung yang kokoh di atasnya. Dia memberkahinya dan dia menentukan padanya kadar makanan-makanan (penghuni)nya dalam empat masa. (Penjelasan itu sebagai jawaban) bagi orang-orang yang bertanya.” (QS. Fushshilat : 10). 2.2 Definisi Graf Definisi 1 Graf
adalah pasangan himpunan
,
dengan
adalah himpunan tidak
kosong dan berhingga dari obyek-obyek yang disebut sebagai titik dan
adalah
himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di yang disebut sebagai sisi. Himpunan titik di himpunan sisi dinotasikan dengan order dari
dinotasikan dengan
. Sedangkan banyaknya unsur di
dan dilambangkan dengan
dan banyaknya unsur di
dan disebut disebut
27 13
ukuran dari graf
dan dilambangkan dengan
, maka order dan ukuran dari
. Jika graf yang dibicarakan hanya tersebut cukup ditulis dengan
dan
(Chartrand dan Lesniak, 1986:4). Suatu graf tidak boleh mempunyai sisi rangkap dan loop. Sisi rangkap dari suatu graf adalah jika dua titik yang dihubungkan oleh lebih dari satu sisi. Sedangkan yang disebut dengan loop adalah suatu sisi yang menghubungkan suatu titik dengan dirinya sendiri. Graf yang mempunyai sisi rangkap dan loop disebut dengan multigraf. , , ,
Sebagai contoh, misal ,
,
,
,
,
,
gambar 2.2.1. Pada gambar 2.2.1, dan sisi ganda sedangkan dan memuat sisi ganda yaitu
,
,
, ,
,
,
,
,
,
dan
, digambarkan pada
merupakan graf karena tidak memuat loop
merupakan multigraf karena memuat loop yaitu dan
.
Contoh 2.2.1
:
:
a. Graf
b. Multigraf
Gambar 2.2.1 Graf dan Multigraf Definisi 2 Sisi
,
dikatakan menghubungkan titik
adalah sisi di graf , maka
dan
dan
. Jika
disebut terhubung langsung (adjacent),
,
dan
28 14
serta
dan
disebut terkait langsung (incident). Untuk selanjutnya, sisi
,
(Chartrand dan Lesniak, 1986:4).
akan ditulis Definisi 3 Graf
disebut subgraf dari
jika himpunan titik di
dan himpunan sisi-sisi di
himpunan titik-titik di sisi di . Dapat ditulis
adalah subset dari
adalah subset dari himpunan
dan
. Jika
adalah subgraf ,
(Chartrand dan Lesniak, 1986:8).
maka dapat ditulis Contoh 2.2.
:
:
Gambar 2.2.2 Graf dan Subgraf , sedangkan karena itu
,
,
,
,
dan ,
,
,
adalah subgraf dari
dan
,
, ,
atau dapat ditulis seperti
,
,
,
,
, . Oleh
.
2.3 Derajat Suatu Titik Definisi 4 Derajat suatu titik
pada sebuah graf
, ditulis dengan deg
, adalah
jumlah sisi yang incident pada . Dengan kata lain, jumlah sisi yang memuat sebagai titik ujung. Titik deg
dikatakan genap atau ganjil tergantung dari jumlah
genap atau ganjil (Chartrand dan Lesniak, 1986:8).
15 29
Derajat minimum dan derajat maksimum titik-titik di dan ∆
dinyatakan dengan
berturut-turut
(Purwanto, 1998:7).
Contoh 2.3.1 :
Gambar 2.3.1 Derajat suatu titik pada graf 2, deg
deg
2, deg
adalah , yaitu sisi
karena banyaknya sisi dari graf dan
sisi
dari graf
,
dan
dan
, sedangkan deg
dan
2,
adalah , yaitu yang
, sedangkan deg
yang terkait langsung dengan
, sedangkan deg
yang terkait langsung dengan
yang terkait
2, karena banyaknya sisi dari graf
adalah , yaitu sisi
3, karena banyaknya sisi dari graf ,
1.
yang terkait langsung dengan
, sedangkan deg
terkait langsung dengan
3, yaitu sisi
3, dan deg
2, karena banyaknya sisi dari graf
Pada contoh 2.3.1, deg langsung dengan
2, deg
adalah
1, karena banyaknya sisi
hanya 1, yaitu sisi
.
Graf yang semua titiknya berderajat sama disebut graf beraturan (regular graph). Suatu graf dikatakan beraturan- (r-regular) jika setiap titiknya berderajat . Gambar 2.3.2 merupakan graf beraturan- dan graf beraturan- .
30 16
Contoh 2.3.2
b. Graf beraturana. Graf beraturanGambar 2.3.2 Graf Beraturan Gambar 2.3.2.a merupakan graf beraturanberderajat
karena masing-masing titiknya
sedangkan Gambar 2.3.2 b merupakan graf beraturan
karena
masing-masing titiknya berderajat . Dalam Islam titik-titik pada graf beraturan diibaratkan sebagai orangorang yang beriman yang berperang di jalan Allah. Mereka membentuk suatu formasi / barisan yang beraturan yang seakan-akan mereka seperti suatu bangunan yang tersusun kokoh. Misalkan graf beraturan
dengan 11 titik adalah gambaran orang-orang
beriman yang berperang di jalan Allah, seperti yang digambarkan sebagai berikut: Keterangan: , ,
,…,
dan dan dan dan dan , , , , , , , ,
= panglima atau pemimpin perang = tentara perang = iman = pasukan perang barisan pertama = pasukan perang barisan kedua = pasukan perang barisan ketiga = pasukan perang barisan keempat = pasukan perang barisan kelima = pasukan perang sayap kiri = pasukan perang sayap kanan
Gambar 2.3.3 Ilustrasi Graf dari Suatu Barisan atau Formasi Orang-orang mukmin yang berperang
17 31
Dari Gambar 2.3.5 terlihat bahwa ada suatu graf yang terdiri dari 11 titik dengan masing-masing titik berderajat , ,
,
,
,
,
,
,
, , dan
(beraturan
. Titik
). Titik-titiknya adalah
mengilustrasikan sebagai panglima
perang yang memimpin pasukannya. Titik
,
,
,
,
,
,
,
, , dan
mempresentasikan tentara dari pasukan perang tersebut. Titik-titik tersebut saling terhubung karena adanya rasa iman pada pasukan perang tersebut. Barisan tentaratentara itu diatur dengan sangat rapi dan dipimpin oleh seorang panglima yang sangat tangguh. Formasi atau barisan yang beraturan seakan-akan seperti bangunan yang tersusun kokoh dan mampu mengalahkan musuh. Seperti yang tertulis dalam al-Qur’an surat ash-Shaff ayat
yaitu:
∩⊆∪ ÒÉθß¹ö¨Β Ö⎯≈uŠ÷Ψç/ Οßγ¯Ρr(x. $y|¹ ⎯Ï&Î#‹Î6y™ ’Îû šχθè=ÏG≈s)ムš⎥⎪Ï%©!$# =Ïtä† ©!$# ¨βÎ) Artinya: “Sesungguhnya Allah menyukai orang-orang yang berperang di jalanNya dalam barisan yang teratur seakan-akan mereka seperti suatu bangunan yang tersusun kokoh.” (QS. ash-Shaff : 4) Kata shaffan atau barisan adalah sekelompok dari sekian banyak anggotanya yang sejenis dan kompak serta berada dalam satu wadah yang kukuh lagi teratur. Kata “marshush” berarti berdempet dan tersusun dengan rapi. Yang dimaksud ayat tersebut adalah kekompakan anggota barisan, kedisiplinan mereka yang tinggi, serta kekuatan mental mereka menghadapi ancaman dan tantangan (Shihab, 2003: 191). Teorema 1 Jika ∑
adalah
suatu
graf
dengan
2 (Chartrand dan Lesniak, 1986:7).
,
,…,
maka
18 32
Bukti: Setiap sisi adalah terkait langsung dengan
titik, jika setiap derajat titik
dijumlahkan, maka setiap sisi dihitung dua kali. Akibat 1: Pada sebarang graf, jumlah derajat titik ganjil adalah genap. Bukti: Misalkan graf titik ganjil pada
dengan ukuran . Maka ambil
serta
yang memuat himpunan
yang memuat himpunan titik genap di . Dari teorema
1 maka diperoleh: 2
dengan demikian karena ∑
genap, maka ∑
juga genap.
Sehingga | | adalah genap. 2.4 Graf Terhubung Definisi 5 Sebuah jalan (walk) kosong).
,
:
,
,
di graf ,
,…,
,
adalah barisan berhingga (tak yang berselang-seling antara titik
dan sisi, yang dimulai dari titik dan diakhiri dengan titik sedemikian hingga untuk 0
. Dengan
adalah sisi di .
disebut titik awal, interval, dan
disebut titik akhir,
menyatakan panjang dari
,
,…,
disebut titik
(Chartrand dan Lesniak, 1986:26).
Definisi 6 Jalan
yang semua sisinya berbeda disebut trail
dan Lesniak, 1986:26).
(Chartrand
33 19
Definisi 7 Jalan
yang semua titiknya berbeda disebut lintasan (path)
.
Dengan demikian, semua lintasan adalah trail (Chartrand dan Lesniak, 1986:26). Contoh 2.4.1
:
Gambar 2.4.1 Jalan pada Graf Dari graf pada Gambar 2..4.1 trail, sedangkan
,
,
,
,
,
,
,
,
,
,
,
,
disebut sebagai
,
disebut sebagai lintasan.
,
Definisi 8 Sebuah trail tertutup (closed trail) yang tak trivial pada graf (Chartrand dan Lesniak, 1986:28).
sirkuit
Dari ,
,
disebut
,
graf
,
,
,
pada ,
,
Gambar
,
,
,
,
2.4.1
contoh
dari
sirkuit
adalah
.
Definisi 9 ,
Sirkuit 1
,…
,
3
dengan
adalah titik-titik berbeda
disebut sikel (cycle) (Chartrand dan Lesniak, 1986:28). Dari ,
,
,
graf ,
,
,
pada ,
,
Gambar
2.4.1
contoh
dari
sikel
adalah
.
Definisi 10 Misalkan
dan
titik berbeda pada graf
. Maka titik
dikatakan terhubung (connected), jika terdapat lintasan
di
dan
dapat
. Sedangkan
20 34
suatu graf
dapat dikatakan terhubung, jika untuk setiap titik
dan
di
terhubung (Chartrand dan Lesniak, 1986:28). Contoh 2.4.2
:
:
Gambar 2.4.2 Graf Terhubung dan Graf Tak Terhubung Pada Gambar 2.4.2,
adalah graf terhubung karena setiap titiknya
terhubung, yaitu terdapat lintasan dari setiap titik ke tiap titik yang lain, sedangkan
adalah graf tak terhubung karena terdapat titik yang tidak
terhubung dengan titik yang lain, yaitu dan
,
, dan
tidak terhubung dengan
.
2.5 Graf dengan Nama Tertentu 2.5.1 Graf Komplit Definisi 11 Graf komplit (complete graph) adalah graf dengan setiap pasang titik yang berbeda dihubungkan oleh satu sisi. Graf komplit dengan dengan
(Purwanto, 1998:21).
titik dinyatakan
21 35
Contoh 2.5.1 ,
Graf
,
dan
.
Gambar 2.5.1 Graf Komplit 2.5.2 Graf Bipartisi Definisi 12 Graf bipartisi (bipartite graph) adalah graf yang himpunan titiknya dapat dipisahkan menjadi dua himpunan tak kosong
dan
sisi di graf tersebut menghubungkan satu titik di
sehingga masing-masing
dan satu titik di ,
dan
disebut himpunan partisi (Purwanto, 1998:21). Contoh 2.5.2 adalah graf bipartisi dengan himpunan partisi , partisi
:
,
,
,
,
,
demikian juga ,
dan
,
,
,
dan
adalah graf bipartisi dengan himpunan ,
,
,
.
:
Gambar 2.5.2 Graf Bipartisi
22 36
2.5.3 Graf Bipartisi Komplit Definisi 13 Graf bipartisi komplit (complete bipartite graph) adalah graf bipartisi dengan himpunan bipartisi
dan
sehingga masing-masing titik di
dihubungkan dengan masing-masing titik di dan | |
oleh tepat satu sisi. Jika | |
, maka graf bipartisi tersebut dinyatakan dengan
,
(Purwanto,
1998:22). Contoh 2.5.3 Graf
,
,
,
, dan
,
,
.
,
,
Gambar 2.5.3 Graf Bipartisi Komplit 2.5.4 Graf Sikel Definisi 14 Graf sikel adalah graf yang terdiri dari satu sikel (Purwanto, 1998:22). Graf sikel dinotasikan dengan
.
Contoh 2.5.4
Gambar 2.5.4 Graf Sikel
37 23
2.5.5 Graf Lintasan Graf yang terdiri dari satu lintasan disebut graf lintasan (Purwanto, 1998:22). Graf lintasan dengan
titik dinotasikan dengan
, dengan
bilangan
asli. Contoh 2.5.5 : : : Gambar 2.5.5 Graf Lintasan 2.5.6 Graf Kubus Definisi 15 Graf kubus (cube graph) adalah graf sederhana yang himpunan titiknya berupa himpunan tupel- (binary -tupel) ( , ,
,…,
), yaitu
adalah
atau
1,2,3, … , , dan dua titik terhubung langsung jika dan hanya jika dua tupel
yang bersesuaian berbeda tepat di satu tempat. Graf kubus yang diperoleh dinyatakan dengan
(Purwanto, 1998:23).
24 38
Contoh 2.5.6 Berikut ini adalah contoh graf
0,1
0
,
, dan
1,1
.
(0,0,1 )
(0,1,1 )
(1,0,1 )
(1,1,1 )
(0,1,0 ) 0,0
1
1,0
(0,0,0 )
(1,1,0 ) (1,0,0 )
Gambar 2.5.6 Graf Kubus 2.5.7 Hutan (forest) Definisi 16 Hutan (forest) adalah graf yang tidak memuat sikel. Hutan yang terhubung disebut pohon (tree) (Purwanto, 1998:23). Contoh 2.5.7
Gambar 2.5.7 Hutan (forest) dan Pohon (tree) Pada Gambar 2.5.7, sikel sedangkan
merupakan hutan karena pada
tidak memuat
merupakan pohon karena memuat hutan yang terhubung.
25 39
2.6 Macam-macam Bangun Ruang 2.6.1 Prisma Prisma adalah suatu bangun ruang yang dibatasi oleh dua bidang berhadapan yang sama, sebangun atau kongruen dan sejajar, serta bidang-bidang lain yang berpotongan menurut rusuk-rusuk yang sejajar (www.crayonpedia.org). Prisma diberi nama berdasarkan bentuk segi- pada bidang alas atau bidang atas. Contoh: prisma segiempat, karena bidang alas dan atas berbentuk segiempat. Rusuk-rusuk pada prisma tegak lurus terhadap bidang alas maupun bidang atas, sehingga disebut dengan prisma tegak. Bidang-bidang tegak berbentuk persegi panjang. Contoh 2.6.1 Prisma Segitiga
Gambar 2.6.1 Prisma Segitiga Pada Gambar 2.6.1 diperoleh, bidang bidang
merupakan bidang alas dan
merupakan bidang atas, dan kedua bidang tersebut berbentuk
segitiga. Bidang-bidang tegaknya adalah bidang tersebut berbentuk persegi panjang.
,
, dan
, dan ketiga
26 40
Prisma segitiga
dengan
titik yaitu titik
, , , , , dan
,
dapat mengilustrasikan rukun iman yang berjumlah , yaitu iman kepada Allah, iman kepada para malaikat, iman kepada kitab-kitab Allah, iman kepada para rasul, iman kepada hari akhir, dan iman kepada qada’ dan qadar (takdir). Keterangan: = iman kepada Allah = iman kepada para malaikat = iman kepada kitab-kitab Allah = iman kepada para rasul = iman kepada hari akhir = iman kepada qada’ dan qadar Gambar 2.6.2 Ilustrasi Rukun Iman Iman kepada Allah artinya merealisasikan pengesaan Allah SWT sehingga tidak menggantungkan harapan kepada selain Allah, tidak takut kepada yang lain, dan tidak menyembah kepada yang lain (Muhammad, 2003:34). Iman kepada malaikat artinya mengimani wujud mereka, mengimanai mereka yang dikenali nama-namanya, mengimani sifat-sifat mereka yang dikenali, dan mengimani tugas-tugas yang diperintahkan Allah kepada mereka (Muhammad, 2002:36-37). Iman kepada kitab-kitab Allah artinya mengimani bahwa benar-benar diturunkan dari Allah, mengimani kitab-kitab yang sudah dikenali namanya (Zabur, Taurat, Injil, dan al-Qur’an), membenarkan seluruh beritanya yang benar, dan mengerjakan seluruh hukum yang belum dinasakh (dihapus) serta rela da pasrah pada hukum itu (Muhammad, 2003:42). Iman kepada para rasul artinya mengimani bahwa risalah mereka benarbenar dari Allah, mengimani para nabi yang sudah dikenali nama-namanya,
27 41
membenarkan berita-berita mereka yang benar, dan mengamalkan syariat dari mereka yang diutus kepada manusia, yaitu nabi terakhir Muhammad SAW yang diutus Allah kepada seluruh manusia (Muhammad, 2003:49-51). Iman kepada hari akhir artinya mengimani ba’ats (kebangkitan) yaitu menghidupkan kembali orang-orang yang sudah mati ketika tiupan sangkakala yang kedua kali, mengimani hisab (perhitungan) dan jaza’ (pembalasan) dengan meyakini bahwa seluruh perbuatan manusia akan dihisab dan dibalas, dan mengimani surga dan neraka sebagai tempat manusia yang abadi (Muhammad, 2003:54). Iman kepada qada’ dan qadar artinya mengimani bahwa Allah mengetahui segala sesuatu secara global maupun terperinci, azali dan abadi, baik yang berkaitan dengan perbuatanNya maupun perbuatan para hambaNya, mengimani bahwa Allah telah menulis hal itu di “Lauh Mahfuzh”, mengimani bahwa seluruh yang ada tidak akan ada kecuali dengan kehendak Allah, dan mengimani bahwa seluruhnya yang ada, zatnya, sifatnya, dan geraknya diciptakan oleh Allah (Muhammad, 2003:77). 2.6.2
Limas Limas adalah bangun ruang yang dibatasi oleh sebuah segitiga ataupun
segibanyak sebagai alas dan beberapa buah bidang berbentuk segitiga sebagai bidang tegak yang bertemu pada satu titik puncak (www.crayonpedia.org). Limas diberi nama berdasarkan bentuk segi- pada bidang alas.
28 42
Contoh 2.6.2 Limas Segiempat .
Gambar 2.6.3 Limas Segiempat . Pada Gambar 2.16 diperoleh, bidang segiempat dan titik ,
,
, dan
sebagai bidang alas berbentuk
sebagai titik puncak. Bidang-bidang tegaknya adalah , dan keempat bidang tersebut berbentuk segitiga.
Limas segiempat .
dengan
titik yaitu titik , , , , dan
mengilustrasikan rukun Islam yang berjumlah
dapat
, yaitu syahadat, shalat, zakat,
puasa, dan haji. Keterangan: = Syahadat = Shalat = Zakat = Puasa = Haji
Gambar 2.6.4 Ilustrasi Rukun Islam Islam didirikan atas lima dasar, sebagaimana yang tersebut dalam sebuah hadits yang diriwayatkan oleh Ibnu Umar: “Islam didirikan atas lima dasar, yaitu: (1) Bersaksi bahwa tiada Tuhan yang berhak disembah selain Allah, dan Muhammad adalah hamba dan Rasul-Nya; (2)
29 43
mendirikan shalat; (3) mengeluarkan zakat; (4) puasa ramadhan; dan (5) beribadah haji ”. (HR. Al-Bukhari dan Muslim). 2.6.3 Bola Bola adalah suatu bangun ruang yang dibatasi oleh sebuah sisi lengkung/ kulit bola (www.crayonpedia.org). 2.7 Pewarnaan pada Graf Ada tiga macam pewarnaan pada graf, yaitu pewarnaan titik, pewarnaan sisi, dan pewarnaan peta. 2.7.1 Pewarnaan Titik (Vertex Colouring) Definisi 17 Pewarnaan titik dari graf titik dari
adalah sebuah pemetaan warna-warna ke titik-
sedemikian hingga titik yang terhubung langsung mempunyai warna-
warna yang berbeda. Graf yang menggunakan
berwarna
jika terdapat sebuah pewarnaan dari
warna (Purwanto, 1998:73).
Dalam pewarnaan titik erat kaitannya dengan penentuan bilangan kromatik, yaitu masalah menentukan banyak warna minimum yang diperlukan untuk mewarnai titik-titik pada graf sehingga dua titik yang terhubung langsung mempunyai warna yang berbeda. Bilangan kromatik (chromatic number) dari graf , adalah bilangan
terkecil sehingga
, dinyatakan dengan
dapat diwarnai dengan
warna.
Biasanya warna-warna yang digunakan untuk mewarnai suatu graf dinyatakan dengan 1,2,3, … , . Jelas bahwa
|
|. Sedangkan cara yang mudah
30 44
untuk menentukan batas bawah dari komplit yang terbesar di
adalah dengan cara mencari graf bagian
(Purwanto, 1998:73).
Beberapa graf tertentu dapat langsung ditentukan bilangan kromatiknya. Graf kosong
1. Karena semua titik tidak terhubung, jadi
memiliki
untuk mewarnai semua titik cukup dibutuhkan satu warna saja. Graf lengkap sebab semua titik saling terhubung sehingga diperlukan
memiliki warna. Contoh 2.7.1
, karena |
Pada gambar 2.7.1 dapat dilihat bahwa untuk graf 3. Untuk
maka
semua titik pada
dan
4. Jadi,
, karena |
|
4, maka
|
4. Sedangkan 3 dan
saling terhubung langsung, akibatnya 3 dan
4. Untuk graf
3, Karena 3
,
warna cukup untuk mewarnainya seperti pada gambar 2.7.1. Karena graf , maka
memuat graf komplit
1
1
3, akibatnya
3. 1
2 3
3
2
4
3
Gambar 2.7.1 Pewarnaan Titik pada
2
3
2
,
3,
dan
31 45
2.7.2 Pewarnaan Sisi (Edge Colouring) Definisi 18 Suatu pewarnaan sisi- untuk graf atau semua
adalah suatu penggunaan sebagian
warna untuk mewarnai semua sisi di
sehingga setiap pasang sisi
yang mempunyai titik persekutuan diberi warna yang berbeda. Jika pewarnaan sisi- , maka dikatakan sisi-sisi di
mempunyai
diwarnai dengan
warna
(Purwanto, 1998:80). Indeks kromatik (chromatic index) dari graf adalah bilangan
terkecil sehingga sisi di
′
dinyatakan dengan
dapat diwarnai dengan
,
warna.
Biasanya warna-warna yang digunakan untuk mewarnai sisi-sisi suatu graf dinyatakan dengan 1,2,3, … , . Jelas bahwa maksimum di
adalah Δ
, maka
titik, misalkan
, jelas bahwa
′
′
′
| Δ
|, dan jika derajat titik
. Untuk graf sikel dengan
2 untuk
genap dan
′
3 untuk
ganjil (Purwanto, 1998:80). Contoh 2.7.2 3 2 2
1
1
2
1
1 3
3
2
3 4
3
Gambar 2.7.2 Pewarnaan Sisi
4 2
,
dan
1
32 46
Untuk graf Δ
3, dan
′
jelas bahwa
′
3 karena sisi-sisi di ′
seperti pada gambar 2.7.2. Akibatnya Untuk
,
′
3. Untuk
4 karena Δ
dapat diwarnai dengan
,
′
3 karena
dapat diwarnai dengan
warna
3. ′
4 dan
4 karena sisi-sisi di
warna seperti pada gambar 2.7.1. Akibatnya,
′
4. 2.7.3 Pewarnaan Permukaan (Face Colouring) Definisi 19 - face colouring 1,2,3, … ,
pada graf bidang
pada permukaan di
adalah pemberian
warna
; pewarnaannya tepat jika tidak ada dua
permukaan dipisahkan oleh sebuah sisi yang berwarna sama. permukaan jika memenuhi pewarnaan
dapat diwarna -
permukaan, dan bilangan
sehingga permukaan di
dapat diwarnai dengan
kromatik permukaan pada
, dilambangkan dengan
terkecil
warna adalah bilangan ′′
atau
(Bondy,
1982:158). Contoh 2.7.3
4 3
2 1
Gambar 2.7.3 Face Colouring Graf
′′
4
47 33
Pewarnaan pada suatu graf jika dianalogikan dalam Islam merupakan suatu warna atau identitas oleh setiap orang. Manusia terbagi menjadi
identitas,
yaitu mukmin, munafik, dan kafir. Misalkan orang mukmin, orang munafik, dan orang kafir digambarkan dalam suatu graf. Orang mukmin digambarkan dengan suatu titik dengan warna hijau, orang munafik dengan warna kuning, dan orang kafir dengan warna hitam. Misalkan graf pada gambar 2.7.4 mempresentasikan ke- macam identitas tersebut. mukmin
Kafir
munafik
Gambar 2.7.4 Representasi Graf dari Pewarnaan untuk suatu Identitas Manusia Seorang manusia beridentitas mukmin jika dia mempunyai ciri-ciri yaitu apabila disebut nama Allah gemetarlah hatinya, dan apabila dibacakan kepada dia ayat-ayatNya, bertambahlah imannya. Seperti yang terdapat dalam al-Qur’an surat al-Anfaal ayat 2:
…çμçG≈tƒ#u™ öΝÍκön=tã ôMu‹Î=è? #sŒÎ)uρ öΝåκæ5θè=è% ôMn=Å_uρ ª!$# tÏ.èŒ #sŒÎ) t⎦⎪Ï%©!$# šχθãΖÏΒ÷σßϑø9$# $yϑ¯ΡÎ) ∩⊄∪ tβθè=©.uθtGtƒ óΟÎγÎn/u‘ 4’n?tãuρ $YΖ≈yϑƒÎ) öΝåκøEyŠ#y— Artinya: : ”Sesungguhnya orang-orang yang beriman ialah mereka yang bila disebut nama Allah gemetarlah hati mereka, dan apabila dibacakan ayat-ayatNya bertambahlah iman mereka (karenanya), dan hanya kepada Tuhanlah mereka bertawakkal.” (Qs. al-Anfaal : 2)
48 34
Seorang manusia beridentitas munafik jika dia mempunyai ciri-ciri yaitu jika dia berbicara berbohong, jika dia berjanji dia ingkar, dan jika dipercaya dia berkhianat. Rasul SAW bersabda: ”Tanda-tanda orang munafik ada , apabila dia berkata dia bohong, apabila dia berjanji dia ingkar, dan apabila dia diamanahi dia berkhianat” (HR. Bukhari dan Muslim dari Abu Hurairah). Seorang manusia beridentitas kafir jika dia mempunyai ciri-ciri yaitu dia tidak melaksanakan syariat Allah. Dia tidak dapat memperhatikan dan memahami ayat-ayat al-Qur’an yang dia dengar dan tidak dapat mengambil pelajaran dari tanda-tanda kebesaran Allah. Seperti dalam firman Allah dalam al-Qur’an surat al-Baqarah ayat 6-7:
ª!$# zΝtFyz ∩∉∪ tβθãΖÏΒ÷σムŸω öΝèδö‘É‹Ζè? öΝs9 ÷Πr& öΝßγs?ö‘x‹Ρr&u™ óΟÎγøŠn=tæ í™!#uθy™ (#ρãxx. š⎥⎪Ï%©!$# ¨βÎ) ∩∠∪ ÒΟŠÏàtã ë>#x‹tã öΝßγs9uρ ( ×οuθ≈t±Ïî öΝÏδÌ≈|Áö/r& #’n?tãuρ ( öΝÎγÏèôϑy™ 4’n?tãuρ öΝÎγÎ/θè=è% 4’n?tã Artinya: ”Sesungguhnya orang-orang kafir, sama saja bagi mereka, kamu beri peringatan atau tidak kamu beri peringatan, mereka tidak juga akan beriman. Allah Telah mengunci-mati hati dan pendengaran mereka, dan penglihatan mereka ditutup, dan bagi mereka siksa yang amat berat.” (QS. al-Baqarah : 6-7)
49
BAB III PEMBAHASAN
Pada bab III akan dibahas mengenai pewarnaan permukaan (face colouring) pada limas, prisma, dan gabungan limas dan prisma. Gabungan limas dan prisma didefinisikan bahwa bidang alas limas berimpit dengan bidang atas prisma. 3.1 Pewarnaan Permukaan (face colouring) pada Limas Segi- (
)
Berikut ini adalah beberapa contoh pewarnaan permukaan pada bangun ruang limas. Langkah-langkahnya adalah sebagai berikut: 1. Menentukan Bilangan Kromatik dari Pewarnaan Permukaan pada , , ,
Limas Segi- , a. Limas Segitiga ( )
Gambar 3.1.1 Limas Segitiga . Pada bangun limas segitiga . alas yang berbentuk segitiga dan titik tegaknya adalah
,
, dan
diperoleh bidang
sebagai bidang
sebagai titik puncak. Bidang-bidang
, ketiga bidang tersebut berbentuk segitiga.
Pada bangun limas segitiga .
tersebut akan diwarna masing-masing
permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang 35
36 50
yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan adalah sebagai berikut:
permukaan (bidang) pada limas segitiga .
4
2 3
1 4
Gambar 3.1.2 Face Colouring pada Limas Segitiga . Pada Gambar 3.1.2 diperoleh pewarnaan permukaan pada limas segitiga .
warna
yaitu warna
untuk bidang tegak
untuk bidang tegak
, warna
, dan warna
untuk bidang tegak
untuk bidang alas
,
. Jadi, warna
minimal yang dibutuhkan (bilangan kromatik) untuk mewarnai permukaan limas segitiga .
adalah sebanyak .
b. Limas Segiempat ( )
Gambar 3.1.3 Limas Segiempat . Pada bangun limas segiempat
diperoleh bidang
.
bidang alas yang berbentuk segiempat dan titik bidang tegaknya adalah berbentuk segitiga.
,
,
dan
sebagai
sebagai titik puncak. Bidang, keempat bidang tersebut
51 37
Pada bangun limas segiempat
tersebut akan diwarna masing-
.
masing permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan adalah sebagai berikut:
permukaan (bidang) pada limas segiempat .
1
2
2
3
1 3 Gambar 3.1.4 Face Colouring pada Limas Segiempat .
Pada Gambar 3.1.4 diperoleh pewarnaan permukaan pada limas segiempat .
tegak
yaitu warna dan
untuk bidang tegak
, dan warna
dan
, warna
untuk bidang alas
untuk bidang
. Jadi, warna minimal
yang dibutuhkan (bilangan kromatik) untuk mewarnai permukaan limas segiempat .
adalah sebanyak .
c. Limas Segilima ( )
Gambar 3.1.5 Limas Segilima . diperoleh bidang
Pada bangun limas segilima . bidang alas yang berbentuk segilima dan titik bidang tegaknya adalah
,
,
,
dan
sebagai
sebagai titik puncak. Bidangberbentuk segitiga.
52 38
Pada bangun limas segilima
tersebut akan diwarna masing-
.
masing permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan adalah sebagai berikut:
permukaan (bidang) pada limas segiempat .
2 1 3
4
1 2 4
Gambar 3.1.6 Face Colouring pada Limas Segilima . Pada Gambar 3.1.6 diperoleh pewarnaan permukaan pada limas segilima .
tegak alas
yaitu warna dan
untuk bidang tegak
, warna
dan
untuk bidang tegak
, warna
untuk bidang
, dan warna
untuk bidang
. Jadi, warna minimal yang dibutuhkan (bilangan kromatik) untuk
mewarnai permukaan limas segitiga .
adalah sebanyak .
d. Limas Segienam ( )
Gambar 3.1.7 Limas Segienam .
39 53
Pada bangun limas segienam
diperoleh bidang
.
sebagai bidang alas yang berbentuk segienam dan titik Bidang-bidang tegaknya adalah
,
,
,
sebagai titik puncak. dan
,
, keenam
bidang tersebut berbentuk segitiga. Pada bangun limas segienam .
tersebut akan diwarna masing-
masing permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan adalah sebagai berikut:
permukaan (bidang) pada limas segienam .
1
2 1
2
1
3
2
3 Gambar 3.1.8 Face Colouring pada Limas Segienam . Pada Gambar 3.1.8 diperoleh pewarnaan permukaan pada limas segienam yaitu warna
.
bidang tegak
,
untuk bidang tegak dan
, dan warna
,
dan
, warna
untuk bidang alas
untuk . Jadi,
warna minimal yang dibutuhkan (bilangan kromatik) untuk mewarnai permukaan limas segienam .
adalah sebanyak .
2. Mencari Pola Bilangan Kromatik Pewarnaan Permukaan Limas Segi( ) Dari beberapa contoh pewarnaan permukaan pada bangun ruang limas segi- diperoleh bilangan kromatiknya yaitu
40 54
4 3
4 3 Dari data di atas terlihat pola yang dapat dinyatakan secara umum sebagai berikut: 4,untuk
ganjil ,
3, untuk
,
3
genap
3. Pola yang Diperoleh Dinyatakan sebagai Konjektur 4,untuk
ganjil ,
3, untuk
,
3
genap
Konjektur tersebut bersifat induktif dan belum diterima kebenarannya dalam matematika. 4. Konjektur Tersebut Dinyatakan sebagai Teorema dan Dibuktikan Teorema 3.1 Bilangan kromatik untuk pewarnaan permukaan (face colouring) pada limas segi- ( ) adalah 4,untuk
ganjil ,
3, untuk
genap
,
3
41 55
Bukti: Ganjil
a. Kasus I, untuk
Setiap limas segi(permukaan) yaitu diberi nama
dimana
ganjil mempunyai
bidang tegak dan
bidang alas. Misalkan bidang alas
dan bidang tegak diberi nama
Terlihat bahwa
1 bidang
1,2,3, … , .
,
dimana ganjil dan
tidak saling berbatasan
langsung (tidak berpotongan) maka dapat diberi warna sama. Demikian dimana
juga
genap tidak saling berbatasan langsung (tidak
berpotongan) maka dapat diberi warna sama. Pilih warna
untuk
dimana ganjil dan
. Karena
genap berbatasan langsung (berpotongan) dengan maka Karena
,
berbatasan langsung (berpotongan) dengan
, maka diberi warna
langsung (berpotongan) dengan maka
ganjil,
dimana genap tidak boleh diberi warna , maka diberi warna .
yang masing-masing berwarna dan
dimana
dimana
dan , maka
,
dan
tidak boleh diwarna
. Karena bidang alas ( ) berbatasan ,
1,2,3, …
yang berwarna 1,2, dan ,
tidak boleh diberi warna-warna tersebut, maka
diberi warna .
Jadi, warna minimal yang diperlukan untuk pewarnaan permukaan (face colouring) pada limas segi- , dimana terbukti
4, untuk
ganjil.
ganjil adalah sebanyak . Jadi,
56 42
b. Kasus II, untuk
Genap dimana
Setiap limas segi(permukaan) yaitu diberi nama
bidang tegak dan
genap mempunyai
bidang alas. Misalkan bidang alas
dan bidang tegak diberi nama
Terlihat bahwa
1 bidang
1,2,3, … , .
,
dimana ganjil tidak saling berbatasan langsung
(tidak berpotongan) maka dapat diberi warna sama. Demikian juga dimana genap tidak saling berbatasan langsung (tidak berpotongan) maka dapat diberi warna sama. Pilih warna
untuk
dimana ganjil. Karena
berbatasan langsung (berpotongan) dengan
dimana
dimana
genap
ganjil, maka
dimana genap tidak boleh diberi warna , maka diberi warna . Karena bidang alas ( ) berbatasan langsung (berpotongan) dengan 1,2,3, …
yang berwarna
tersebut, maka
dan , maka
,
tidak boleh diberi warna-warna
diberi warna . Jadi, warna minimal yang diperlukan
untuk pewarnaan permukaan (face colouring) pada limas segi- , dimana genap adalah sebanyak . Jadi, terbukti
3, untuk
genap.
3.2 Pewarnaan Permukaan (face colouring) pada Prisma Segi- (
)
Berikut ini adalah beberapa contoh pewarnaan permukaan pada bangun ruang prisma. Langkah-langkahnya adalah sebagai berikut: 1. Menentukan Bilangan Kromatik dari Pewarnaan Permukaan pada Prisma Segi- ,
, , ,
57 43
a. Prisma Segitiga
Gambar 3.2.1 Prisma Segitiga diperoleh bidang
Pada bangun prisma segitiga bidang alas dan
sebagai
sebagai bidang atas, kedua bidang tersebut berbentuk
segitiga. Bidang-bidang tegaknya adalah
, dan
,
, ketiga bidang
tersebut berbentuk persegi panjang. tersebut akan diwarna masing-
Pada bangun prisma segitiga
masing permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan adalah sebagai berikut:
permukaan (bidang) pada prisma segitiga
4 3
1 4
4 2
Gambar 3.2.2 Face colouring pada Prisma Segitiga Pada Gambar 3.2.2 diperoleh pewarnaan permukaan pada prisma segitiga yaitu warna , warna
untuk bidang tegak
untuk bidang tegak
, warna
, dan warna
untuk bidang tegak
untuk bidang alas
dan
58 44
bidang atas
. Jadi, warna minimal yang dibutuhkan (bilangan kromatik) untuk
mewarnai permukaan prisma segitiga
adalah sebanyak .
b. Prisma Segiempat
Gambar 3.2.3 Prisma Segiempat Pada bangun prisma segiempat
diperoleh bidang
sebagai bidang atas, kedua bidang tersebut
sebagai bidang alas dan
berbentuk segiempat. Bidang-bidang tegaknya adalah
,
,
dan
, keempat bidang tersebut berbentuk persegi panjang. tersebut akan diwarna masing-
Pada bangun prisma segiempat
masing permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan permukaan (bidang) pada prisma segiempat
adalah sebagai berikut:
3 1
2
3 2
1 3 Gambar 3.2.4 Face Colouring pada Prisma Segiempat
45 59
Pada Gambar 3.2.4 diperoleh pewarnaan permukaan pada prisma segiempat
yaitu warna
untuk bidang tegak bidang atas
untuk bidang tegak
dan
, dan warna
dan
, warna
untuk bidang alas
dan
. Jadi, warna minimal yang dibutuhkan (bilangan kromatik)
untuk mewarnai permukaan prisma segiempat
adalah sebanyak .
c. Prisma Segilima
Gambar 3.2.5 Prisma Segilima Pada bangun prisma segilima sebagai bidang alas dan
diperoleh bidang
sebagai bidang atas, kedua bidang tersebut
berbentuk segilima. Bidang-bidang tegaknya adalah , dan
,
,
,
, kelima bidang tersebut berbentuk persegi panjang.
Dari bangun prisma segilima
tersebut akan diwarna masing-
masing permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan permukaan (bidang) pada prisma segilima
adalah sebagai berikut:
46 60
2 4
1 4
2
3
1 4
Gambar 3.2.6 Face Colouring pada Prisma Segilima Pada Gambar 3.2.6 diperoleh pewarnaan permukaan pada prisma segilima yaitu warna dan
bidang tegak untuk bidang alas
untuk bidang tegak
dan
, warna 3 untuk bidang tegak dan bidang atas
, warna
untuk
,dan warna
. Jadi, warna minimal yang
dibutuhkan (bilangan kromatik) untuk mewarnai permukaan prisma segilima adalah sebanyak . d. Prisma Segienam
Gambar 3.2.7 Prisma Segienam Pada bangun prisma segienam sebagai bidang alas dan
diperoleh bidang
sebagai bidang atas, kedua bidang tersebut
47 61
berbentuk segienam. Bidang-bidang tegaknya adalah dan
,
,
,
,
, keenam bidang tersebut berbentuk persegi panjang. tersebut akan diwarna
Pada bangun prisma segienam
masing-masing permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. adalah
Pewarnaan permukaan (bidang) pada prisma segienam sebagai berikut:
1
2 3
1 3
2
2 1 3
Gambar 3.2.8 Face Colouring pada Prisma Segienam
Pada Gambar 3.2.8 diperoleh pewarnaan permukaan pada prisma segienam warna bidang alas
yaitu warna untuk bidang tegak dan bidang atas
untuk bidang tegak ,
dan
,
, dan warna
, dan untuk
. Jadi, warna minimal yang
dibutuhkan (bilangan kromatik) untuk mewarnai permukaan prisma segienam adalah sebanyak
.
48 62
2. Mencari Pola Bilangan Kromatik Pewarnaan Permukaan Prisma Segi(
) Dari beberapa contoh pewarnaan permukaan pada bangun ruang prisma
segi- diperoleh bilangan kromatiknya yaitu 4 3 4 3
Dari data di atas terlihat pola yang dapat dinyatakan secara umum sebagai berikut: 4,untuk
ganjil ,
3, untuk
,
3
genap
3. Pola yang Diperoleh Dinyatakan sebagai Konjektur 4,untuk
ganjil ,
3, untuk
,
3
genap
Konjektur tersebut bersifat induktif dan belum diterima kebenarannya dalam matematika. 4. Konjektur Tersebut Dinyatakan sebagai Teorema dan Dibuktikan Teorema 3.2 Bilangan kromatik untuk pewarnaan permukaan (face colouring) pada prisma segi- ( ) adalah
49 63
4,untuk
ganjil ,
3, untuk
,
3
genap
Bukti: a. Kasus I, untuk
Ganjil
Setiap prisma segi(permukaan) yaitu
dimana
bidang tegak,
bidang atas diberi nama tegaknya diberi nama
bidang alas dan
2 bidang
bidang atas. Misalkan
dan bidang alas diberi nama
, sedangkan bidang
1,2,3, … , .
,
Terlihat bahwa
ganjil mempunyai
dimana
ganjil dan
tidak saling berbatasan
langsung (tidak berpotongan) maka dapat diberi warna sama. Demikian juga dimana genap tidak saling berbatasan langsung (tidak berpotongan) maka dan
dapat diberi warna sama. Dan juga
tidak saling berbatasan langsung
(tidak berpotongan) maka dapat diberi warna sama. Pilih warna
untuk
dimana
ganjil dan
genap berbatasan langsung (berpotongan) dengan dimana ,
genap tidak boleh diberi warna
diberi warna
dan , maka
, maka diberi warna
dan
diberi warna
dan
tidak boleh diwarna
,
1,2,3, …
. Karena
yang masingdan , maka
. Karena bidang alas ( ) dan bidang atas
langsung (berpotongan) dengan maka
,
dimana
dimana ganjil, maka
berbatasan langsung (berpotongan) dengan
masing berwarna
. Karena
berbatasan
yang berwarna 1,2, dan
tidak boleh diberi warna-warna tersebut, maka
,
dan
. Jadi, warna minimal yang diperlukan untuk pewarnaan
50 64
permukaan (face colouring) pada prisma segi- , dimana sebanyak . Jadi, terbukti b. Kasus II, untuk
4, untuk
dimana
bidang tegak,
bidang atas diberi nama tegak diberi nama
ganjil.
genap
Setiap prisma segi(permukaan) yaitu
ganjil adalah
genap mempunyai
bidang alas, dan
2 bidang
bidang atas. Misalkan
dan bidang alas diberi nama
, sedangkan bidang
1,2,3, … , .
,
Terlihat bahwa b dimana
ganjil tidak saling berbatasan langsung
(tidak berpotongan) maka dapat diberi warna sama. Demikian juga
dimana
genap tidak saling berbatasan langsung (tidak berpotongan) maka dapat diberi warna sama. Dan juga
dan
tidak saling berbatasan langsung (tidak
berpotongan) maka dapat diberi warna sama. Pilih warna
untuk
dimana
berbatasan langsung (berpotongan) dengan
ganjil. Karena
dimana
dimana ganjil, maka
genap dimana
genap tidak boleh diberi warna , maka diberi warna . Karena bidang alas ( ) dan bidang atas 1,2,3, …
yang berwarna
warna tersebut, maka
berbatasan langsung (berpotongan) dengan dan , maka dan
dan
diberi warna
,
tidak boleh diberi warna. Jadi, warna minimal yang
diperlukan untuk pewarnaan permukaan (face colouring) pada prisma segi- , dimana
genap adalah sebanyak . Jadi, terbukti
3, untuk
genap.
65 51
3.3 Pewarnaan Permukaan (face coloring) pada Gabungan Limas Segi- dan Prisma SegiBerikut ini adalah beberapa contoh pewarnaan permukaan pada bangun ruang gabungan limas segi-
dan prisma segi- . Langkah-langkahnya adalah
sebagai berikut: 1. Menentukan Bilangan Kromatik dari Pewarnaan Permukaan pada Gabungan Limas Segi- Dan Prisma Segi- , a. Gabungan Limas Segitiga .
, , ,
dan Prisma Segitiga
Gambar 3.3.1 Limas Segitiga .
dan Prisma Segitiga
Kedua bangun ruang pada Gambar 3.3.1 akan digabung, yaitu bidang alas dari limas segitiga . segitiga
diimpitkan dengan bidang atas
dari prisma
. Gabungan kedua bangun ruang tersebut adalah sebagai berikut:
Gambar 3.3.2 Gabungan Limas Segitiga . Prisma Segitiga
dan
52 66
Pada Gambar 3.3.2 diperoleh suatu bangun ruang . puncak
, bidang alas , dan
, ,
dengan titik
yang berbentuk segitiga, 3 bidang tegak atas
yang berbentuk segitiga, dan 3 bidang tegak bawah
, dan
yang berbentuk persegi panjang.
Dari bangun ruang
tersebut akan diwarna masing-masing
.
permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan adalah sebagai berikut:
permukaan (bidang) pada bangun ruang .
3 2 4
1 2
1 3 4
Gambar 3.3.3 Face Colouring pada Bangun Ruang . Pada Gambar 3.3.3 diperoleh pewarnaan permukaan pada bangun ruang yaitu warna 1 untuk bidang tegak atas
.
, warna warna
untuk bidang tegak atas
untuk bidang tegak atas
untuk bidang alas
dan bidang tegak bawah
dan bidang tegak bawah
dan bidang tegak bawah
,
, dan warna
. Jadi, warna minimal yang dibutuhkan (bilangan kromatik)
untuk mewarnai permukaan bangun ruang .
adalah sebanyak .
67 53
b. Gabungan
Limas
Segiempat
.
Gambar 3.3.4 Limas Segiempat .
dan
Prisma
Segiempat
dan Prisma Segiempat
Kedua bangun ruang pada Gambar 3.3.4 akan digabung, yaitu bidang alas dari limas segiempat . prisma segiempat
diimpitkan dengan bidang atas
dari
. Gabungan kedua bangun ruang tersebut adalah
sebagai berikut:
B Gambar 3.3.5 Gabungan Limas Segiempat . Segiempat Pada Gambar 3.3.5 diperoleh suatu bangun ruang . titik puncak , bidang alas
dan Prisma dengan
yang berbentuk segiempat, 4 bidang tegak atas
54 68
,
dan
, ,
yang berbentuk segitiga, dan 4 bidang tegak bawah dan
,
yang berbentuk persegi panjang. tersebut akan diwarna masing-masing
Dari bangun ruang .
permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan adalah sebagai berikut:
permukaan (bidang) pada bangun ruang .
1
2
2
1 3
2
1
1
2 3 Gambar 3.3.6 Face Colouring pada Bangun Ruang . Pada Gambar 3.3.6 diperoleh pewarnaan permukaan pada bangun ruang .
yaitu warna 1 untuk bidang tegak atas
tegak bawah
dan
bidang tegak bawah
, warna dan
dan
untuk bidang tegak atas , dan warna
dan bidang dan
untuk bidang alas
dan . Jadi,
warna minimal yang dibutuhkan (bilangan kromatik) untuk mewarnai permukaan bangun ruang .
adalah sebanyak .
55 69
c. Gabungan
Limas
Segilima
.
dan
Prisma
Segilima
H
Gambar 3.3.7 Limas Segilima .
dan Prisma Segilima
Kedua bangun ruang pada Gambar 3.3.7 akan digabung, yaitu bidang alas dari limas segilima prisma segilima
.
diimpitkan dengan bidang atas
dari
. Gabungan kedua bangun ruang tersebut adalah
sebagai berikut:
Gambar 3.3.8 Gabungan Limas Segilima .
dan Prisma Segilima
Pada Gambar 3.3.8 diperoleh suatu bangun ruang . titik puncak , bidang alas
dengan
yang berbentuk segilima, 5 bidang tegak atas
56 70
,
, ,
, ,
dan
yang berbentuk segitiga, dan 5 bidang tegak bawah dan
,
yang berbentuk persegi panjang. tersebut akan diwarna masing-masing
Pada bangun ruang .
permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan adalah sebagai berikut:
permukaan (bidang) pada bangun ruang .
2
1
1 2
2
1
3
2
4
1
3 4
Gambar 3.3.9 Face Colouring pada Bangun Ruang . Pada Gambar 3.3.9 diperoleh pewarnaan permukaan pada bangun ruang .
tegak bawah
yaitu warna 1 untuk bidang tegak atas dan
bidang tegak bawah bidang tegak bawah
, warna dan
dan
untuk bidang tegak atas , warna
, dan warna
dan bidang dan
untuk bidang tegak atas
untuk bidang alas
dan dan
. Jadi, warna
minimal yang dibutuhkan (bilangan kromatik) untuk mewarnai permukaan bangun ruang .
adalah sebanyak .
57 71
d. Gabungan
Limas
Segienam
.
Gambar 3.3.10 Limas Segienam .
dan
Prisma
Segienam
dan Prisma Segienam
Kedua bangun ruang pada Gambar 3.3.10 akan digabung, yaitu bidang alas dari limas segienam . dari prisma segienam
diimpitkan dengan bidang atas . Gabungan kedua bangun ruang tersebut
adalah sebagai berikut:
Gambar 3.3.11 Gabungan Limas Segienam . Segienam
dan Prisma
58 72
Pada Gambar 3.3.11 diperoleh suatu bangun ruang dengan titik puncak , bidang alas tegak atas
,
tegak bawah
,
,
,
yang berbentuk segienam, 6 bidang
dan
, ,
,
.
yang berbentuk segitiga, dan 6 bidang dan
,
yang berbentuk persegi
panjang. Pada bangun ruang
tersebut akan diwarna masing-
.
masing permukaan atau bidangnya dan harus mendapat tepat satu warna serta dua bidang yang berpotongan atau berbatasan langsung berwarna berbeda. Pewarnaan permukaan (bidang) pada bangun ruang
adalah sebagai
.
berikut: 2 1 2
2
1
1
3
2 1
2
1 1
2 3
Gambar 3.3.12 Face Colouring pada Bangun Ruang . Pada Gambar 3.3.12 diperoleh pewarnaan permukaan pada bangun ruang yaitu warna 1 untuk bidang tegak atas
.
bidang tegak bawah ,
dan
untuk bidang alas
,
dan
dan bidang tegak bawah
, warna ,
,
dan
dan
untuk bidang tegak atas dan
, dan warna
. Jadi, warna minimal yang dibutuhkan (bilangan
59 73
kromatik) untuk mewarnai permukaan bangun ruang
.
adalah
sebanyak . 2. Mencari Pola Bilangan Kromatik Pewarnaan Permukaan Gabungan Limas Segi- dan Prisma Segi- (
)
Dari beberapa contoh pewarnaan permukaan pada bangun ruang gabungan limas segi- dan prisma segi- (
) diperoleh bilangan kromatiknya yaitu 4 3 4 3
Dari data di atas terlihat pola yang dapat dinyatakan secara umum sebagai berikut: 4,untuk
ganjil ,
3, untuk
,
3
genap
3. Pola yang Diperoleh Dinyatakan sebagai Konjektur 4,untuk
ganjil ,
3, untuk
,
3
genap
Konjektur tersebut bersifat induktif dan belum diterima kebenarannya dalam matematika.
60 74
4. Konjektur Tersebut Dinyatakan sebagai Teorema dan Dibuktika Teorema 3.3 Bilangan kromatik untuk pewarnaan permukaan (face colouring) pada gabungan limas segi- dan prisma segi- ( 4,untuk
ganjil ,
3, untuk
) adalah
,
3
genap
Bukti: a. Kasus I, untuk
Ganjil
Setiap gabungan limas segi- dan prisma segi- ( 1 bidang (permukaan) yaitu
mempunyai 2
tegak bawah, dan ,
ganjil
bidang tegak atas,
bidang
bidang alas. Misalkan bidang tegak atas diberi nama
1,2,3, … , bidang tegak bawah diberi nama
alas diberi nama
) dimana
,
dan bidang
1,2,3, …
dimulai dari bidang yang berbatasan langsung
.
dan berakhir pada bidang yang
(berpotongan) dengan bidang tegak atas
berbatasan langsung (berpotongan) dengan dengan bidang tegak atas Terlihat bahwa
dan
dimana
ganjil dan
.
tidak saling
berbatasan langsung (tidak berpotongan) maka dapat diberi warna sama. Demikian juga
dan
dimana
genap tidak saling berbatasan langsung
(tidak berpotongan) maka dapat diberi warna sama. Pilih warna dimana dimana
untuk
dan
dimana ganjil dan
. Karena
genap berbatasan langsung (berpotongan) dengan
ganjil, maka
dan
maka diberi warna . Karena
dimana dan
dan
dan
genap tidak boleh diberi warna , berbatasan langsung (berpotongan)
61 75
dengan maka
dan dan
dimana
1 yang masing-masing berwarna
1,
tidak boleh diwarna
dan , maka diberi warna . Karena
bidang alas ( ) berbatasan langsung (berpotongan) dengan yang berwarna 1,2, dan , maka maka
diberi warna
dan ,
,
1,2,3, …
tidak boleh diberi warna-warna tersebut,
. Jadi, warna minimal yang diperlukan untuk
pewarnaan permukaan (face colouring) pada bangun ruang gabungan limas segi- dan prisma segi- , dimana 4, untuk
ganjil adalah sebanyak . Jadi, terbukti
ganjil.
b. Kasus II, untuk
Genap
Setiap gabungan limas segi- dan prisma segi- ( mempunyai 2
1 bidang (permukaan) yaitu
tegak bawah, dan ,
genap
bidang tegak atas,
bidang
bidang alas. Misalkan bidang tegak atas diberi nama
1,2,3, … , bidang tegak bawah diberi nama
alas diberi nama
) dimana
,
1,2,3, …
dan bidang
dimulai dari bidang yang berbatasan langsung
.
dan berakhir pada bidang yang
(berpotongan) dengan bidang tegak atas
berbatasan langsung (berpotongan) dengan dengan bidang tegak atas dan
Terlihat bahwa
dimana
.
ganjil tidak saling berbatasan
langsung (tidak berpotongan) maka diberi warna sama. Demikian juga
dan
dimana genap tidak saling berbatasan langsung (tidak berpotongan) maka dapat diberi warna sama. Pilih warna
untuk
dan
dimana
ganjil. Karena
dimana genap berbatasan langsung (berpotongan) dengan
dan
dan dimana
62 76
ganjil, maka
dan
dimana genap tidak boleh diberi warna , maka diberi
warna . Karena bidang alas ( ) berbatasan langsung (berpotongan) dengan ,
1,2,3, …
yang berwarna
warna tersebut, maka
dan , maka
tidak boleh diberi warna-
diberi warna . Jadi, warna minimal yang diperlukan
untuk pewarnaan permukaan (face colouring) pada bangun ruang gabungan limas segiterbukti
dan prisma segi- , dimana 3, untuk
genap.
genap adalah sebanyak
. Jadi,
77
BAB IV PENUTUP
4.1 Kesimpulan Berdasarkan hasil pembahasan pada bab III, maka dapat diambil kesimpulan, yaitu: 1. Untuk menentukan bilangan kromatik permukaan (face chromatic number) pada limas dilakukan dengan langkah-langkah berikut: a. Menentukan ,
,
, dan
bilangan
kromatik
pada
beberapa
kasus
yaitu
,
b. Mencari pola bilangan kromatik pada langkah (a), c. Pola yang diperoleh dinyatakan sebagai konjektur, d. Konjektur tersebut dinyatakan sebagai teorema dan dibuktikan. Berdasarkan langkah-langkah di atas diperoleh: 4, untuk n ganjil ,
,
3
3, untuk n genap
2. Untuk menentukan bilangan kromatik permukaan (face chromatic number) pada prisma dilakukan dengan langkah-langkah berikut: a. Menentukan bilangan kromatik pada beberapa kasus yaitu pada ,
,
, dan
,
b. Mencari pola bilangan kromatik pada langkah (a), c. Pola yang diperoleh dinyatakan sebagai konjektur, d. Konjektur tersebut dinyatakan sebagai teorema dan dibuktikan. 63
64 78
Berdasarkan langkah-langkah di atas diperoleh: 4, untuk n ganjil ,
,
3
3, untuk n genap
3. Untuk menentukan bilangan kromatik permukaan (face chromatic number) pada gabungan limas dan prisma dilakukan dengan langkah-langkah berikut: a. Menentukan bilangan kromatik pada beberapa kasus yaitu
,
,
, dan
. b. Mencari pola bilangan kromatik pada langkah (a), c. Pola yang diperoleh dinyatakan sebagai konjektur, d. Konjektur tersebut dinyatakan sebagai teorema dan dibuktikan. Berdasarkan langkah-langkah di atas diperoleh: 4, untuk n ganjil ,
,
3
3, untuk n genap
4.2 Saran Pada skripsi ini, penulis hanya memfokuskan pada pokok bahasan mengenai face colouring pada limas, prisma, dan gabungan limas dan prisma. Oleh karena itu, untuk penulisan skripsi selanjutnya, penulis menyarankan kepada pembaca untuk mengkaji masalah face colouring pada graf-graf yang lain atau komputasi
pemprograman
tampilannnya bagus.
sehingga
hasilnya
lebih
cepat,
akurat,
dan
79
DAFTAR PUSTAKA Bondy, J.A dan Murty, U.S.R. 1982. Graph Therory with Application. Canada:Department of Combinatorics and Optimization, University of Waterloo. Chartrand, G. dan Lesniak, L. 1986. Graph and Digraph 2 Wadsworth.Inc.
Edition. California:
Masruri, M. Hadi dan Rossidy Imron. 2007. Filsafat Sains dalam Al-qur’an. Malang: UIN Malang Press. Muhammad, Syaikh. 2003. Syarhu Ushulil Iman: Prinsip-prinsip Dasar Keimanan.Riyadh: Ha’iatul Iqhatsah Al-Islamiah Al-Alamiah. Purwanro. 1998. Matematika Diskrit. Malang: IKIP Malang. Shihab, Quraish. 2003. Tafsir Al-Mishbah: Pesan, Kesan, dan Keserasian AlQur’an. Jakarta: Lentera Hati. Suryanto. 1986. Materi Pokok Pengantar Teori Graph. Jakarta: Karunika Universitas terbuka. http://www.crayonpedia.org/mw/ Kubus Balok Prisma Tegak dan Limas 8.2 # C. Prisma. Diakses pada tanggal 9 Juli 2009 pukul 06.00 WIB http://www.crayonpedia.org/mw/ Bola dan Kerucut. Diakses pada tanggal 24 Juli 2009 pukul 06.00 WIB
80
DEPARTEMEN AGAMA RI UNIVERSITAS ISLAM NEGERI MAULANA MALIK IBRAHIM (UIN MMI) MALANG FAKULTAS SAINS DAN TEKNOLOGI Jl. Gajayana No. 50 Dinoyo Malang (0341)551345 Fax. (0341)572533
BUKTI KONSULTASI SKRIPSI Nama NIM Fakultas/ jurusan Judul skripsi
: Ririn Salusiningsih : 04510002 : Sains Dan Teknologi/ Matematika : FACE COLOURING PADA LIMAS, PRISMA, DAN GABUNGAN LIMAS DAN PRISMA
Pembimbing I : Evawati Alisah, M.Pd Pembimbing II : Ahmad Barizi, M.A No Tanggal HAL
Tanda Tangan
1
2 Juli 2009
Proposal
1.
2
3 Juli 2009
ACC Proposal
3
16 Juli 2009
Konsultasi BAB III
4
17 Juli 2009
Revisi BAB III
5
18 Juli 2009
Konsultasi BAB I dan II
6
18 Juli 2009
Kajian Keagamaan
7
21 Juli 2009
Revisi BAB I dan II
8
21 Juli 2009
Kajian Keagamaan
9
22 Juli 2009
Kajian Keagamaan
10
22 Juli 2009
ACC BAB I, II, dan III
11
23 Juli 2009
ACC Keseluruhan
2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Malang, 23 Juli 2009 Mengetahui, Ketua Jurusan Matematika
Sri Harini, M.Si NIP. 150 318 321