i

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

ii

iii

iv

v

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).

vi

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.

vii

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

viii

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 dengan

merupakan jumlah seluruh label sisi graf G dan 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

ix

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 ( )( )

, to

every with be the sum of all edge labels of graph G and 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

x

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.

xi

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

xii

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

xiii

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

xiv

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.

xv

Swaminathan, V. (2002). Super Vertex Magic Labeling. Department of

Mathematics. Saraswathi Narayanan Collage, India.