PELABELAN GRAF SIKLUS SEDERHANA UNTUK MENGKONSTRUKSI VERTEX-MAGIC GRAPH

MAKALAH

Disusun untuk Melengkapi salah satu Tugas Mata Kuliah Seminar Pendidikan Matematika Semester Genap Tahun Akademik 2006/2007

Disusun oleh :

J A E N U D I N NIM. 040521

JURUSAN PENDIDIKAN MATEMATIKA FAKULTAS PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS PENDIDIKAN INDONESIA

2007

i

KATA PENGANTAR

Bismillahirrahmanirrahim

Segala puji hanya diperuntukkan bagi Allah SWT yang telah

menurunkan Al-Qur’an sebagai petunjuk bagi orang yang bertaqwa, Sang Maha

Pencipta yang Maha Sempurna dalam setiap penciptaan-Nya. Hanya karena-Nya

penyusun dapat menyelesaikan penyusunan makalah ini. Semoga shalawat serta

salam tercurahlimpahkan kepada pemimpin alam, Nabi Muhammad SAW yang

telah membawa manusia dari gelapnya kehidupan jahiliyah kepada jalan yang

lurus yang diridhai Allah SWT.

Masalah dalam makalah yang berjudul "Pelabelan Graf Siklus Sederhana

untuk Mengkonstruksi Vertex-Magic Graph" ini adalah pelabelan sisi dan simpul

sebuah graf siklus untuk memperoleh vertex-magic graph (graf simpul ajaib).

Vertex-magic graph adalah graf siklus dengan v simpul dan e sisi yang diberi

label dari 1 hingga (v + e), demikian sehingga apabila setiap label simpul dan sisi

yang insiden pada simpul tersebut dijumlahkan akan diperoleh jumlah yang sama.

Jumlah yang sama tersebut dinamakan magic number (bilangan ajaib). Untuk

mengkonstruksi sebuah vertex-magic graph dapat dilakukan dengan beberapa

teknik. Salah satunya adalah pelabelan graf siklus berdasarkan magic number

maksimum dan minimum. Selain itu, bisa juga dilakukan berdasarkan penempatan

bilangan ganjil atau bilangan genap sebagai label simpulnya.

Dalam kesempatan ini penyusun mengucapkan terima kasih yang tak

terhingga kepada Bapak Drs. H. Yaya S. Kusumah, M.Sc., Ph.D. selaku

pembimbing yang telah mengarahkan penyusun untuk menyelesaikan penulisan

makalah ini. Juga kepada semua pihak yang telah memberikan bantuan kepada

penyusun. Semoga segala amal baik yang telah diberikan kepada penyusun

dibalas Allah SWT dengan pahala yang berlipat ganda.

Penyusun sangat menyadari bahwa penyusunan makalah ini masih jauh

dari sempurna. Untuk itu, penyusun sangat berharap kepada pembaca untuk dapat

ii

memberikan kritik dan saran yang membangun untuk perbaikan penyusunan

makalah di masa mendatang.

Hanya kepada Allah SWT penyusun berserah diri dan memohon

perlindungan.

Bandung, Maret 2007

Penyusun,

iii

DAFTAR ISI

LEMBAR PENGESAHAN ............................................................................. i

KATA PENGANTAR ..................................................................................... ii

DAFTAR ISI ................................................................................................... iv

DAFTAR TABEL ........................................................................................... vi

DAFTAR GAMBAR ....................................................................................... vii

BAB I PENDAHULUAN

1.1 Latar Belakang Masalah ............................................................ 1

1.2 Rumusan dan Batasan Masalah ................................................. 2

1.3 Tujuan Penulisan ........................................................................ 2

1.4 Manfaat Penulisan ...................................................................... 3

BAB II KONSEP DASAR TEORI GRAF

2.1 Sejarah Singkat Teori Graf ........................................................ 4

2.2 Pengertian Graf .......................................................................... 5

2.3 Graf Sederhana .......................................................................... 6

2.4 Graf Terhubung ......................................................................... 7

2.5 Graf Siklus ................................................................................. 8

BAB III VERTEX-MAGIC GRAPH

3.1 Pengertian Vertex-Magic Graph ................................................ 9

3.2 Batas Bawah Magic Number ..................................................... 10

3.3 Batas Atas Magic Number ......................................................... 15

3.4 Pelabelan Graf Siklus dengan Banyak Simpul Ganjil

dan Magic Number Maksimum .................................................

18

3.5 Pelabelan Graf Siklus dengan Banyak Simpul Ganjil

dan Magic Number Minimum ...................................................

21

iv

3.6 Pelabelan Graf Siklus dengan Banyak Simpul Ganjil

dan Bilangan Ganjil sebagai Label Simpul ...............................

24

3.7 Pelabelan Graf Siklus dengan Banyak Simpul Ganjil

dan Bilangan Genap sebagai Label Simpul ...............................

27

BAB IV KESIMPULAN DAN SARAN

4.1 Kesimpulan ................................................................................ 30

4.2 Saran .......................................................................................... 31

DAFTAR PUSTAKA ...................................................................................... 32

v

DAFTAR TABEL

Tabel 3.1 Aturan Pelabelan Sisi Graf Siklus dengan Banyak Simpul Ganjil

dan Magic Number Maksimum .......................................................

20

Tabel 3.2 Aturan Pelabelan Sisi Graf Siklus dengan Banyak Simpul Ganjil

dan Magic Number Minimum .........................................................

23

Tabel 3.3 Aturan Pelabelan Sisi Graf Siklus dengan Banyak Simpul Ganjil

dan Bilangan Ganjil sebagai Label Simpul .....................................

25

Tabel 3.4 Aturan Pelabelan Sisi Graf Siklus dengan Banyak Simpul Ganjil

dan Bilangan Genap sebagai Label Simpul .....................................

28

vi

DAFTAR GAMBAR

Gambar 2.1 Jembatan Königsberg ................................................................. 4

Gambar 2.2 Graf dengan Empat Simpul dan Tiga Sisi ................................... 6

Gambar 2.3 Sisi Rangkap dan Loop ................................................................ 6

Gambar 2.4 Graf Terhubung ........................................................................... 8

Gambar 2.5 Graf Siklus ................................................................................... 8

Gambar 3.1 Vertex-Magic Graph dan Edge-Magic Graph ............................ 10

Gambar 3.2 Label Graf Siklus dengan Banyak Simpul Ganjil

dan Magic Number Maksimum ...................................................

19

Gambar 3.3 Graf Siklus dengan 3 Simpul dan Magic Number 12 .................. 21

Gambar 3.4 Graf Siklus dengan 5 Simpul dan Magic Number 19 .................. 21

Gambar 3.5 Label Graf Siklus dengan Banyak Simpul Ganjil

dan Magic Number Minimum .....................................................

22

Gambar 3.6 Graf Siklus dengan 3 Simpul dan Magic Number 9 ................... 23

Gambar 3.7 Graf Siklus dengan 5 Simpul dan Magic Number 14 .................. 24

Gambar 3.8 Label Graf Siklus dengan Banyak Simpul Ganjil dan Bilangan

Ganjil sebagai Label Simpul ........................................................

25

Gambar 3.9 Graf Siklus dengan 3 Simpul dan Magic Number 11 .................. 26

Gambar 3.10 Graf Siklus dengan 5 Simpul dan Magic Number 17 ................ 26

Gambar 3.11 Label Graf Siklus dengan Banyak Simpul Ganjil

dan Bilangan Genap sebagai Label Simpul ...............................

27

Gambar 3.12 Graf Siklus dengan 3 Simpul dan Magic Number 10 ................ 28

Gambar 3.13 Graf Siklus dengan 5 Simpul dan Magic Number 16 ................ 29

1

BAB I

PENDAHULUAN

1.5 Latar Belakang Masalah

Teori graf adalah salah satu cabang matematika yang cukup penting

untuk dipelajari dan dikembangkan. Teori graf mempunyai berbagai terapan

dalam berbagai bidang ilmu pengetahuan, diantaranya dalam model jaringan

transportasi, sistem komunikasi, silsilah keluarga, desain arsitektur, dan masih

banyak lagi terapan lainnya (Sutarno, dkk, 2003: 71-74)

Pada awalnya teori graf diperkenalkan oleh Leonhard Euler sebagai

solusi permasalahan mungkin tidaknya melewati ketujuh jembatan di kota

Königsberg (sekarang dikenal sebagai Kaliningrad, Rusia) dan kembali ke tempat

semula tepat satu kali. Kemudian Leonhard Euler memodelkan permasalahan

tersebut ke dalam model matematika berupa bagan yang terdiri dari titik dan garis.

Titik merepresentasikan kota yang dihubungkan jembatan dan garis sebagai

jembatan yang menghubungkan kota. Model ini kemudian dikenal sebagai teori

graf.

Teori graf masih terus berkembang selaras dengan pemikiran-pemikiran

para ahli yang mengembangkannya. Salah satu masalah cukup terkenal dalam

teori graf adalah Konjektur Empat Warna (Four Color Conjecture), yaitu masalah

pewarnaan peta dengan menggunakan empat macam warna sehingga setiap negara

yang berbatasan mempunyai warna yang berbeda.

Selain itu, masalah yang cukup menarik dalam teori graf adalah pelabelan

graf. Suatu graf siklus dengan e sisi dan v simpul dapat berikan label pada simpul

dan sisi mulai 1 sampai (v + e) sehingga apabila label-label pada sisi yang saling

ajasen dan label simpul yang insiden dengan sisi-sisi tersebut dijumlahkan, akan

menghasilkan jumlah yang sama. Jumlah ini kemudian disebut sebagai bilangan

ajaib (magic number) dan graf tersebut dikenal sebagai graf simpul ajaib (vertex-

magic graph). Untuk selanjutnya istilah bilangan ajaib disebut magic number saja

dan graf simpul ajaib disebut vertex-magic graph saja. Masalah yang cukup

2

menarik dari pelabelan graf tersebut adalah bagaimana cara memberikan label

simpul atau sisi sehingga diperoleh vertex-magic graph. Selain itu, berapakah

magic number minimum dan maksimum dari pelabelan suatu vertex-magic

graph?

Penyusun tertarik dengan masalah pelabelan graf siklus sederhana yang

mempunyai banyak simpul ganjil untuk mengkonstruksi vertex-magic graph.

Untuk itu penyusun memberikan judul pada makalah ini dengan: "Pelabelan Graf

Siklus Sederhana untuk Mengkonstruksi Vertex-Magic Graph".

1.6 Rumusan dan Batasan Masalah

Masalah dalam makalah ini dapat dirumuskan sebagai berikut:

a. Bagaimana pelabelan pada graf siklus sederhana yang banyak simpulnya

ganjil sehingga diperoleh vertex-magic graph?

b. Berapakah magic number maksimum dan minimum dari suatu vertex-magic

graph?

Makalah ini dibatasi hanya pada permasalahan pelabelan graf untuk

mendapatkan vertex-magic graph pada graf siklus sederhana yang banyak

simpulnya ganjil saja. Permasalahan pelabelan graf untuk mendapatkan vertex-

magic graph pada graf siklus yang lebih kompleks lagi dapat kita kembangkan

untuk penelitian atau penulisan berikutnya.

1.7 Tujuan Penulisan

Tujuan penulisan makalah ini adalah sebagai berikut:

a. Memperoleh gambaran umum tentang pelabelan graf siklus sederhana yang

banyak simpulnya ganjil sehingga diperoleh sebuah vertex-magic graph

b. Memperoleh gambaran umum tentang magic number maksimum dan

minimum dari suatu graf siklus sederhana dengan banyak simpul ganjil yang

termasuk vertex-magic graph

3

1.8 Manfaat Penulisan

Penyusunan makalah ini diharapkan dapat memberikan manfaat sebagai

berikut:

a. Menambah pengetahuan pembaca mengenai teori graf khususnya tentang

pelabelan graf. Karena masalah dalam makalah ini tidak diperkenalkan pada

materi perkuliahan matematika diskrit.

b. Sebagai pengetahuan dasar untuk memahami lebih lanjut mengenai teori graf

khususnya pelabelan graf.

4

BAB II

KONSEP DASAR TEORI GRAF

2.6 Sejarah Singkat dan Perkembangan Teori Graf

Teori graf pertama kali diperkenalkan oleh Leonhard Euler pada tahun

1736 sebagai upaya pemecahan masalah jembatan Königsberg. Masalah jembatan

Königsberg adalah mungkin tidaknya melewati ketujuh jembatan yang ada di kota

Königsberg masing-masing tepat satu kali dan kembali lagi ke tempat semula.

Untuk memecahkan masalah tersebut, Euler memisalkan daratan yang

dihubungkan jembatan dengan titik (vertex) dan jembatan dinyatakan dengan

garis atau sisi (edge). Dengan menggunakan model tersebut, Euler berkesimpulan

bahwa tidak mungkin seseorang dapat melalui ketujuh jembatan tersebut masing-

masing satu kali dan kembali lagi ke tempat semula (Sutarno, dkk, 2005: 65;

Munir, 2003: 291; Cunningham, 2004: 1).

Pada tahun 1847, G.R. Kirchoff (Sutarno, dkk, 2003: 58)

mengembangkan teori pohon yang digunakan dalam permasalahan listrik. Konsep

pohon ini kemudian digunakan oleh A. Cayley untuk menjelaskan masalah kimia

yaitu hidrokarbon pada tahun 1857.

Gambar 2.1 Jembatan Königsberg

5

Salah satu masalah yang cukup terkenal dalam teori graf adalah

Konjektur Empat Warna (The Four Color Conjecture) yang diajukan oleh Francis

Guthrie sekitar tahun 1850 (Cunningham, 2004: 1). Masalah dalam Konjektur

Empat Warna (The Four Color Conjecture) adalah mewarnai sebuah peta dengan

empat macam warna sedemikian hingga tiap negara yang berbatasan memiliki

warna yang berbeda.

Kemudian pada tahun 1859, Sir W. R. Hamilton menemukan sebuah

permainan dari kayu berbentuk dodecahedron beraturan yakni berupa polihedron

dengan 12 muka dan 20 titik. Tiap muka berbentuk sebuah pentagon beraturan

dan tiap pojoknya dibentuk oleh tiga sisi berbeda. Tiap pojok dodecahedron

tersebut dipasangkan dengan sebuah kota terkenal seperti London, New York,

Paris, dan lainnya. Masalah dalam permainan tersebut adalah mencari suatu rute

melalui sisi-sisi dodecahedron sehingga tiap kota dilalui tepat satu kali (Sutarno,

dkk, 2005: 65-66).

Pada tahun 1920-an König mengumpulkan hasil-hasil penelitian para ahli

matematika tentang teori graf termasuk hasil pemikirannya sendiri untuk

kemudian disusun menjadi sebuah buku yang diterbitkan pada tahun 1936. Buku

tersebut dianggap sebagai referensi pertama tentang teori graf (Sutarno, dkk,

2005: 66).

Banyak para ahli yang kemudian tertarik dengan teori graf ini, baik untuk

pengembangan teori graf murni maupun terapan. Para ahli tersebut diantaranya

adalah Claude Berge, Oysten Ore, Paul Erdos, William Tutte, dan Frank Harary

(Sutarno, dkk, 200: 66).

2.7 Pengertian Graf

Sebuah graf G adalah himpunan terhingga tak kosong yang memuat

objek-objek yang disebut simpul (titik/vertex) dan himpunan pasangan tak urut

antara simpul-simpul yang berlainan, yang disebut sisi (rusuk/edge). Himpunan

simpul dari graf G ditulis dengan V(G), sedangkan himpunan sisi dari graf G

dinyatakan dengan E(G) (Kusumah, 1998: 8-9).

6

Sebuah simpul dikatakan insiden dengan sebuah sisi jika simpul ini

merupakan ujung sisi tersebut atau menempel pada sisi tersebut. Jika sebuah sisi

menghubungkan dua buah simpul, maka kedua simpul tersebut dikatakan ajasen.

Apabila dua buah sisi insiden pada sebuah simpul, maka kita katakan bahwa

kedua sisi tersebut saling ajasen.

Perhatikan Gambar 2.2 di bawah ini. Dapat dilihat bahwa sisi e1 ajasen

dengan sisi e2, sisi e1 insiden pada simpul v2 dan simpul v1, simpul v1 ajasen

dengan simpul v2, simpul v2 ajasen dengan simpul v3 dan simpul v4.

v1

v4

v2

v3

e1

e2

e3

Gambar 2.2 Graf dengan Empat Simpul dan Tiga Sisi

2.8 Graf Sederhana

Dua buah sisi yang menghubungkan dua simpul yang sama disebut

sebagai sisi rangkap/ganda. Perhatikan Gambar 2.3 di bawah ini. e1 dan e2

merupakan contoh sisi rangkap/ganda karena baik e1 maupun e2 sama-sama

menghubungkan simpul v1 dan v2. Apabila sebuah sisi menghubungkan suatu

simpul dengan simpul itu sendiri, maka sisi tersebut disebut sebagai loop. Contoh

loop bisa dilihat pada Gambar 2.3 di bawah ini, yakni sisi e4 yang

menghubungkan simpul v3 dengan simpul itu sendiri.

v 1

v3

v2

e1

e 3

e2

e4

Gambar 2.3

Sisi Rangkap dan Loop

7

Sebuah graf yang tidak mengandung loop dan sisi rangkap disebut graf

sederhana.

2.9 Graf Terhubung

Berikut ini akan kita bahas beberapa istilah untuk menjelaskan graf

terhubung. Pertama-tama kita harus memahami jalan, yakni sebuah urutan tak nol

w = v0e1v1e2v2...ekvk yang suku-sukunya bergantian antara simpul dan sisi

sedemikian hingga vi-1 dan vi merupakan simpul-simpul ujung sisi ei untuk

1 < i < k. Dengan kata lain w adalah sebuah jalan dari vo ke vk. vo disebut simpul

awal dan vk disebut simpul akhir, sedangkan v1, v2, ..., vk -1 disebut simpul internal

(Sutarno, dkk, 2005: 92).

Apabila semua sisi pada sebuah jalan berlainan, maka disebut jejak.

Sedangkan apabila semua simpul v1, v2, v3, ..., vk dalam suatu jalan berbeda, maka

jalan tersebut dinamakan lintasan. Selanjutnya jejak yang mempunyai simpul awal

dan simpul akhirnya sama disebut jejak tertutup. Sebuah siklus akan terbentuk

dari jejak tertutup apabila simpul awal dan simpul internal pada sebuah jejak

tertutup tersebut berlainan.

Selain konsep yang telah dijelaskan di atas, masih ada konsep yang harus

kita bahas untuk menjelaskan graf terhubung, yaitu graf bagian. Graf K disebut

graf bagian dari graf G, dinyatakan dengan K ⊆ G, apabila himpunan semua

simpul di K merupakan himpunan bagian dari himpunan simpul di G dan

himpunan sisi di K juga merupakan himpunan bagian dari himpunan sisi di G.

Jika sebuah graf hanya terdiri dari satu bagian, maka graf tersebut disebut

graf terhubung. Dalam graf terhubung, untuk setiap pasang sisi sembarang vi dan

vj pada graf tersebut, terdapat suatu lintasan unik dari simpul vi dan vj. Gambar 2.4

di bawah ini merupakan contoh graf terhubung.

8

Gambar 2.4 Graf Terhubung

2.10 Graf Siklus

Graf G disebut graf siklus jika graf tersebut merupakan graf terhubung

yang setiap simpulnya ajasen pada dua buah simpul yang berbeda. Dengan kata

lain dalam sebuah graf siklus termuat sebuah siklus melalui semua simpulnya.

Contoh graf siklus dapat dilihat dalam Gambar 2.5 berikut ini.

Gambar 2.5 Graf Siklus

9

BAB III

VERTEX-MAGIC GRAPH

3.8 Pengertian Vertex-Magic Graph

Sebuah sisi atau simpul dari suatu graf dapat diberi label dengan

menggunakan bilangan. Label tersebut bisa dipilih sesuai dengan kehendak kita.

Namun bisa juga dibatasi bilangan tersebut berdasarkan banyaknya simpul dan

sisi.

Salah satu masalah yang sangat menarik dari pelabelan graf berdasarkan

banyaknya simpul dan sisi adalah bagaimana mengkonstruksi sebuah graf yang

termasuk vertex-magic graph.

Definisi (Cunningham, 2004: 2)

Jika sebuah graf G dengan v simpul dan e sisi diberi label 1 hingga (v + e)

demikian sehingga apabila setiap label simpul dan sisi yang insiden pada

simpul tersebut dijumlahkan menghasilkan jumlah yang sama, maka graf G

disebut vertex-magic graph. Sedangkan jumlah yang sama tersebut disebut

magic number.

Jika graf G dengan v simpul dan e sisi diberi label 1 hingga (v + e) demikian

sehingga apabila setiap label sisi dan dua buah simpul yang ajasen pada sisi

tersebut dijumlahkan menghasilkan jumlah yang sama, maka graf G disebut

edge-magic graph.

Apabila diperhatikan, dari kedua definisi di atas akan diperoleh hubungan

antara vertex-magic graph dan edge-magic graph. Hubungan tersebut adalah

edge-magic graph dapat dibentuk dari vertex-magic graph. Salah satu cara untuk

membentuk graf tersebut adalah dengan merotasikan label-label pada vertex-

magic graph searah perputaran jarum jam dengan urutan yang tetap. Perhatikan

Gambar 3.1 (a) dan Gambar 3.1 (b). Gambar 3.1 (a) merupakan vertex-magic

10

graph dengan magic number 10, sedangkan Gambar 3.1 (b) merupakan edge-

magic graph yang dibentuk dari vertex-magic graph pada Gambar 3.1 (a).

1 46

3 5

2

6 13

2 4

5

(a) (b)

Gambar 3.1 Vertex-Magic Graph dan Edge-Magic Graph

Untuk selanjutnya masalah yang dibahas adalah masalah vertex-magic

graph saja. Meskipun demikian, kita bisa memperoleh edge-magic graph dengan

menggunakan cara yang telah dijelaskan di atas.

Sebuah magic number bisa diperoleh dengan menjumlahkan label simpul

dan label sisi yang insiden pada simpul tersebut. Magic number bergantung pada

label simpul dan sisi yang diberikan. Hal ini akan memberikan dampak bahwa

magic number akan berbeda untuk pelabelan yang satu dengan pelabelan yang

lainnya. Namun apakah magic number ini mempunyai batas-batas tertentu?

Berikut kita bahas.

3.9 Batas Bawah Magic Number

Untuk mendapatkan suatu vertex-magic graph kita tidak mungkin untuk

mencoba-coba setiap bilangan sebagai magic number. Namun akan lebih mudah

apabila kita mempunyai range (daerah) magic number. Range (daerah) untuk

magic number bisa kita peroleh berdasarkan pada banyaknya simpul dan sisi pada

graf tersebut.

11

Lemma 1 (Cunningham, 2004: 3)

Jika G adalah sebuah vertex-magic graph dengan v simpul dan e sisi, maka:

kvv

evev=+

+++ sum

2)1)(( E

dengan k adalah sebuah magic number dan Esum adalah jumlah seluruh label

sisi graf G.

Bukti lemma di atas adalah sebagai berikut:

Misalkan: V adalah jumlah seluruh label simpul graf G, maka:

Esum + V = 1 + 2 + 3 + ... + (v + e)

= ( ) ( )evev++

+ 12

{jumlah (v + e) suku pertama deret aritmetika}

= ( )( )2

1+++ evev

Karena setiap sisi insiden pada dua simpul yang berbeda, maka setiap

label sisi akan dijumlahkan dengan kedua label simpul yang ajasen pada sisi

tersebut. Akibatnya diperoleh:

2Esum + V = vk

( )( )2

1+++ evev + Esum = vk

( )( )v

evev2

1+++ + vsumE

= k

Teorema 1 (Cunningham, 2004: 3)

Misalkan G sebuah graf dengan v simpul dan e sisi. Jika G adalah vertex-

magic graph, maka magic number k terbatas sehingga berlaku:

veveveeek

vevevee

2))(1()1(

2))(1()1( +++++

+≤≤+++++

Bukti teorema ini bisa dikonstruksi dari Lemma 1. Pembuktiannya adalah

sebagai berikut:

12

Dari Lemma 1 kita peroleh:

Esum = vk - ( )( )2

1+++ evev

Esum minimum akan diperoleh apabila 1 hingga e ditempatkan sebagai

label sisi. Sehingga diperoleh:

Esum ≥ 1 + 2 + 3 + ... + e

= ( )ee+1

2

= ( )2

1+ee

Sedangkan Esum maksimum akan diperoleh apabila (e + 1) hingga (v + e)

ditempatkan sebagai label sisi. Sehingga diperoleh:

Esum ≤ (v + 1) + (v + 2) + ... + (v + e)

= ∑=

+e

iiv

1

= ∑∑==

+e

i

e

iv

111

= ( )2

1++

eeve

Dengan demikian diperoleh bahwa:

( )2

1+ee ≤ Esum ≤ ( )2

1++

eeve

( )2

1+ee ≤ vk - ( )( )2

1+++ evev ≤ ( )2

1++

eeve

( )2

1+ee + ( )( )2

1+++ evev ≤ vk ≤ ( )2

1++

eeve + ( )( )2

1+++ evev

( ) ( )( )v

evevee2

11 +++++ ≤ k ≤ ( ) ( )( )v

eveveee2

11 ++++++

Berdasarkan teorema di atas diperoleh bahwa magic number terbatas

pada interval ( ) ( )( ) ( ) ( )( )⎥⎦⎤

⎢⎣⎡ +++++

++++++

veveveee

vevevee

211 ,

211 . Dengan

demikian kita bisa memilih suatu bilangan untuk dijadikan magic number pada

13

interval tersebut. Misalnya kita akan mengkonstruksi sebuah vertex-magic graph

dengan 5 buah simpul dan 5 buah sisi, maka magic number graf tersebut akan

terletak pada interval [ ]91 ,14 .

Contoh 1

Misalkan G adalah graf siklus yang termasuk vertex-magic graph dengan

V(G) = {a, b, d, f} dan E(G) = {p, q, r, s}. Tentukan interval untuk magic

number yang mungkin.

Graf G memiliki empat buah simpul dan empat buah sisi. Maka berdasarkan

Teorema 1, magic number graf G terletak pada interval [11,5; 15,5]

Apabila kita perhatikan sebuah graf siklus, maka kita peroleh bahwa

banyaknya simpul dan bayaknya sisi pada graf tersebut adalah sama. Hal ini akan

berpengaruh pada penentuan magic number baik untuk graf siklus sederhana

dengan banyak simpulnya ganjil maupun genap. Akibat-akibat tersebut

diperlihatkan dalam Akibat 1 berikut.

Akibat 1 (Cunningham, 2004: 4)

Misalkan G adalah sebuah graf siklus dengan v simpul. Jika G adalah sebuah

vertex-magic graph, maka berlaku:

ganjil jika ,23

25 vkv ≤+ , dan

genap jika ,225 vkv ≤+

Pembuktian Akibat 1 di atas adalah sebagai berikut:

Dari uraian sebelumnya, diketahui bahwa banyak simpul dan sisi pada

graf siklus adalah sama. Artinya diperoleh hubungan:

v = e

14

Substitusikan persamaan di atas pada Teorema 1, sehingga diperoleh:

k ≥ ( ) ( )v

vvvv2

2121 +++

= 2

112 ++

vv

= 23

25

+v

Jika v ganjil, maka (v + 1) habis dibagi 2. Jadi magic number minimum

untuk graf siklus dengan banyak simpulnya ganjil adalah 23

25

+v .

Bagaimana bila v genap? (v + 1) tidak habis dibagi 2 dan k haruslah

merupakan bilangan bulat. Akibatnya label 1 hingga v tidak bisa digunakan untuk

pelabelan sisi untuk memperoleh magic number yang minimum pada graf siklus

dengan banyak simpul genap.

Namun dengan menambahkan 2v pada salah satu label sisi, akan

diperoleh magic number minimum yang merupakan bilangan bulat. Akibatnya 2v

harus ditambahkan pula pada Esum, sehingga diperoleh:

Esum = (1 + 2 + ... + v) + 2v

= ( )22

1 vvv+

+

Akibatnya:

k = v

v sum12E

++

≥

( )

v

vvv

v 21

12

++

++

= 2

212 +++

vv

= 225

+v

15

Jadi magic number minimum untuk graf siklus dengan banyak simpulnya

genap adalah 225

+v . Perhatikan contoh 1 dan contoh 2 untuk melihat bagaimana

penerapan Akibat 1.

Contoh 2

Misalkan G adalah graf siklus dengan banyak simpulnya 9 buah. Jika G

merupakan vertex-magic graph, tentukan magic number minimum untuk graf

G.

Esum terkecil akan diperoleh apabila sisi-sisi graf G diberi label 1 hingga 9.

Berdasarkan Akibat 1, maka magic number minimum untuk graf G adalah

( ) 24239

25

=+ .

Contoh 3

Misalkan G adalah graf siklus dengan banyak sisinya 4 buah. Bagaimana

kombinasi pelabelan simpul graf G untuk memperoleh vertex-magic graph

dengan magic number minimum?

Dimulai dengan menempatkan 1 hingga 4 sebagai label sisi graf G, maka

diperoleh Esum = 1 + 2 + 3 + 4 = 10. Perhatikan bahwa Esum tidak habis dibagi

dengan 4, sehingga Esum harus ditambah 2 agar bisa habis dibagi 4, karena

bilangan terdekat setelah 10 yang habis dibagi 4 adalah 12. Akibatnya Esum =

1 + 2 + 3 + 6. Jadi salah satu kombinasi pelabelan sisi graf G adalah {1, 2, 3,

6} agar diperoleh magic number yang minimum.

3.10 Batas Atas Magic Number

Pada uraian sebelumnya kita telah mengupas masalah batas bawah magic

number suatu vertex-magic graph. Karena suatu vertex-magic graph diberi label

dari 1 hingga (v + e), maka vertex-magic graph akan mempunyai magic number

maksimum. Bagaimana mengatur kombinasi label yang mungkin sehingga

diperoleh magic number maksimum? Berikut penjelasannya.

16

Akibat 2 (Cunningham, 2004: 6)

Misalkan G adalah graf dengan v simpul. Jika G merupakan graf vertex-

magic graph, maka magic number k terbatas sehingga berlaku:

ganjil jika , 23

27 vvk +≤ , dan

genapjika ,127 v vk +≤

Hampir serupa dengan pembuktian Akibat 1, Akibat 2 dapat dibuktikan

sebagai berikut:

Magic number akan maksimum apabila kita menempatkan (v + 1) hingga 2v

sebagai label sisi. Akibatnya diperoleh:

Esum = ∑=

+v

i

iv1

= ∑∑==

+v

i

v

i

iv11

= ( )2

12 ++

vvv

= ( )2

13 +vv

Perhatikan juga bahwa:

k = v

v sum12E

++ , maka

k ≤

( )

v

vv

v 213

12

+

++

= ( )v

vvv2

1312 +++

= 2

113 +++

vv

= 23

27

+v

17

Seperti pada masalah batas bawah magic number, apabila v ganjil, yakni

banyak simpul graf G ganjil, maka (v + 1) habis dibagi 2. Jadi magic number

maksimum yang mungkin untuk suatu graf siklus G dengan banyak simpul ganjil

adalah 23

27

+v . Bagaimana magic number maksimum untuk graf siklus G apabila

banyak simpulnya genap?

Apabila v genap, maka (v + 1) tidak habis dibagi 2. Karena tidak boleh

ada label sisi yang lebih dari 2v, maka salah satu alternatif untuk mendapatkan

magic number maksimum adalah dengan mengurangkan label sisi tersebut dengan

2v . Akibatnya Esum harus dikurangi pula dengan

2v , sehingga diperoleh:

Esum = ( )22

13 vvv−

+

= ( )23vv

= 2

3 2v

Akibatnya:

k = v

v sum12E

++

≤ v

v

v 23

12

2

++

= 2312 vv ++

= 127

+v

Jadi magic number maksimum yang mungkin untuk graf siklus G dengan

banyak simpul genap adalah 127

+v . Perhatikan Contoh 3 dan Contoh 4 berikut

untuk melihat bagaimana penerapan Akibat 2.

18

Contoh 4

Misalkan G graf siklus dengan banyak sisinya 7 buah. Jika graf G termasuk

vertex-magic graph, tentukan magic number maksimum graf G.

Magic number akan maksimum apabila bilangan 8 hingga 14 kita tempatkan

sebagai label sisi. Berdasarkan Akibat 2, maka magic number maksimum graf

G tersebut adalah ( ) 26 237

27

=+ .

Contoh 5

Misalkan G adalah graf siklus dengan banyak simpul 4 buah. Bagaimanakah

pelabelan sisi graf G agar termasuk vertex-magic graph yang mempunyai

magic number maksimum?

Karena bilangan 5 hingga 8 ditempatkan sebagai label sisi graf G agar

diperoleh magic number maksimum, maka Esum = 5 + 6 + 7 + 8 = 26. Namun

Esum tersebut tidak habis dibagi 4. Kelipatan 4 terbesar yang lebih kecil dari

26 adalah 24. Jadi Esum dikurangi 2, maka salah satu label sisi graf G harus

dikurangi 2. Salah satu pelabelan sisi graf G dengan magic number

maksimum adalah {3, 6, 7, 8}.

Untuk selanjutnya, fokus pembahasan dibatasi hanya pada pelabelan graf

siklus yang banyak simpulnya ganjil saja. Pelabelan graf siklus yang mempunyai

banyak simpul genap tidak akan dibahas. Selain itu, pelabelan graf siklus yang

dimaksud dalam makalah ini adalah pelabelan graf siklus untuk mengkonstruksi

vertex-magic graph.

3.11 Pelabelan Graf Siklus dengan Banyak Simpul Ganjil dan Magic Number Maksimum

Pada uraian di atas telah dibahas batas atas dan batas bawah suatu magic

number dari graf siklus yang termasuk vertex-magic graph, baik untuk graf siklus

yang mempunyai banyak simpul ganjil maupun yang genap. Sedangkan pada

uraian berikutnya kita akan membahas pemberian label graf siklus yang

mempunyai banyak simpul ganjil saja. Graf siklus yang mempunyai banyak

19

simpul ganjil mempunyai batas bawah magic number 23

25

+≥ vk dan batas atas

magic number 23

27

+≤ vk .

Magic number maksimum akan diperoleh apabila kita menempatkan

(v+1) hingga 2v sebagai label sisi graf tersebut. Dengan kata lain kita

menempatkan 1 hingga v sebagai label simpul.

Teorema 2 (Cunningham, 2004: 8)

Misalkan G adalah sebuah graf siklus dengan v simpul dan v ganjil. Terdapat

pelabelan vertex-magic graph dengan bilangan 1 hingga v diletakkan pada

simpul dan sebuah magic number 23

27

+v sebagai batas atas untuk magic

number.

1

2v

2

3

4

5

6

v (3/2) ½v +

(3/2) - (½)v

2 - 1v (3/2) - (3/2)v

2 - 2v

Gambar 3.2 Label Graf Siklus dengan Banyak Simpul Ganjil

dan Magic Number Maksimum

Teorema 2 di atas menegaskan bahwa pada graf siklus dengan banyak

simpulnya ganjil terdapat suatu pelabelan untuk magic number maksimum dengan

bilangan 1 hingga v ditempatkan sebagai label simpul. Teorema tersebut dapat

kita buktikan sebagai berikut:

Simpul graf G diberi label 1 hingga v secara berurutan searah perputaran

jarum jam (Gambar 3.2). Sebuah sisi kita sebut di sebelah kanan suatu simpul

apabila sisi ini ajasen dengan simpul tersebut dan sisi ini mempunyai orientasi

20

negatif (berlawanan arah dengan perputaran jarum jam) terhadap simpul tersebut.

Selain itu, sebuah sisi disebut berada di sebelah kiri suatu simpul apabila sisi ini

ajasen dengan simpul tersebut dan sisi ini mempunyai orientasi positif (searah

perputaran jarum jam) terhadap simpul tersebut. Aturan ini akan sangat penting

untuk diingat, sebab akan berpengaruh pada penentuan label suatu sisi graf G

yang akan bergantung pada letak suatu simpul graf G.

Pelabelan graf G dimulai dengan memberikan label simpul dengan 1

hingga v. Kemudian dilanjutkan dengan pemberian label sisi yang terletak di

sebelah kanan simpul yang berlabel 1. Label sisi dimulai dengan 2v yang

kemudian berkurang sesuai dengan label simpul yang bersesuaian. Pelabelan sisi

graf G mengikuti aturan yang tertera dalam tabel berikut:

Tabel 3.1 Aturan Pelabelan Sisi Graf Siklus

dengan Banyak Simpul Ganjil dan Magic Number Maksimum

Deskripsi kasus Label simpul Label sisi kiri Label sisi kanan

Setiap simpul yang

berlainan dimulai

dengan 1

2i + 1

i = 0, ... , 2

1−v iv −+

21

23 2v – i

Setiap simpul yang

berlainan dimulai

dengan 2

2i + 2

i = 0, ... , 12

1−

−v 2v – i iv −−

21

23

Sumber: Cunningham, vertex-magic

Pada kasus pertama, graf G mempunyai magic number berikut:

( ) ( )23

272

21

2312 +=−+⎟

⎠⎞

⎜⎝⎛ −+++ vivivi .

Sedangkan pada kasus kedua, graf G mempunyai magic number di bawah ini:

( ) ( )23

27

21

23222 +=⎟

⎠⎞

⎜⎝⎛ −−+−++ vivivi .

21

Gambar 3.3 dan Gambar 3.4 berikut ini memperlihatkan bagaimana

pelabelan graf siklus yang mempunyai banyak simpul ganjil dengan magic

number maksimum.

4 23

5 6

1

Gambar 3.3 Graf Siklus dengan 3 Simpul dan Magic Number 12

2

1

34

5

8

6

9

10

7

Gambar 3.4

Graf Siklus dengan 5 Simpul dan Magic Number 19

3.12 Pelabelan Graf Siklus dengan Banyak Simpul Ganjil dan Magic Number Minimum

Bagaimana pelabelan graf siklus yang mempunyai banyak simpul ganjil

dan Magic Number minimum? Magic Number minimum akan diperoleh manakala

kita menempatkan (v + 1) hingga 2v sebagai label simpul. Dengan kata lain kita

akan mengatur label-label sisi sedemikian hingga kita peroleh vertex-magic graph

dengan magic number minimum.

22

Teorema 3 (Cunningham, 2004: 10)

Misalkan G adalah sebuah graf siklus dengan v simpul dan v ganjil. Terdapat

pelabelan pada vertex-magic graph dengan (v + 1) hingga 2v ditempatkan

pada simpul dan magic number 23

25

+v adalah batas bawah untuk magic

number. v + 12v

v + 2

v + 3

v + 4

v + 5

v + 6

v

(½) (½)v +

(½) - (½)v

v - 1(½) - (3/2)v

v - 2

Gambar 3.5 Label Graf Siklus dengan Banyak Simpul Ganjil

dan Magic Number Minimum

Ide yang sama seperti pada pelabelan graf siklus dengan magic number

maksimum di atas, dapat kita gunakan untuk menentukan pelabelan graf siklus

dengan magic number minimum. Untuk mendapatkan magic number minimum

kita harus menempatkan angka (v + 1) hingga 2v sebagai label simpul. Dengan

kata kata lain kita hanyalah membuat kombinasi label untuk sisi dengan bilangan

1 hingga v.

Sisi yang pertama kali diberi label adalah sisi yang berada di sebelah

kanan simpul yang mempunyai label (v + 1). Label yang diberikan pada sisi

tersebut adalah v. Kemudian sisi yang lainnya diberi label berdasarkan label

simpul yang bersesuaian. Pemberian label sisi ini mengikuti aturan yang tertera

dalam tabel berikut ini:

23

Tabel 3.2 Aturan Pelabelan Sisi Graf Siklus

dengan Banyak Simpul Ganjil dan Magic Number Minimum

Deskripsi kasus Label simpul Label sisi kiri Label sisi kanan

Setiap simpul yang

berlainan dimulai

dengan (v + 1)

v + 2i + 1

i = 0, ... , 2

1−v 22

21

2iv

−+ v – i

Setiap simpul yang

berlainan dimulai

dengan (v + 2)

v + 2i + 2

i = 0, ... , 12

1−

−v v – i

22

21

2iv

−−

Sumber: Cunningham, vertex-magic

Pada kasus pertama, graf G mempunyai magic number berikut:

( ) ( )23

25

22

21

212 +=−+⎟

⎠⎞

⎜⎝⎛ −++++ viviviv

Sedangkan pada kasus kedua, graf G mempunyai magic number yang sama

seperti pada kasus pertama, yaitu:

( ) ( )23

25

22

21

222 +=⎟

⎠⎞

⎜⎝⎛ −−+−+++ viviviv

Gambar 3.6 dan Gambar 3.7 berikut ini memperlihatkan bagaimana

pelabelan graf siklus yang mempunyai banyak simpul ganjil dan magic number

maksimum.

1 56

2 3

4

Gambar 3.6

Graf Siklus dengan 3 Simpul dan Magic Number 9

24

7

6

89

10

3

1

4

5

2

Gambar 3.7 Graf Siklus dengan 5 Simpul dan Magic Number 14

Selain dengan mengatur penempatan label 1 hingga v sebagai label sisi

atau sebagai label simpul, kita juga bisa menempatkan bilangan ganjil atau

bilangan genap antara 1 hingga 2v sebagai label simpul. Bagaimana pelabelan

tersebut dan bagaimana magic number yang diperoleh? Berikut akan disajikan

uraiannya.

3.13 Pelabelan Graf Siklus dengan Banyak Simpul Ganjil dan Bilangan Ganjil sebagai Label Simpul

Selain dengan menggunakan cara pelabelan seperti di atas, kita bisa

menempatkan bilangan ganjil mulai dari 1 hingga (2v – 1) sebagai label simpul.

Dengan kata lain kita akan mengatur penempatan bilangan genap antara 2 hingga

2v sebagai label sisi.

Teorema 4 (Cunningham, 2004: 16)

Misalkan G adalah sebuah graf siklus dengan v simpul dan v ganjil. Terdapat

sebuah pelabelan pada vertex-magic graph dengan bilangan ganjil antara 1

hingga (2v – 1) ditempatkan pada simpul dan magic number 3v + 2

25

1

3

5

79

11

2 - 1vv + 1

2v

v - 1

2 - 2v

v - 3

2 - 4v

Gambar 3.8 Label Graf Siklus dengan Banyak Simpul Ganjil

dan Bilangan Ganjil sebagai Label Simpul

Pada pelabelan kali ini, kita akan menempatkan bilangan ganjil antara 1

hingga (2v – 1) secara berurutan sebagai label simpul graf G searah perputaran

jarum jam. Kita akan mengatur penempatan bilangan genap antara 2 hingga 2v

sebagai label sisi graf G sehingga kita peroleh sebuah vertex-magic graph.

Dimulai dengan menempatkan 2v sebagai label sisi di sebelah kanan simpul yang

berlabel 1, kemudian memberikan label berikutnya searah perputaran jarum jam

pada sisi yang lain sesuai dengan label simpul yang bersesuaian. Pemberian label

sisi dengan angka genap di atas mengikuti aturan pelabelan pada tabel berikut ini:

Tabel 3.3 Aturan Pelabelan Sisi Graf Siklus dengan Banyak Simpul Ganjil

dan Bilangan Ganjil sebagai Label Simpul

Deskripsi kasus Label simpul Label sisi kiri Label sisi kanan

Setiap simpul yang

berlainan dimulai

dengan 1

4i + 1

i = 0, ... , 2

1−v v + 1 – 2i 2v – 2i

Setiap simpul yang

berlainan dimulai

dengan 3

4i + 3

i = 0, ... , 12

1−

−v 2v – 2i v – 1 – 2i

Sumber: Cunningham, vertex-magic

26

Pada kasus pertama, kita memperoleh magic number berikut ini:

( ) ( ) ( ) 23222114 +=−+−+++ vivivi

Sedangkan pada kasus kedua, diperoleh magic number yang sama seperti pada

kasus pertama, yaitu:

( ) ( ) ( ) 23212234 +=+−+−++ vivivi

Perhatikan Gambar 3.9 dan Gambar 3.10 untuk melihat pelabelan graf

siklus dengan bilangan ganjil sebagai label simpulnya.

2 35

4 6

1

Gambar 3.9 Graf Siklus dengan 3 Simpul dan Magic Number 11

3

1

57

9

6

2

8

10

4

Gambar 3.10

Graf Siklus dengan 5 Simpul dan Magic Number 17

Pada uraian di atas kita telah melihat pelabelan graf siklus dengan

menempatkan bilangan ganjil sebagai label simpul sehingga diperoleh vertex-

magic graph dengan melakukan pengaturan bilangan genap sebagai label sisinya.

Bagaimana apabila bilangan genap ditempatkan sebagai label simpul? Bagaimana

dengan magic number yang diperoleh? Berikut ini disajikan uraiannya.

27

3.14 Pelabelan Graf Siklus dengan Banyak Simpul Ganjil dan Bilangan Genap sebagai Label Simpul

Pada uraian di atas kita telah membahas pelabelan graf siklus dengan

menempatkan bilangan ganjil sebagai label simpul. Pada pelabelan kali terakhir

ini, kita akan membahas bagaimana pelabelan graf siklus dengan menempatkan

bilangan genap sebagai label simpulnya. Dengan kata lain, kita akan mengatur

penempatan bilangan ganjil antara 1 hingga (2v – 1) sebagai label sisi supaya

diperoleh vertex-magic graph.

Teorema 5 (Cunningham, 2004: 18)

Misalkan G adalah sebuah graf siklus dengan v simpul dan v ganjil. Terdapat

sebuah pelabelan vertex-magic graph dengan bilangan genap antara 2 hingga

2v ditempatkan pada simpul dan magic number 3v + 1.

2

4

6

810

12

2v 2 - 1v

v - 2

2 - 3v

v - 4

2 - 5v

v

Gambar 3.11 Label Graf Siklus dengan Banyak Simpul Ganjil

dan Bilangan Genap sebagai Label Simpul

Teknik yang serupa seperti pada pelabelan graf siklus dengan bilangan

ganjil sebagai label simpul, dapat kita gunakan untuk melakukan pelabelan graf

dengan bilangan genap sebagai label sisinya. Bilangan genap antara 2 hingga 2v

ditempatkan secara berurutan searah perputaran jarum jam sebagai label sisi.

Kemudian kita mengatur kombinasi bilangan ganjil antara 1 hingga (2v – 1)

sebagai label sisi. Dimulai dengan memberikan label (2v – 1) pada sisi yang

28

berada di sebelah kanan simpul yang berlabel 2, kemudian memberikan label pada

sisi yang lainnya yang terus berkurang hingga 1 berdasarkan label simpul yang

bersesuaian. Aturan pemberian label pada sisi graf tersebut tertera dalam tabel

berikut:

Tabel 3.4 Aturan Pelabelan Sisi Graf Siklus dengan Banyak Simpul Ganjil

dan Bilangan Genap sebagai Label Simpul

Deskripsi kasus Label simpul Label sisi kiri Label sisi kanan

Setiap simpul yang

berlainan dimulai

dengan 2

4i + 2

i = 0, ... , 2

1−v v – 2i 2v – 1 – 2i

Setiap simpul yang

berlainan dimulai

dengan 4

4i + 4

i = 0, ... , 12

1−

−v 2v – 1 – 2i v – 2i – 2

Sumber: Cunningham, vertex-magic

Pada kasus pertama, magic number graf tersebut adalah:

( ) ( ) ( ) 13212224 +=−−+−++ vivivi

Sedangkan pada kasus kedua kita memperoleh magic number berikut:

( ) ( ) ( ) 132221244 +=−−+−−++ vivivi

Untuk melihat pelabelan graf siklus dengan bilangan genap sebagai label

simpulnya, perhatikan Gambar 3.12 dan Gambar 3.13 berikut ini.

1 46

3 5

2

Gambar 3.12

Graf Siklus dengan 3 Simpul dan Magic Number 10

29

4

2

68

10

5

1

7

9

3

Gambar 3.13

Graf Siklus dengan 5 Simpul dan Magic Number 16

Demikian uraian pelabelan graf siklus untuk mengkonstruksi vertex-

magic graph. Uraian di atas hanyalah beberapa teknik pelabelan graf, masih

banyak lagi teknik-teknik yang lainnya yang tidak dibahas dalam makalah ini.

3.15 Temuan

Berdasarkan uraian yang telah dijelaskan sebelumnya, dapat

digeneralisasi sebagai berikut:

Konjektur

Sebuah graf G dengan v simpul dan e sisi dapat diberi label k hingga (k + v

+ e) demikian sehingga apabila setiap label simpul dan sisi yang insiden

pada simpul tersebut dijumlahkan menghasilkan jumlah yang sama, maka

graf G disebut vertex-magic graph. Sedangkan jumlah yang sama tersebut

disebut magic number.

Sebuah graf G dengan v simpul dan e sisi dapat diberi label k hingga (k + v +

e) demikian sehingga apabila setiap label sisi dan dua buah simpul yang

ajasen pada sisi tersebut dijumlahkan menghasilkan jumlah yang sama, maka

graf G disebut edge-magic graph.

30

Demikian uraian pelabelan graf siklus untuk mengkonstruksi vertex-

magic graph. Uraian di atas hanyalah beberapa teknik pelabelan graf, masih

banyak lagi teknik-teknik yang lainnya yang tidak dibahas dalam makalah ini.

31

BAB IV

KESIMPULAN DAN SARAN

4.3 Kesimpulan

Berdasarkan uraian pada bagian sebelumnya, kita dapat menyimpulkan

beberapa hal berikut:

a. Untuk mengkonstruksi sebuah vertex-magic graph, sebuah graf siklus yang

banyak simpulnya ganjil dapat diberi label berdasarkan magic number

maksimum atau minimum.

b. Untuk mengkonstruksi sebuah vertex-magic graph, graf siklus yang banyak

simpulnya ganjil dapat diberi label dengan bilangan genap atau ganjil sebagai

label simpulnya.

c. Magic number yang diperoleh, akan bergantung pada teknik pelabelan graf

siklus yang dilakukan, yaitu:

i. Untuk pelabelan graf siklus berdasarkan magic number maksimum,

maka diperoleh magic number 23

27

+v ;

ii. Untuk pelabelan graf siklus berdasarkan magic number minimum,

maka diperoleh magic number 23

25

+v ;

iii. Untuk pelabelan graf siklus berdasarkan bilangan ganjil sebagai label

simpulnya, maka diperoleh magic number 3v + 2;

iv. Untuk pelabelan graf siklus berdasarkan bilangan genap sebagai label

simpulnya, maka diperoleh magic number 3v + 1.

32

4.4 Saran

Dalam kesempatan ini, penyusun ingin memberikan beberapa saran

kepada pembaca sebagai berikut:

a. Dalam makalah ini hanya dibahas tentang pelabelan graf siklus sederhana

yang banyak simpulnya ganjil berdasarkan magic number maksimum atau

minimum dan penempatan bilangan ganjil atau bilangan genap sebagai label

simpul. Masih banyak teknik pelabelan graf siklus sederhana dengan banyak

simpul ganjil yang tidak tercakup dalam makalah ini. Oleh karena itu,

pembaca disarankan agar tidak terpaku pada teknik yang dijelaskan pada

makalah ini saja.

b. Makalah ini hanya membahas teknik pelabelan graf siklus sederhana untuk

mengkonstruksi vertex-magic graph yang banyak simpulnya ganjil saja. Oleh

karena itu, pembaca disarankan untuk mempelajari teknik pelabelan graf

siklus yang banyak simpulnya genap. Teknik pelabelan ini sedikit berbeda

dengan teknik pelabelan graf siklus yang banyak simpulnya ganjil.

c. Dalam makalah ini hanya dibahas teknik pelabelan untuk graf siklus

sederhana saja, jenis graf lainnya seperti graf bipartit, graf euler, dan graf

hamilton memerlukan teknik pelabelan yang berbeda. Pembaca dapat

memfokuskan penelitiannya pada teknik pelabelan graf tersebut.

33

DAFTAR PUSTAKA

Cunningham, D. 2004. Vertex-Magic. [Online]. Tersedia: http://math.furman.edu/~woodard/fuejum/content/2004/paper1_2004.pdf. [30 September 2006]

Munir, R. 2003. Matematika Diskrit. Bandung: Informatika.

Kusumah, Y. S. 1998. Matematika Diskrit. Bandung: IKIP Bandung Press

Sutarno, H, Nanang Priatna, dan Nurjanah. 2005. Matematika Diskrit. Malang: Universitas Negeri Malang.

34

BIOGRAFI

JAENUDIN, lahir di Garut pada tanggal 18 Desember 1985.

Menyelesaikan pendidikan Sekolah Dasar di SDN Tenjolaut

(1992 – 1998), kemudian melanjutkan ke SMPN 1 Bungbulang

(1998 – 2001). Lulus dari SMAN 1 Bungbulang pada tahun

2004, mendapat kesempatan belajar ke Universitas Pendidikan

Indonesia (UPI) dengan mengambil Jurusan Pendidikan

Matematika. Setelah empat tahun belajar di UPI, lulus tahun 2008 dengan yudisium

Cum Laude. Saat ini aktif mengajar di sebuah lembaga yang melayani pendidikan

bagi anak-anak SD dan SMP. Selain aktif sebagai konsultan pendidikan, juga aktif

dalam bidang webmaster, pemrograman Macromedia Flash, serta database. Saat ini,

sedang menunggu kesempatan untuk melanjutkan studi ke jenjang yang lebih tinggi.

Bagi berkepentingan, bisa menghubungi e-mail: sydney_nineteen@yahoo.com