LAPORAN TUGAS AKHIR
Topik Tugas Akhir : Kajian Matematika Murni
PELABELAN GRAF SIKLUS UNTUK MENGKONSTRUKSIKAN GRAF SISI AJAIB
TUGAS AKHIR Diajukan Kepada Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang sebagai Salah Satu Prasyarat untuk Mendapatkan Gelar Sarjana Pendidkan Matematika
oleh : EVI DENTARY MIFTAKHUL RACHMAN NIM : 201110060311043
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH MALANG 2015
i
ii
iii
iv
MOTTO
Melawan Kemalasan untuk Mendapatkan Keberhasilan adalah Ujian untuk Meningkatkan Kualitas Diri.
Pendidikan adalah senjata paling mematikan di dunia, karena dengan itu anda dapat mengbah dunia (Nelson Mandela).
Jika kamu tidak mengejar apa yang kamu inginkan , maka kamu tidak akan mendapatkannya. Jika kamu tidak bertanya maka jawabannya adalah tidak. Jika kamu tidak melangkah maju, kamu akan berada ditempat yang sama (Nora Roberts).
v
PERSEMBAHAN
Alhamdulillah, Rasa syukur kepada Allah SWT yang memberikan rahmat-Nya, nikmat-Nya serta hidayah-Nya dan Rasulullah SAW yang memberikan kemudahan dan kelancaran sehingga penulis dapat menyelesaikan Tugas Akhir ini. 1. Kupersembahkan tugas akhir ini untuk kedua orang tuaku tercinta dan mbak mita tersayang yang telah membantu semangat serta segalanya, terimakasih untuk semua dukungan, doa, dan semangatnya. 2. Kupersembahkan juga tugas akhir ini untuk keluarga besar di malang terimakasih buat doa, bantuan, dan dukungannya. 3. Serta kupersembahkan juga tugas akhir ini untuk seseorang, terimakasih buat cinta dan kasih sayang serta semangatnya.
vi
KATA PENGANTAR
ﺑﺴﻢﷲﺍﻟﺮﺣﻤﻦﺍﻟﺮﺣﻴﻢ Syukur Alhamdulillah penulis panjatkan kehadirat Allah SWT atas rahmat, hidayah, dan inayah-Nya sehingga penulis dapat menyelesaikan tugas akhir ini dengan judul “Pelabelan Graf Siklus untuk Mengkonstruksikan Graf Simpul Ajaib”. Sholawat serta salam tercurahkan kepada Rasulullah Muhammad SAW, keluarga serta sahabatnya. Tugas Akhir ini merupakan metode kajian dengan mempelajari studi literatur pada pokok bahasan yang berhubungan dengan pembahasan. Penulis menyadari bahwa Tugas Akhir ini dapat diselesaikan berkat bimbingan, bantuan dan motivasi dari berbagai pihak. Oleh karena itu dengan ketulusan hati penulis menghaturkan rasa hormat dan terima kasih kepada : 1. Dra. Siti Inganah, M.M.,M.Pd., selaku dosen pembimbing I yang telah meluangkan waktu dan kesabaran dalam memberikan petunjuk, bimbingan dan pengarahan kepada penulis sehingga Tugas Akhir ini terselesaikan. 2. Dr. Yus Mochamad Cholily, M.Si selaku dosen pembimbing II yang telah meluangkan waktu dan kesabaran dalam memberikan petunjuk, bimbingan dan pengarahan kepada penulis sehingga Tugas Akhir ini terselesaikan. Semoga Allah SWT menunjukkan jalan dan memberikan cahaya-Nya, serta melapangkan dengan limpahan iman dan keindahan tawakal kepada-Nya. Penulis berharap semoga Tugas Akhir ini bermanfaat bagi semua pihak yang berkepentingan. Namun demikian tiada manusia yang sempurna, oleh karena itu dengan kerendahan hati, kritik dan saran yang membangun sangat penulis harapkan untuk menjadikan Tugas akhir ini lebih sempurna. Malang, 25 April 2015
Penulis
vii
ABSTRAK Evi Dentary. 2015. Pelabelan Graf untuk Mengkonstruksikan Graf Sisi Ajaib. Tugas Akhir, Program Studi Pendidikan Matematika, Fakultas Keguruan dan Ilmu Pendidikan, Universitas Muhammadiyah Malang, Pembimbing (I) : Dra. Siti Inganah, M.M.,M.Pd, Pembimbing (II) : Dr. Yus Mochamad Cholily, M.Si
Teori graf merupakan cabang ilmu matematika yang dalam penerapannya banyak dimanfaatkan untuk menyelesaikan permasalahan matematika, salah satunya dalam pelabelan graf. Salah satu manfaat pelabelan graf untuk memudahkan dalam membaca sebuah graf. Pelabelan graf merupakan pemetaan injektif yang memetakan unsur himpunan titik dan atau unsur himpunan sisi ke bilangan asli yang disebut label. Suatu pelabelan simpul ajaib adalah jika graf G dengan
simpul dan
sisi dilabelkan dari 1 hingga
demikian sehingga
simpul dan sisi yang insiden dijumlahkan menghasilkan jumlah yang sama, dengan bilangan ajaib
(
)(
)
, untuk setiap
merupakan jumlah seluruh label sisi graf G dan
dengan
bilangan ajaib yang
konstan. Pelabelan Sisi Ajaib (Edge magic labeling) adalah jika sebuah graf G adalah simpul V(G) dan sisi E(G) dilabelkan dengan bilangan bulat *
| ( )
( )|+ sehingga setiap sisi dengan simpul – simpul yang ajasen
terhadap sisi tersebut berjumlah sama. Pembahasan pada tugas akhir ini adalah tentang pelabelan graf simpul ajaib pada graf siklus yang jumlah label simpulnya ganjil. Maka dijelaskan beberapa pelabelan graf siklus diantaranya pelabelan sisi ajaib graf siklus dengan simpul dan sisi ganjil serta bilangan ajaib minimumnya dan pelabelan sisi Aaaib pada graf siklus dengan simpul dan sisi ganjil serta bilangan ajaib maksimumnya.
Kata Kunci : Graf sisi ajaib, graf siklus, bilangan ajaib minimum dan maksimum
viii
ABSTRACT Evi Dentary. 2015. Graph Labeling to Construct Edge Megic Graf. Thesis, Department of Mathematics Education, Faculty of teacher training and Education Science, University of Muhammadiyah Malang, Adviser (I) : Dra. Siti Inganah, M.M.,M.Pd, Adviser (II) : Dr. Yus Mochamad Cholily, M.Si
Graph theory is branch of mathematics that its application widely used to solve mathematical problems, one of which in the labeling of a graph. One of benefit labeling of a graph for simplify read a graph. Graph labeling is an injective mapping that maps the elements of the set vertices or element of the set edges to the set numbers is called the label. A vertices magic labeling is graph G with vertices and
edges labeled from 1 to
such that vertices and its incident
edge adds up to the same number, with magic number every
with
(
)(
)
be the sum of all edge labels of graph G and
, to magic
labeling constant.
Edge Magic Labeling (edge magic labeling) is if a graph G is vertex V (G) and the E (G) is labeled with integers *
| ( )
( )|+ so that each side
with the vertex ajasen against the side of the same number. Explanation of this thesis is about labeling of edge magic graph for odd cycle graphs. Then described some of the labeling cycle graph such as edge magic labeling cycle with odd vertices, edge and magic number minimum. Then edge magic labeling cycle with odd vertices, edge and magic number maximum.
.
Keywords: Edge magic graph, cycle graph, magic number minimum and maximum
ix
DAFTAR ISI
LAPORAN TUGAS AKHIR ..............................................................................................i LEMBAR PERSETUJUAN .............................................................................................. ii LEMBAR PENGESAHAN ............................................................................................. iii SURAT PERNYATAAN..................................................................................................iv MOTTO ..............................................................................................................................v PERSEMBAHAN .............................................................................................................vi KATA PENGANTAR .................................................................................................... vii ABSTRAK .......................................................................................................................viii DAFTAR ISI......................................................................................................................x DAFTAR GAMBAR ...................................................................................................... xii BAB I PENDAHULUAN ................................................. Error! Bookmark not defined. 1.1. Latar Belakang ........................................................ Error! Bookmark not defined. 1.2. Rumusan Masalah ................................................... Error! Bookmark not defined. 1.3 Pembatasan Masalah ............................................... Error! Bookmark not defined. 1.4 Tujuan Kajian ......................................................... Error! Bookmark not defined. 1.5 Manfaat Kajian ....................................................... Error! Bookmark not defined. 1.6 Metode Kajian ........................................................ Error! Bookmark not defined. BAB II TINJAUAN PUSTAKA ....................................... Error! Bookmark not defined. 2.1. Sejarah Singkat dan Perkembangan Teori Graf ...... Error! Bookmark not defined. 2.2. Pengertian Dasar Graf ............................................. Error! Bookmark not defined. 2.3 Jenis-Jenis Graf ....................................................... Error! Bookmark not defined. 2.5 Pelabelan Sisi Ajaib pada Graf Siklus dengan Simpul dan Sisi GanjilError! Bookmark not defined. 2.6 Pelabelan Sisi ajaib Graf Siklus dengan Simpul dan Sisi Ganjil serta Bilangan Ajaib Minimumnya ................................................. Error! Bookmark not defined. 2.7 Pelabelan Sisi Ajaib pada Graf Siklus dengan Simpul dan Sisi Ganjil serta Bilangan Ajaib Maksimumnya ............................... Error! Bookmark not defined. BAB III PEMBAHASAN ................................................. Error! Bookmark not defined. 3.1 Penerapan Proses Graf Siklus dalam Membentuk Graf Sisi AjaibError! Bookmark not defined. 3.2 Penerapan Pelabelan Sisi ajaib Graf Siklus dengan Simpul dan Sisi Ganjil serta Bilangan Ajaib Minimumnya .................................. Error! Bookmark not defined.
x
BAB IV Kesimpulan dan Saran ........................................ Error! Bookmark not defined. 4.1 Kesimpulan ............................................................. Error! Bookmark not defined. 4.2 Saran ....................................................................... Error! Bookmark not defined. DAFTAR PUSTAKA .......................................................................................................33
xi
DAFTAR GAMBAR
Gambar 2.1 (a) Ilustrasi Jembatan Königsberg (Sutarno dkk, 2012: 79) ........................6 Gambar 2.1 (b) Graf model jembatan Königsberg (Sutarno dkk, 2012: 79) ......................7 Gambar 2.2 Graf
dan Graf
...................................................................................9
Gambar 2.3 Graf Lengkap ............................................................................................10 Gambar 2.4 (a) Graf Siklus dengan n= 3 ....................................................................10 Gambar 2.4 (b) Graf Siklus dengan n = 5 ..................................................................11 Gambar 2.5 (a) Graf Simpul Ajaib ..............................................................................12 Gambar 2.5 (b) Graf Sisi Ajaib ...................................................................................12 Gambar 2.6 Beberapa Graf Lintasan ...........................................................................12 Gambar 2.7 Pelabelan Sisi Ajaib pada Graf Siklus dengan n = 3 dan k = 26 ........13 Gambar 2.8 Pelabelan Sisi tidak Ajaib pada Graf Siklus dengan n = 7 .................14 Gambar 2.9 Label Graf Simpul Ajaib pada Graf Siklus dengan Banyak Simpul dan Sisi Ganjil dan Bilangan Ajaib Minimum ......................................17 Gambar 2.10 Label Graf Sisi Ajaib pada Graf Siklus dengan banyak Simpul dan Sisi Ganjil dan Bilangan Ajaib Minimum .............................................18 Gambar 2.11 Label Graf Simpul Ajaib pada Graf Siklus dengan banyak Simpul dan Sisi Ganjil dan Bilangan Ajaib Maksimum ...................................20 Gambar 2.12 Label Graf Sisi Ajaib pada Graf Siklus dengan banyak Simpul dan Sisi Ganjil dan Bilangan Ajaib Maksimum ............................................21 Gambar 3.1 Graf Siklus dengan Banyak Simpul dan Sisi Ganjil n = 9...................22 Gambar 3.2 Tahap Pelabelan Simpul pada Graf Siklus dengan Banyak Simpul dan Sisi Ganjil n = 9 ........................................................................................23 Gambar 3.3 Pelabelan Graf Simpul Ajaib pada Graf Siklus dengan Banyak Simpul dan Sisi Ganjil n = 9 ....................................................................24 Gambar 3.4 Pelabelan Sisi Ajaib pada Graf Siklus dengan Banyak Simpul dan Sisi Ganjil n = 9, k = 33 ............................................................................25 Gambar 3.5 Graf Siklus dengan Banyak Simpul dan Sisi Ganjil n = 7...................26 Gambar 3.6 Tahan Pelabelan Simpul pada Graf Siklus dengan Banyak Simpul dan Sisi Ganjil n = 7 .........................................................................................26
xii
Gambar 3.7 Pelabelan Graf Simpul Ajaib pada Graf Siklus dengan banyak impul dan Sisi Ganjil n = 7 .................................................................................27 Gambar 3.8 Pelabelan Sisi Ajaib pada Graf Siklus dengan Banyak Simpul dan Sisi Ganjil n = 7, k = 24 ............................................................................28
xiii
DAFTAR PUSTAKA
Sutarno, H, Priatna, N dan Nurjanah. (2005). Matematika Diskrit. Malang: Universitas Negeri Malang Cunningham, D. (2004). Vertex-Magic. Electronical Journal of Undergraduate Mathematics, Furman University Munir, R. (2003). Matematika Diskrit. Bandung: Informatika Kusumah, Y. S. (1998). Matematika Diskrit. Bandung: IKIP Bandung Press Gallian, J.A. (2011). A Dynamic Survey of Graph Labeling. The Electronic Journal Combinatoric, University of Minnesota Duluth Lipschutz, Seymour, Ph.D, dkk. (1998).
Matematika Dikrit 2. Salemba:
Terjemahan Tim Editor Salemba Teknik Deo, N. (1986). Graph Theory With Aplications to Enginering and Computer Science. Prentice-Hall of India Private Limited Ali, G. (2005). Graph Labeling. Abdus Salam School of Matematical Science GC University, Lahore Pakistan Budayasa, I. K. Matematika Diskrit 1. Surabaya: IKIP Surabaya Siang, J. J. (2002). Matmatika Diskrit dan Aplikasinya pada Ilmu Komputer. Yogyakarta: Andi Yogyakarta Sadikin, A. (2008). Penyelesaian Masalah Pelabelan Graph Vertex Magic pada Graph Cycle Sederhana. Bogor Wallis, W. D, Philips, P.S. Totally Magic Graphs Departement of Mathematics. Southern Illinois University, Carbondale IL, USA Wilson, R. J. (1996). Introduction to Graph Theory. Fourt Edition. Prentice Hall England Jaenudin. (2007). Pelabelan Graf Siklus Sederhana untuk Mengkonstruksikan Vertex Magic Graph. Universitas Pendidikan Indonesia, Bandung Enomoto, H, Liado, A.S. (1998). Super Edge Magic Graps. SUT Journal of Mathematics Wallis, W. D. (2000). Edge Magic Total Labelings. Department of Mathematics. Southern Illinois University, USA.
xiv
Swaminathan, V. (2002). Super Vertex Magic Labeling. Department of Mathematics. Saraswathi Narayanan Collage, India.
xv
