pelabelan dan pembentukan graf middle pada …lib.unnes.ac.id/19104/1/4111409019.pdf · 1 pelabelan...

1

PELABELAN DAN PEMBENTUKAN GRAF

MIDDLE PADA BEBERAPA GRAF KHUSUS

skripsi

disajikan sebagai salah satu syarat

untuk memperoleh gelar Sarjana Sains

Program Studi Matematika

oleh

Meliana Deta Anggraeni

4111409019

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS NEGERI SEMARANG

2013

ii

ii

PENGESAHAN

Skripsi yang berjudul

Pelabelan dan Pembentukan Graf Middle pada Beberapa Graf

Khusus

disusun oleh :


NIM. 4111409019

Telah dipertahankan di hadapan sidang Panitia Ujian Skripsi FMIPA UNNES

pada tanggal 02 Agustus 2013.

Panitia :

Ketua Sekretaris

Prof. Dr.Wiyanto, M.Si. Drs Arief Agoestanto, M.Si.

NIP. 196310121988031001 NIP. 196807221993031005

Penguji

Dr. Rochmad, M.Si

NIP. 195711161987011001

Anggota Penguji / Anggota Penguji /

Pembimbing Utama Pembimbing Pendamping

Dr. Mulyono, M.Si Drs. Amin Suyitno, M.Pd

NIP. 19700902 199702 1 001 NIP. 19520604 197612 1 001

iii

iii

PERNYATAAN

Saya menyatakan bahwa skripsi ini bebas plagiat, dan apabila di kemudian hari

terbukti terdapat plagiat dalam skripsi ini, maka saya bersedia menerima sanksi

sesuai ketentuan peraturan perundang-undangan.

Semarang, Agustus 2013


NIM. 4111409019

iv

iv

MOTTO DAN PERSEMBAHAN

MOTTO o Mengetahui kekurangan diri adalah tangga untuk menggapai cita-

cita, berusaha terus untuk mengisi kekurangan adalah keberanian luar biasa.

o Awali segala sesuatu dengan ‘BASMALLAH’. o Hanya dengan sabar, berusaha, dan berdoa, keberhasilan akan

terwujud.

PERSEMBAHAN

Persembahan ini saya tujukan untuk :

1. Bapak dan Ibu, yang tak hentinya melantunkan bait-bait doanya untukku dan selalu menantikan keberhasilanku.

2. Adik dan kekasih tersayang. 3. Almamaterku.

v

v

KATA PENGANTAR

Puji syukur penulis panjatkan ke hadirat Allah SWT yang telah

melimpahkan rahmat dan hidayah-Nya, sehingga penulis dapat menyelesaikan

skripsi dengan judul “PELABELAN DAN PEMBENTUKAN GRAF

MIDDLE PADA BEBERAPA GRAF KHUSUS” sebagai salah satu syarat

untuk menyelesaikan jenjang studi sarjana pada Fakultas Matematika dan Ilmu

Pengetahuan Alam Universitas Negeri Semarang.

Penulis menyadari bahwa terselesainya penulisan skripsi ini berkat

bimbingan, pengarahan, dan bantuan dari berbagai pihak baik berupa moral

maupun materiil. Oleh karena itu pada kesempatan ini, penulis akan

menyampaikan rasa hormat, serta terima kasih kepada :

1. Prof. Dr. Fathur Rokhman, M.Hum., Rektor Universitas Negeri Semarang,

2. Prof. Dr. Wiyanto, M.Si., Dekan Fakultas Matematika dan Ilmu Pengetahuan

Alam,

3. Drs. Arief Agoestanto, M.Si., Ketua Jurusan Matematika Fakultas Matematika

dan Ilmu Pengetahuan Alam Universitas Negeri Semarang,

4. Dr. Mulyono, M.Si., dosen pembimbing I yang telah memberikan bimbingan,

masukan, motivasi, semangat dalam pembuatan skripsi ini,

5. Drs. Amin Suyitno, M.Pd., dosen pembimbing II yang telah memberikan

bimbingan, masukan, motivasi, semangat dalam pembuatan skripsi ini,

6. Seluruh Dosen Matematika yang telah membimbing dan memberikan ilmunya

kepada penulis,

vi

vi

7. Bapak, Ibu, dan adik tercinta yang telah memberikan dorongan, dukungan dan

doa kepada penulis dalam penyusunan skripsi ini,

8. Teman-teman Matematika 2009, terima kasih atas kebersamaanya,

9. Semua pihak yang mendukung dan membantu proses terselesaikannya skripsi

ini yang tidak dapat penulis sebutkan satu per satu.

Semoga Allah SWT memberi rahmat serta hidayah-Nya pada kita semua baik

di dunia maupun di akhirat. Penulis sadar bahwa kesempurnaan hanya milik Allah

Yang Maha Kuasa, meskipun begitu penulis berharap skripsi ini dapat memberi

manfaat bagi Almamater pada khususnya serta pembaca pada umumnya.

Semarang, Agustus 2013

Penulis

vii

vii

ABSTRAK

Anggraeni, M. D. 2013. Pelabelan dan Pembentukan Graf Middle pada

Beberapa Graf Khusus. Skripsi. Jurusan Matematika, Fakultas Matematika dan

Ilmu Pengetahuan Alam, Universitas Negeri Semarang. Pembimbing I: Dr.

Mulyono, M.Si dan Pembimbing II: Drs. Amin Suyitno, M.Pd.

Kata Kunci: Graf khusus; graf middle; pelabelan .

Pelabelan dari suatu graf adalah suatu pemetaan yang membawa setiap

elemen graf yaitu himpunan sisi (edge) atau himpunan titik (vertex) ke bilangan-

bilangan bulat positif, yang disebut label. Pelabelan adalah pelabelan di

mana dalam suatu graf jika terdapat dua titik dengan jarak satu maka harus

memiliki label dengan selisih minimal 3, jika terdapat dua titik dengan jarak dua

maka harus memiliki label dengan selisih minimal 2, dan jika terdapat dua

titik dengan jarak tiga maka harus memiliki label dengan selisih minimal 1.

Permasalahan dalam skripsi ini adalah bagaimana menentukan pelabelan

dan menentukan graf middle pada graf path , graf sikel , graf

bintang .

Penelitian ini merupakan penelitian studi pustaka dengan langkah sebagai

berikut, yaitu (1) mempelajari dan mengkaji tentang pelabelan pada graf

path , graf sikel , dan graf bintang . (2) Mempelajari dan mengkaji tentang

pembentukan graf middle pada graf path , graf sikel , graf bintang dan

pelabelan nya.

Untuk menentukan hasil pelabelan pada graf path , graf sikel

, dan graf bintang , terlebih dahulu membuktikan teorema-teorema yang ada.

Penelitian ini memberikan hasil dan kesimpulan bahwa

.

.

viii

viii

DAFTAR ISI

Halaman

HALAMAN JUDUL .............................................................................................. i

HALAMAN PENGESAHAN ............................................................................... ii

PERNYATAAN ................................................................................................... iii

MOTTO DAN PERSEMBAHAN ....................................................................... iv

KATA PENGANTAR .......................................................................................... v

ABSTRAK .......................................................................................................... vii

DAFTAR ISI ...................................................................................................... viii

DAFTAR GAMBAR ............................................................................................ x

DAFTAR SIMBOL ............................................................................................ xiii

BAB 1. PENDAHULUAN ................................................................................... 1

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

1.2 Rumusan Masalah ....................................................................................... 2

1.3 Batasan Masalah.......................................................................................... 2

1.4 Tujuan Penulisan ......................................................................................... 3

1.5 Manfaat Penulisan ...................................................................................... 3

1.6 Sistematika Penyusunan Skripsi ................................................................. 3

BAB 2. LANDASAN TEORI ............................................................................... 6

2.1 Graf ............................................................................................................. 6

2.2 Jenis-Jenis Graf ......................................................................................... 12

2.3 Fungsi (Pemetaan) ..................................................................................... 14

ix

ix

2.4 Pelabelan Graf ........................................................................................... 15

BAB 3. METODE PENELITIAN....................................................................... 18

3.1 Menentukan Masalah ................................................................................ 18

3.2 Perumusan Masalah .................................................................................. 18

3.3 Metode Pengambilan Data........................................................................ 19

3.4 Analisis dan Pemecahan Masalah ............................................................. 19

3.5 Penarikan Kesimpulan .............................................................................. 20

BAB 4. HASIL PENELITIAN DAN PEMBAHASAN ..................................... 21

4.1 Pelabelan .................................................................................. 21

4.2 Pelabelan pada Graf Khusus ..................................................... 23

4.2.1 Pelabelan pada Graf Path ........................................... 23

4.2.2 Pelabelan pada Graf Sikel .......................................... 29

4.2.3 Pelabelan pada Graf Bintang ..................................... 43

4.3 Graf Middle............................................................................................... 46

4.4 Pembentukan Graf Middle pada Graf Khusus .......................................... 47

4.4.1 Graf Middle dari Graf Path ......................................................... 47

4.4.2 Graf Middle dari Graf Sikel ........................................................ 56

4.4.3 Graf Middle dari Graf Bintang ................................................... 63

BAB 5. PENUTUP ............................................................................................. 68

5.1 Kesimpulan ............................................................................................... 68

5.2 Saran .......................................................................................................... 69

DAFTAR PUSTAKA ......................................................................................... 70

x

x

DAFTAR GAMBAR

Halaman

Gambar 2.1 Graf dengan 5 titik dan 6 sisi ............................................................ 6

Gambar 2.2 Jalan , Jejak, Lintasan, dan Siklus dalam suatu Graf ........................ 9

Gambar 2.3 Graf bagian dari yang dibangun oleh ....... 10

Gambar 2.4 Graf terhubung dan Graf tidak terhubung ............................. 11

Gambar 2.5 Graf tidak terhubung dengan komponen, yaitu ........... 11

Gambar 2.6 Graf Path ..................................................................................... 12

Gambar 2.7 Graf Sikel ................................................................................... 12

Gambar 2.8 Graf Lengkap ............................................................................. 13

Gambar 2.9 Graf Bintang ............................................................................... 14

Gambar 2.10 Pelabelan Titik pada Graf .......................................................... 16

Gambar 2.11 Pelabelan Sisi pada Graf ............................................................ 16

Gambar 2.12 Pelabelan Total pada Graf ......................................................... 17

Gambar 4.1 Graf ............................................................................................ 23

Gambar 4.2 Graf ............................................................................................ 23

Gambar 4.3 Pelabelan pada Graf Path dengan ......................... 27





Gambar 4.8 Pelabelan pad Graf Path dengan ........................... 28

xi

xi


Gambar 4.10 Pelabelan pada Graf Path ......................................... 29

Gambar 4.11 Pelabelan pada Graf Sikel dengan .............. 31



Gambar 4.14 Pelabelan pada Graf Sikel dengan ........... 35

Gambar 4.15 Pelabelan pada Graf Sikel dengan , jika maka

.................................................................................... 41

Gambar 4.16 Pelabelan pada Graf Sikel dengan , jika maka

..................................................................................... 42

Gambar 4.17 Pelabelan pada Graf Sikel dengan , jika

maka ............................................................................. 42

Gambar 4.18 Pelabelan pada Graf Sikel dengan , jika ,

maka ........................................................................... 43

Gambar 4.19 Pelabelan pada Graf Bipartit Lengkap ................... 45

Gambar 4.20 Graf Bintang dan pelabelan pada Graf Bintang ... 47

Gambar 4.21 Graf dan Graf ................................................................. 50


Gambar 4.23 Graf dan Pelabelan pada Graf ................ 51




Gambar 4.27 Graf dan Pelabelan pada Graf ................. 52

xii

xii




Gambar 4.31 Pelabelan pada Graf ........................................... 54

Gambar 4.32 Graf dan Graf ................................................................ 55





Gambar 4.37 Pelabelan pada Graf .......................................... 59

Gambar 4.38 Graf dan Graf ............................................................... 60


Gambar 4.40 Graf dan Graf ............................................................... 62


Gambar 4.42 Graf dan Graf .............................................................. 64




xiii

xiii

DAFTAR SIMBOL

: suatu graf

: graf dengan himpunan titik dan himpunan sisi

: himpunan titik dari graf

: himpunan sisi dari graf

: jumlah titik dari graf

: jumlah sisi dari graf

: titik ke

: sisi ke

: derajat dari titik

: derajat minimum

: derajat maksimum

: anggota dari

: sama dengan

: tidak sama dengan

: lebih besar sama dengan

: lebih kecil sama dengan

: lebih besar dari

: lebih kecil dari

: kongruen

: himpunan bagian (subset)

: label tertinggi dari suatu titik pada graf

: graf lengkap dengan titik

: graf bipartit lengkap dengan dan banyaknya titik di kedua

partisi tersebut

: graf bintang dengan titik

: graf path dengan titik

: graf sikel dengan titik

: fungsi atau pemetaan

: graf middle pada graf

: himpunan titik graf middle pada graf

: graf middle dari graf path dengan titik

: graf middle dari graf sikel dengan titik

: graf middle dari graf bintang dengan titik

1

BAB I

PENDAHULUAN

1.1 Latar Belakang

Banyaknya permasalahan dalam kehidupan sehari–hari mendorong

manusia untuk mencari solusi yang secara tidak langsung permasalahan tersebut

mendorong berkembangnya ilmu pengetahuan dan teknologi. Matematika

merupakan salah satu yang banyak memberikan alternatif dalam menyelesaikan

permasalahan di segala bidang. Salah satu cabang matematika yang dapat

menyelesaikan suatu permasalahan adalah teori graf (Clipperton dkk., 2008:1).

Teori graf pertama kali diperkenalkan oleh Leonhard Euler pada tahun

1736 ketika mencoba membuktikan kemungkinan untuk melewati empat daerah

yang terhubung dengan tujuh jembatan di atas sungai Pregel di Konigsberg, Rusia

dalam sekali waktu. Pembuktian Euler tersebut ditulis dalam karya tulisnya yang

berjudul Solution problematis ad geometrian situs pertinensi. Masalah jembatan

Konigsberg tersebut dapat dinyatakan dengan istilah graf dalam menentukan

keempat daerah itu sebagai titik (vertex) dan ketujuh jembatan sebagai sisi (edge)

yang menghubungkan pasangan titik yang sesuai (Sutarno dkk., 2003: 58).

Pelabelan dari suatu graf adalah suatu pemetaan yang membawa setiap

elemen graf yaitu himpunan sisi (edge) atau himpunan titik (vertex) ke bilangan-

bilangan bulat positif, yang disebut label (Chang, 2000). Jika suatu pelabelan

hanya menggunakan domain berupa titik maka disebut pelabelan titik, dan apabila

2

domainnya berupa himpunan sisi maka disebut pelabelan sisi. Jika domainnya

berupa himpunan titik dan sisi maka disebut pelabelan total (total labeling).

Pelabelan adalah pelabelan di mana dalam suatu graf jika terdapat

dua titik dengan jarak satu maka harus memiliki label dengan selisih

minimal 3, jika terdapat dua titik dengan jarak dua maka harus memiliki

label dengan selisih minimal 2, dan jika terdapat dua titik dengan jarak tiga

maka harus memiliki label dengan selisih minimal 1 (Lingsheit, 2009).

Adapun graf khusus yang dibahas di sini antara lain yaitu graf path , graf sikel

, dan graf bintang (Griggs, 1992: 586).

1.2 Perumusan Masalah

Berdasarkan uraikan di atas, maka permasalahan yang dapat dirumuskan

dalam penelitian ini adalah sebagai berikut.

1. Bagaimana menentukan pelabelan pada graf path , graf sikel

, dan graf bintang ?

2. Bagaimana cara menentukan graf middle dari graf path , graf sikel ,

graf bintang , dan pelabelan nya?

1.3 Pembatasan Masalah

1. Pelabelan .

2. Graf khusus yang dibahas dalam penelitian ini meliputi graf path , graf

sikel , graf bintang , dan graf middle.

3

1.4 Tujuan Penulisan

Tujuan dari penelitian ini adalah sebagai berikut.

1. Mengetahui pelabelan pada graf path , graf sikel , dan graf

bintang .

2. Mengetahui cara menentukan graf middle dari graf path , graf sikel ,

graf bintang , dan pelabelan nya .

1.5 Manfaat Penulisan

Manfaat penelitian ini diantaranya adalah sebagai berikut.

a. Bagi Penulis

Memberikan pengalaman dan pengetahuan mengenai pelabelan

dan pembentukan graf middle pada beberapa graf khusus.

b. Bagi Pembaca

Dapat dijadikan sumbang saran bagi pembaca yang akan melakukan

penelitian pelabelan .

c. Bagi Perpustakaan Jurusan Matematika

Dapat dijadikan sebagai tambahan referensi, sehingga dapat menambah

wawasan bagi mahasiswa.

1.6 Sistematika Penyusunan Skripsi

Sistematika penulisan skripsi ini secara garis besar terbagi menjadi tiga

bagian yaitu bagian awal, bagian isi, dan bagian akhir skripsi.

4

(1) Bagian awal skripsi meliputi halaman sampul, halaman judul, pernyataan

keaslian tulisan, motto dan persembahan, kata pengantar, abstrak, daftar isi,

daftar gambar, daftar tabel dan daftar lampiran.

(2) Bagian isi skripsi secara garis besar terdiri dari lima bab, adalah sebagai

berikut.

BAB I : PENDAHULUAN

Dikemukakan latar belakang, permasalahan, pembatasan masalah,

tujuan penelitian, manfaat penelitian, dan sistematika penyusunan

skripsi.

BAB 2 : LANDASAN TEORI

Dikemukakan konsep-konsep yang dijadikan landasan teori sebagai

berikut: graf dan pelabelan graf.

BAB 3 : METODE PENELITIAN

Dikemukakan metode penelitian yang berisi langkah-langkah yang

ditempuh untuk memecahkan masalah yaitu: menentukan masalah,

perumusan masalah, metode pengambilan data, analisis dan

pemecahan masalah, serta penarikan kesimpulan.

BAB 4 : HASIL PENELITIAN DAN PEMBAHASAN

Dikemukakan hasil penelitian dan pembahasan yang berisi

pembahasan dari permasalahan yang berkaitan dengan pelabelan

dan pembentukan graf middle pada graf khusus.

5

BAB 5 : PENUTUP

Bagian penutup meliputi simpulan dan saran. Simpulan merupakan

hasil pembahasan bab-bab sebelumnya yang mencerminkan hasil

penlitian. Saran berupa anjuran atau rekomendasi.

(3) Bagian akhir skripsi meliputi daftar pustaka dan lampiran-lampiran dari

pembahasan yang telah dilakukan serta yang mendukung penulisan skripsi.

6

BAB II

LANDASAN TEORI

2.1 Graf

2.1.1 Definisi

Graf adalah pasangan , di mana adalah himpunan

berhingga titik-titik (vertices) yang tak kosong dan adalah himpunan sisi

(mungkin kosong), sedemikian sehingga setiap sisi (edge) di adalah

pasangan tak berurutan dari titik-titik di . Himpunan titik dari dinotasikan

dengan , sedangkan himpunan sisi dinotasikan dengan (Budayasa,

2007: 1).

Jumlah titik dari graf disebut order graf yang dinotasikan dengan

sedangkan jumlah sisi dari graf disebut size graf yang dinotasikan

dengan . Gambar di bawah ini contoh graf dengan 5 titik dan 6 sisi.

Contoh :

Gambar 2.1 Graf dengan 5 titik dan 6 sisi

7

Dalam sebuah graf, seperti terlihat pada Gambar 2.1, dimungkinkan

adanya suatu sisi yang dikaitkan dengan pasangan . Sisi yang dua titik

ujungnya sama disebut loop/gelang. Pada Gambar 2.1, sisi merupakan sebuah

loop. Dalam sebuah graf dimungkinkan adanya lebih dari satu sisi yang dikaitkan

dengan sepasang titik. Pada Gambar 2.1, sisi dan sisi dikaitkan dengan

pasangan titik . Menurut Sutarno dkk. (2003: 60), pasangan sisi semacam

ini disebut sisi-sisi pararel/sejajar atau sisi rangkap. Sebuah graf yang tidak

memiliki loop dan tidak memiliki sisi rangkap disebut graf sederhana.

2.1.2 Definisi

Jika sebuah titik merupakan titik ujung dari suatu sisi , maka dan

disebut saling berinsidensi atau titik terkait (incident) dengan sisi

(Sutarno dkk., 2003: 60).

Contoh :

Pada Gambar 2.1 di atas, sisi dan adalah sisi-sisi yang terkait

dengan titik .

2.1.3 Definisi

Dua sisi yang tidak pararel disebut bertetangga (adjacent), bila kedua sisi

tersebut terkait dengan titik yang sama. Selain itu, dua buah titik disebut

bertetangga jika kedua titik tersebut merupakan titik-titik ujung dari sisi yang

sama (Sutarno dkk., 2003: 60).

8

Contoh :

dan dalam Gambar 2.1, merupakan dua sisi yang bertetangga.

Dalam Gambar 2.1, dan adalah dua titik yang saling bertetangga, sedangkan

titik dan merupakan dua titik yang tidak saling bertetangga.

2.1.4 Definisi

Jumlah atau banyaknya sisi yang terkait dengan suatu titik (loop

dihitung dua kali), disebut derajat (degree) dari titik tersebut dinotasikan .

Derajat suatu titik sering juga disebut valensi dari titik tersebut. Derajat minimum

dari graf dinotasikan dengan dan derajat maksimumnya dinotasikan

dengan (Siang, 2002: 205).

Contoh :

Pada Gambar 2.1, terlihat bahwa untuk setiap titik di derajat titiknya

adalah , , , . Sehingga

dan .

2.1.5 Definisi

Misalkan G adalah sebuah graf. Sebuah jalan (walk) di adalah barisan

berhingga (tak kosong) yang suku-sukunya bergantian

titik dan sisi, sedemikian sehingga dan adalah titik-titik akhir sisi , untuk

. Titik dan berturut-turut disebut titik awal dan titik akhir .

Sedangkan titik-titik disebut titik-titik internal dari . Panjang dari

jalan adalah banyaknya sisi dalam . Jika semua sisi dalam

jalan berbeda, maka disebut jejak (trail). Jika semua titik

dalam jalan juga berbeda, maka disebut sebuah lintasan (path). Sebuah

9

jalan disebut tertutup, jika titik awal dan titik akhir dari sama. Jejak tertutup

disebut sirkuit. Sirkuit yang titik awal dan titik internalnya berlainan disebut

siklus (cycle). Siklus dengan titik dinotasikan dengan (Sutarno dkk., 2003:

65).

Contoh :

Gambar 2.2 Jalan, Jejak, Lintasan, dan Siklus dalam suatu Graf

Jalan :

Jalan tertutup : .

Jejak : .

Jejak tertutup : .

Lintasan : .

Siklus : .

2.1.6 Definisi

Sebuah graf disebut graf bagian dari graf , ditulis , jika

dan . Jika dan , maka disebut

graf bagian rentang (spanning subgraf) dari (Budayasa, 2007: 5).

10

Contoh :

Gambar 2.3 Graf Bagian dari yang dibangun oleh .

Graf bagian dari yang dibangun oleh adalah sebuah graf bagian dari

yang himpunan titiknya adalah dan himpunan sisinya beranggotakan semua

sisi yang mempunyai titik-titik akhir di Pada Gambar 2.3, graf adalah graf

bagian dari graf yang dibangun oleh , sedangkan graf bagian dari

yang dibangun oleh adalah sebuah graf bagian dari yang himpunan sisinya

adalah dan himpunan titiknya beranggotakan semua titik yang terkait dengan

sisi Pada Gambar 2.3, graf adalah graf bagian dari graf yang dibangun oleh

.

2.1.7 Definisi

Sebuah graf dikatakan terhubung (connected graph) jika untuk setiap

dua titik yang berbeda terdapat sebuah lintasan yang menghubungkan kedua

titik tersebut. Sebaliknya graf disebut tidak terhubung (disconnected graph)

(Rosen, 2003: 570).

11

Contoh :

Gambar 2.4 Graf terhubung dan Graf tidak terhubung

2.1.8 Definisi

Sebuah komponen graf adalah sebuah graf bagian terhubung maksimal

(titik dan sisi) dari . Graf dikatakan graf bagian terhubung maksimal dari graf

, jika tidak ada graf bagian lain dari yang terhubung dan memuat . Jadi

setiap graf terhubung memiliki tepat satu komponen sedangkan graf tak terhubung

memiliki paling sedikit dua komponen (Budayasa, 2007: 8).

Contoh :

Gambar 2.5 Graf tidak terhubung dengan komponen, yaitu

12

2.2 Jenis-jenis Graf

2.2.1 Definisi

Graf path adalah graf sederhana yang terdiri dari lintasan tunggal. Graf

path dengan titik dinotasikan dengan . memiliki sisi (Budayasa,

2007: 6).

Contoh :

Gambar 2.6 Graf Path

2.2.2 Definisi

Graf sikel adalah graf sederhana yang terdiri dari sebuah sikel tunggal dan

setiap titiknya berderajat dua. Graf sikel dengan titik dinotasikan dengan ,

Jika titik-titik pada adalah maka sisi-sisinya adalah

. Dengan kata lain, ada sisi dari titik

terakhir, ke titik pertama, (Rosen, 2003: 548).

Contoh :

Gambar 2.7 Graf Sikel

13

2.2.3 Definisi

Misalkan adalah sebuah graf sederhana. Jika untuk

setiap pasang titik dan di terdapat sebuah sisi yang menghubungkannya,

maka disebut graf lengkap. Graf lengkap dengan titik dinotasikan dengan

(Sutarno dkk, 2003: 82).

Contoh :

Gambar 2.8 Graf Lengkap

2.2.4 Definisi

Graf Bintang adalah graf bipartit lengkap yang berbentuk . Graf

bintang memiliki titik (Huda, 2012: 32). Sebuah graf disebut graf bipartit

jika (himpunan titik dari graf ) dapat dipartisi menjadi dua himpunan

bagian dan sedemikian sehingga setiap sisi dari menghubungkan sebuah

titik di dan sebuah titik di . Dinotasikan bipartit dari (Sutarno dkk,

2003: 84).

Apabila sederhana dan bipartit dengan partisi sedemikian

sehingga setiap titik di adjacent dengan setiap titik di , maka disebut graf

14

bipartit lengkap, dinotasikan dengan dengan dan adalah banyaknya titik

di kedua partisi tersebut.

Contoh :

Gambar 2.9 Graf Bintang

2.3 Fungsi (Pemetaan)

2.3.1 Definisi

Misalkan dan merupakan himpunan tidak kosong, maka cross product

dari dua buah himpunan dan yang dinotasikan dengan adalah

himpunan semua pasangan terurut dengan dan yaitu

Contoh :

Diberikan dan , maka

dan

. Dari hasil dan didapat bahwa

.

2.3.2 Definisi

Misalkan dan adalah dua himpunan yang tidak kosong. Suatu cara

atau aturan yang memasangkan setiap elemen dari himpunan dengan tepat satu

15

elemen di himpunan disebut pemetaan dari himpunan ke himpunan .

Pemetaan dari himpunan ke himpunan diberi notasi , yaitu . Secara

umum pemetaan digolongkan menjadi tiga golongan.

2.3.3 Definisi

Pemetaan adalah pemetaan surjektif jika range dari adalah

semua elemen di , dengan kata lain jika untuk setiap terdapat

sehingga (Bartle & Sherbert, 1994:13).

2.3.4 Definisi

Menurut Bartle & Sherbert (1994:13) sebuah pemetaan

dikatakan injektif (one-one) jika dan hanya jika maka ,

untuk semua .

2.3.5 Definisi :

Jika f merupakan pemetaan yang surjektif dan sekaligus injektif maka

f disebut pemetaan bijektif (Bartle & Sherbert, 1994:13).

2.4 Pelabelan Graf

2.4.1 Definisi

Hasil penelitian Budiasti (2010) mengatakan bahwa pelabelan pada suatu

graf adalah pemetaan (fungsi) yang memasangkan unsur-unsur graf (titik atau sisi)

dengan bilangan (biasanya bilangan bulat positif). Jika domain dari pemetaan

16

adalah titik, maka pelabelan disebut pelabelan titik (vertex labeling). Jika

domainnya adalah sisi, maka disebut pelabelan sisi (edge labeling), dan jika

domainnya titik dan sisi, maka disebut pelabelan total (total labeling).

Contoh :

Diberikan graf sebagai berikut.

Didefinisikan

Gambar 2.10 Pelabelan Titik pada Graf

Contoh :


Didefinisikan .

Gambar 2.11 Pelabelan Sisi pada Graf

17

Contoh :


Didefinisikan

Gambar 2.12 Pelabelan Total pada Graf

18

BAB III

METODE PENELITIAN

Pada penelitian ini metode atau langkah-langkah yang digunakan adalah

sebagai berikut.

3.1 Menemukan Masalah

Dalam tahap ini dicari sumber pustaka dan dipilih bagian dari sumber

pustaka sebagai suatu masalah. Penulis mencari berbagai macam sumber pustaka

yang berhubungan dengan pelabelan , graf middle, dan graf khusus yang

meliputi graf path , graf sikel , dan graf bintang . Kemudian menyeleksi

untuk ditetapkan sebagai suatu masalah yang harus diselesaikan.

3.2 Merumuskan Masalah

Masalah yang ditemukan kemudian dirumuskan kedalam pertanyaan

yang harus diselesaikan yaitu:

(1) Bagaimana menentukan pelabelan pada graf path , graf sikel

, dan graf bintang .

(2) Bagaimana menentukan graf middle dari graf path , graf sikel , graf

bintang , dan pelabelan nya.

19

3.3 Metode Pengambilan Data

Pada penelitian ini metode atau langkah-langkah yang digunakan adalah

sebagai berikut.

1) Studi Pustaka

Dalam langkah ini dilakukan kajian sumber-sumber pustaka tentang

pelabelan , graf middle, dan graf khusus yang meliputi graf path

, graf sikel , dan graf bintang dengan cara mencari referensi dari

buku-buku dan jurnal yang berkaitan dengan pelabelan , graf

middle, dan graf khusus yang meliputi graf path , graf sikel , dan graf

bintang sehingga didapatkan suatu ide mengenai bahan dasar

pemecahan masalah.

2) Dokumentasi

Metode pengumpulan data dengan cara dokumentasi dilakukan penulis

dengan mengambil atau melihat langsung data-data dari internet yang ter-

update. Misalnya dengan cara mencarinya di situs www.google.com dengan

menggunakan kata kunci pelabelan , graf middle, dan graf khusus

yang meliputi graf path , graf sikel , dan graf bintang .

3.4 Analisis dan Pemecahan Masalah

Dari berbagai sumber pustaka yang sudah menjadi bahan kajian, diperoleh

suatu pemecahan masalah di atas. Selanjutnya dilakukan langkah-langkah

pemecahan masalah sebagai berikut.

20

1. Memahami definisi pelabelan .

2. Membuktikan Lemma dan Teorema yang ada pada graf path , graf sikel

, dan graf bintang .

3. Memberikan pelabelan pada graf path , graf sikel , dan graf

bintang .

4. Memahami definisi graf middle.

5. Membentuk graf middle dari graf path , graf sikel , dan graf bintang .

6. Memberikan pelabelan pada graf middle yang dibentuk dari graf

path , graf sikel , dan graf bintang .

3.5 Penarikan Kesimpulan

Tahap ini merupakan tahap terakhir dalam metode penelitian. Penarikan

kesimpulan dari permasalahan diperoleh dari hasil langkah pemecahan masalah

yang dirumuskan berdasarkan studi pustaka dan pembahasannya.

18

BAB IV

HASIL DAN PEMBAHASAN

4.1 Pelabelan

4.1.1 Definisi

Berdasarkan hasil penelitian Clipperton dkk., (2005:1) dan Chia, (2011:

2439) jika diketahui graf . Maka pelabelan pada graf

adalah fungsi , dengan berlaku

4.1.2 Definisi

Jika terdapat titik dan di dalam graf , maka jarak antara titik dan

adalah banyaknya sisi yang dilewati dari titik menuju titik . Bilangan

pelabelan , disimbolkan , dari graf adalah bilangan asli terkecil

sedemikian sehingga memiliki pelabelan dengan sebagai label

maksimum. Sebuah pelabelan dari graf disebut pelabelan

minimal dari jika label tertinggi dari sembarang titik dalam pelabelan itu adalah

(Yeh, 2006: 1218).

Jika tidak digunakan sebagai label titik dalam suatu pelabelan

dari sebuah graf, maka setiap label titik dapat diturunkan untuk memperoleh

pelabelan dari sebuah graf. Jadi dalam pelabelan minimal,

harus digunakan sebagai label titik.

19

Gambar 4.1 Graf

Pada gambar 4.1 dijelaskan tentang pelabelan pada suatu graf

. Pertama, beri label 1 pada suatu titik misalkan titik . Karena titik dan

berjarak satu maka harus diberikan label dengan selisih minimal tiga, misalkan

titik diberi label . Sedangkan pada titik dan berjarak dua maka harus

diberikan label dengan selisih minimal dua, misalkan titik diberi label 7,

karena pada titik dan berjarak tiga maka harus diberikan label dengan selisih

minimal satu, maka titik diberi label . Sehingga diperoleh label terkecil pada

graf adalah dan .

Gambar 4.2 Graf

20

Pada Gambar 4.2 dijelaskan tentang pelabelan pada suatu graf

. Pertama, beri label pada suatu titik misalkan titik . Karena titik dan

berjarak satu maka harus diberikan label dengan selisih minimal tiga, misalkan

titik diberi label . Karena titik dan berjarak satu maka titik diberi

label . Sedangkan titik dan berjarak dua maka harus diberikan label dengan

selisih minimal dua, misalkan titik diberi label . Karena titik dan

berjarak dua maka titik diberi label . Sedangkan titik dan berjarak tiga

maka harus diberikan label dengan selisih minimal satu, misalkan titik diberi

label dan karena titik dan berjarak satu maka titik diberi label .

Sehingga diperoleh label terkecil pada graf adalah dan .

4.2 Pelabelan pada Graf Khusus

4.2.1 Pelabelan pada Graf Path

Berikut ini akan dibahas Lemma 4.2.1.1 untuk membuktikan teorema

4.2.1.2.

Lemma 4.2.1.1

Untuk setiap graf path pada titik yang dinotasikan dengan , dengan

, maka .

Bukti :

Misalkan adalah pelabelan minimal untuk graf path pada

titik yang dinotasikan dengan dan andaikan untuk . Misalkan

merupakan titik dengan label . Di sana dimasukan subpath paling sedikit

21

titik dengan sebagai titik pertama. Misalkan

merupakan graf path. Selanjutnya akan dihitung kemungkinan untuk

Kasus I :

Jika dimisalkan dan , maka

kontradiksi dengan yang diasumsikan bahwa .

Kasus II :

Jika dimisalkan , maka kontradiksi dengan yang diasumsikan

bahwa

Kasus III :

Jika dimisalkan , maka kontradiksi dengan yang

diasumsikan bahwa .

Kasus IV :

Jika dimisalkan atau . Keduanya mungkin untuk dengan

memberi , yang mana kontradiksi dengan Hal ini dapat

dilihat bahwa jika diambil dan

maka kontradiksi. Jika diambil dan ,

maka kontradiksi juga.

Oleh karena itu, dapat diambil kesimpulan bahwa jika

Teorema 4.2.1.2

Untuk setiap graf path, yang dinotasikan dengan , maka

22

Bukti :

Misalkan merupakan himpunan dari titik pada

sedemikian sehingga berdekatan dengan untuk Didefinisikan

sedemikian sehingga dan

jika (mod8). Menurut definisi dari dan berdasarkan Lemma 4.2.1.1 maka

untuk .

Untuk setiap dengan , maka akan diproses beberapa kasus dengan

menggunakan pola pelabelan yang didefinisikan oleh dan dapat dilihat bahwa

setiap merupakan subpath yang tereduksi dari dengan .

Kasus I :

Ini adalah kasus trivial.

Kasus II : .

Pola pelabelan menunjukkan bahwa karena tidak ada

penyelesaian yang lebih baik dari pada itu.

Kasus III :

Akan ditunjukan bahwa pola pelabelan dari untuk

adalah Andaikan Terdapat titik sedemikian

sehingga Jika memiliki derajat , maka titik dan ada

sedemikian sehingga dan sehingga kontradiksi. Jika

memiliki derajat , misalkan , maka kemungkinan untuk adalah

dan . Dalam salah satu kasus, diketahui maka kontradiksi dengan

yang diasumsikan bahwa .

23

Kasus IV :

Akan ditunjukkan bahwa pola pelabelan dari untuk

adalah . Andakain . Terdapat titik sedemikian

sehingga dan titik dan ada atau dan ada. Tanpa

menghilangkan sifat umum, andaikan dan ada. Kemungkinan untuk

adalah dan Jika , maka , sehingga

kontradiksi dengan yang diasumsikan bahwa . Jika maka

Selanjutnya, jika memiliki derajat , maka ada dan

Jika memiliki derajat maka titik dan ada. Satu-

satunya kemungkinan untuk adalah . Tetapi dengan memasukkan

maka kontradiksi dengan yang diasumsikan bahwa .

Pada gambar berikut ini akan diberikan contoh pelabelan pada

graf path yang berdasarkan pada Lemma 4.2.1.1 dan Teorema 4.2.1.2.

Contoh :

Misalkan, suatu graf path dengan titik yang dinotasikan dengan

maka .

Gambar 4.3 Pelabelan pada Graf Path dengan

Contoh :

Misalkan, suatu graf path dengan titik yang dinotasikan dengan ,

maka

24


Contoh :

Misalkan, suatu graf path dengan titik atau yang dinotasikan

dengan dan , maka dan



Contoh :

Misalkan, suatu graf path dengan titik atau yang dinotasikan

dengan dan , maka dan


6

7 6

4

25

Gambar 4.8 Pelabelan pad Graf Path dengan


Contoh :

Misalkan terdapat graf path dengan titik , yang dinotasikan dengan

maka Selanjutnya pada Gambar 4.10 dijelaskan tentang pelabelan

pada graf path Pertama, beri label 1 pada suatu titik misalkan titik

. Karena titik dan berjarak satu maka harus diberikan label dengan selisih

minimal tiga, misalkan titik diberi label . Karena titik dan berjarak satu

maka titik diberi label . Sedangkan pada titik dan berjarak dua maka

harus diberikan label dengan selisih minimal dua, misalkan titik diberi label .

Karena titik dan berjarak satu maka titik diberi label . Karena titik

dan berjarak satu maka titik diberi label . Sedangkan pada titik dan

berjarak dua maka titik diberi label . Kemudian untuk titik diberi label

karena pada titik dan berjarak satu.

.

2

26

Gambar 4.10 Pelabelan pada Graf Path

4.2.2 Pelabelan pada Graf Sikel

Lemma 4.2.2.1

Misalkan adalah bilangan bulat ganjil, jika maka .

Bukti :

Misalkan adalah pelabelan minimal dari di mana adalah

bilangan ganjil dan . Andaikan Maka hanya pelabelan yang

mungkin dengan sebagai bilangan bulat maksimum adalah sebagai berikut:

dan

Dapat dilihat bahwa dan adalah pelabelan untuk sikel genap.

Dari pelabelan sisa dan semua gagal sebagai pelabelan pada

sikel karena label yang hilang harus lebih besar daripada yang diasumsikan

. Oleh karena itu, tidak ada pelabelan minimal yang berada

pada dengan ganjil dan sedemikian sehingga

7

27

Lemma 4.2.2.2

Untuk setiap graf sikel dengan maka .

Bukti :

Akan ditunjukkan bahwa pola pelabelan dari adalah .

Kemudian, misalkan adalah pelabelan minimal dari dan andaikan

. Diberikan sedangkan dan adalah dua titik yang

berdekatan dengan . Maka kemungkinan untuk )} adalah

.

Kasus I :

Jika misalkan maka kontradiksi dengan yang diasumsikan

bahwa Jika diambil maka tidak memenuhi definisi 4.1.1

karena selisih label pada titik dan hanya 1.

Kasus II : { atau

Jika dimisalkan maka kontradiksi dengan yang diasumsikan

bahwa Jika diambil maka tidak memenuhi definisi 4.1.1

karena selisih label pada titik dan hanya 1. Oleh karena itu .

Contoh :

Gambar 4.11 Pelabelan pada Graf Sikel dengan

28

Lemma 4.2.2.3

Untuk setiap graf sikel dengan maka

Bukti :

Dari teorema 4.2.1.2 dapat diketahui bahwa karena

Misalkan adalah pelabelan minimal dari dan andaikan

Diberikan dan misalkan dan adalah dua titik yang berdekatan

dengan . Maka kemungkinan untuk adalah dan

Kasus I :


bahwa

Kasus II : atau :


bahwa

Karena tidak mungkin terjadi, maka didapatkan .

Menurut Lemma 4.2.2.1 untuk sikel ganjil, dapat dilihat bahwa Maka

diperoleh Sehingga, pola pelabelan menunjukkan bahwa

Oleh karena itu

29

Contoh :


Lemma 4.2.2.4

Untuk graf sikel dengan maka

Bukti :

Akan ditunjukkan bahwa pola pelabelan dari adalah

. Misalkan adalah pelabelan minimal dari dan

andaikan Diberikan , dan misalkan dan adalah dua

titik yang berdekatan dengan . Maka kemungkinan untuk adalah

, dan .

Kasus I :

Jika dimisalkan dan Untuk diketahui ,

maka kontradiksi dengan

Kasus II : atau


bahwa Oleh karena itu .

30

Contoh :


Lemma 4.2.2.5

Untuk graf sikel dengan maka

Bukti :

Misalkan adalah himpunan titik dari . Andaikan

dan misalakan adalah pelabelan minimal dari , maka

kemungkinan nilai pada berada di dalam Karena jarak

terbesar antara dua titik yang berada di dalam adalah , tidak ada kemungkinan

nilai untuk dapat diulangi. Serta, hanya sampai dua label berurutan yang

mungkin dipergunakan. Jika mempergunakan tiga label berurutan itu tidak

mungkin karena terdapat pembatas jarak pada pelabelan . Maka paling banyak

ada label yang dapat digunakan dari , seharusnya titik yang tak berlabel

menjadi berlabel dengan nilai yang , sehigga kontradiksi dengan yang

diasumsikan bahwa Dengan demikian Sehingga, pola

pelabelan menunjukkan bahwa Oleh karena itu,

31

Contoh :


Selanjutnya, untuk membuktikan Teorema 4.2.2.9 bahwa setiap graf sikel

dengan , jika genap maka atau jika ganjil maka

, maka diperlukan Lemma 4.2.2.6 dan Lemma 4.2.2.7.

Lemma 4.2.2.6

Misalkan adalah bilangan bulat genap. Jika , maka terdapat

bilangan bulat non negatif dan sedemikian sehingga .

Bukti :

Misalkan dan adalah bilangan bulat

genap. Maka (mod atau (mod . Andaikan bahwa

Kasus I : (mod ) :

Jika terdapat bilangan bulat sedemikian sehingga . Karena

Ini meliputi di mana dan . Maka, .

1

32

Kasus II : (mod ) :

Jika terdapat bilangan bulat sedemikian sehingga Ini

meliputi . Karena dan (mod ), didapatkan .

Maka Dari ini, terdapat bahwa di mana

dan Maka,

Oleh karena itu, jika adalah bilangan bulat genap dan maka

terdapat bilangan bulat non negatif dan sedemikian sehingga

Contoh :


genap. Jika , maka terdapat bilangan bulat non negatif dan sedemikian

sehingga

Sehingga diperoleh

Lemma 4.2.2.7

Misalkan adalah bilangan bulat ganjil. Jika dan , maka

terdapat bilangan bulat non negatif dan sedemikian sehingga

33

Bukti :


ganjil. Maka (mod ) atau (mod ). Andaikan dan .

Kasus I : (mod ) :

Jika terdapat bilangan bulat sedemikian sehingga . Ini

meliputi bahwa . Karena didapatkan Ini

mengimplikasikan bahwa di mana dan Maka,

.

Kasus II : (mod ) :

Jika terdapat bilangan bulat sedemikian sehingga Ini

mengimplikasikan bahwa Karena dan

(mod , didapatkan Maka Karena di

mana dan maka

Oleh karena itu, jika adalah bilangan bulat ganjil sedemikian sehingga

dan maka di mana dan bilangan bulat non

negatif.

Contoh :


ganjil. Jika dan maka terdapat bilangan bulat non negatif dan

sedemikian sehingga

34

Sehingga diperoleh

Sebelum membahas teorema 4.2.2.9 kita akan bahas terlebih dahulu

teorema yang mendukung teorema 4.2.2.9.

Teorema 4.2.2.8

Untuk setiap graf lengkap pada titik, maka .

Bukti :

Misalkan adalah suatu graf lengkap dengan

dan adalah pelabelan minimal dari dengan

untuk semua . Kemudian, untuk setiap dan

, sedemikian sehingga Dengan demikian,

untuk setiap dan Karena terdapat di

dalam sedemikian sehingga maka Begitu juga, karena

adalah pelabelan minimal dari , sedemikian sehingga untuk setiap

dengan Secara rekursif, maka akan diperoleh :

35

.

Oleh karena itu,

Teorema 4.2.2.9

Untuk setiap graf sikel, dengan maka

Bukti :

Misalkan dan adalah titik dari sedemikian

sehingga untuk dan adalah sisi dalam Kasus

berikut ini menggambarkan semua kemungkinan pada

Kasus I :

Dapat dilihat bahwa adalah graf lengkap. Oleh karena itu, berdasarkan

Teorema 4.2.2.8 untuk graf lengkap, maka

Kasus II : genap :

Diketahui menurut Lemma 4.2.2.2 dan menurut

Lemma 4.2.2.4. Berdasarkan Teorema 4.2.1.2 pada graf path menunjukkan bahwa

untuk . Maka untuk setiap graf sikel yang genap,

Mengingat pelabelan yang digunakan untuk dan pada Lemma 4.2.2.2 dan

Lemma 4.2.2.4, secara berturut-turut yaitu: untuk digunakan

dan untuk digunakan Dapat dilihat bahwa

36

pelabelan yang digunakan untuk dapat diulang secara tak terbatas untuk setiap

dengan perkalian dari . Demikian juga, pelabelan yang digunakan untuk

dapat diulang secara tak terbatas untuk setiap dengan perkalian dari . Selain

itu, pelabelan dari dan dapat digabung bersama menjadi label seperti

berikut : Berdasarkan Lemma 4.2.2.6, dapat

diketahui bahwa setiap bilangan bulat genap yang lebih besar dari atau sama

dengan dapat dinyatakan sebagai kombinasi dari perkalian non negatif dari

dan . Dari hal ini, jelas bahwa pelabelan dari setiap yang genap tersusun dari

kombinasi yang berasal dari perkalian non negatif pada pola pelabelan dan .

Oleh karena itu, untuk setiap genap.

Kasus III : ganjil dan atau

Berdasarkan Lemma 4.2.2.3 diketahui bahwa kemudian

bardasarkan Teorema 4.2.1.2 untuk graf path diketahui bahwa untuk

karena dan bardasarkan Lemma 4.2.2.1 diketahui bahwa

untuk graf sikel ganjil. Ini mengimplikasikan bahwa untuk setiap graf

sikel ganji . Dalam Lemma 4.2.2.3, dilabeli dengan

Dapat dilihat bahwa pelabelan dari dapat diulang secara tak terbatas untuk

setiap dengan perkalian dari . Serta dapat dikombinasikan pelabelan untuk

dengan pelabelan untuk yang digunakan dalam Lemma 4.2.2.2 menjadi

label seperti berikut : Berdasarkan Lemma 4.2.2.7 dapat

diketahui bahwa setiap bilangan bulat ganjil yang lebih besar dari atau sama

dengan , dengan pengecualian 11, dapat dinyatakan sebagai suatu kombinasi dari

perkalian non negatif dari dan . Ini mengimplikasikan bahwa setiap , dengan

37

dan terdiri dari kombinasi yang berasal dari perkalian non negatif

pada dan . Oleh sebab itu, karena diperoleh untuk

setiap , dimana dan . Untuk dapat diketahui bahwa

(berasal dari Lemma 4.2.2.2 dan Lemma 4.2.2.5). Didefinisikan untuk

sedemikian sehingga . Karena max

Kasus IV :

Berdasarkan Lemma 4.2.2.5, maka diperroleh

Contoh :

Untuk setiap graf sikel yang dinotasikan dengan , dengan , jika

maka .


maka

Contoh :


genap maka . Misalkan maka .

38


maka

Contoh :


ganjil dan atau maka maka


maka

39

Contoh :

Misalkan untuk setiap graf sikel yang dinotasikan dengan , dengan

, jika maka Selanjutnya pada Gambar 4.18 pelabelan

pada graf sikel Pertama, beri label 1 pada suatu titik misalkan titik

. Karena titik dan berjarak satu maka harus diberi label dengan selisih

tiga, misalkan titik diberi label . Karena titik dan berjarak satu maka


label . Sedangkan pada titik dan berjarak tiga maka harus diberi label

dengan selisih minimal satu, misalkan titik diberi label . Karena titik dan

berjarak tiga maka titik diberi label 5. Kemudian untuk titik diberi label

karena pada titik dan berjarak tiga.

Gambar 4.18 Pelabelan pada Graf Sikel dengan , jika ,

maka

40

4.2.3 Pelabelan pada Graf Bintang

Teorema 4.2.3.1

Untuk setiap graf bipartit lengkap , maka

Bukti :

Misalkan adalah suatu graf bipartit lengkap, yang

dinotasikan dengan . Graf ini memiliki titik dan sisi. Misalkan

dan .

Akan dibuktikan bahwa titik label pada himpunan dan memenuhi

Teorema 4.2.3.1. Misalkan adalah pelabelan minimal dari dengan

dan . Jika

untuk setiap dengan maka sama halnya untuk

pasangan dari titik di dalam yaitu untuk setiap dengan

. Misalkan maka tiap dengan menjadi ganjil karena

adalah minimal. Dengan demikian, .

Karena setiap berdekatan dengan setiap , maka

. Sehingga diperlukan . Kemudian, karena

, maka Oleh karena itu, adalah

minimal sehingga diperoleh . Pelabelan pada

titik berikut sama dengan pelabelan pada titik yaitu : karena

maka diperlukan untuk menjadi genap. Dengan demikian,

. Sehingga diperoleh

. Oleh karena itu .

41

Contoh :

Pada Gambar 4.19 berikut ini akan diberikan contoh pelabelan

pada graf bipartit lengkap. Misalkan terdapat graf bipartit lengkap dengan titik

dan yang dinotasikan dengan , maka

. Selanjutnya akan dijelaskan tentang pelabelan pada graf bipartit

lengkap . Pertama, beri label 1 pada suatu titik misalkan titik . Karena titik

dan berjarak dua maka harus diberikan label dengan selisih minimal dua,

misalkan titik diberi label . Karena titik dan berjarak dua maka titik

diberi label . Karena titik dan berjark dua maka titik diberi label .

Sedangkan pada titik dan berjarak satu maka harus diberikan label dengan

selisih minimal tiga, misalkan titik diberi label . Kemudian untuk titik

diberi label karena pada titik dan berjarak dua.

Gambar 4.19 Pelabelan pada Graf Bipartit Lengkap

42

Akibat 4.2.3.2

Untuk graf bintang atau , maka .

Bukti :

Menurut definisi, graf bintang atau adalah graf bipartit lengkap yang

berbentuk . Oleh karena itu, .

Contoh :

Pada gambar 4.20 berikut ini akan diberikan contoh pelabelan

pada graf bintang. Misalkan terdapat graf bintang dengan titik yang

dinotasikan dengan atau , maka . Selanjutnya akan

dijelaskan tentang pelabelan pada graf bintang . Pertama, beri label

pada suatu titik misalkan titik . Karena titik dan berjarak satu maka harus

diberikan label dengan selisih minimal tiga, misalkan titik diberi label .

Sedangkan pada titik dan berjarak dua maka harus diberikan label dengan

selisih minimal dua, misalkan titik diberi label . Karena titik dan

berjarak dua maka titik diberi label . Karena titik dan berjarak dua maka

titik diberi label . Kemudian untuk titik diberi label karena pada titik

dan berjarak dua.

43

Gambar 4.20 Graf Bintang dan pelabelan pada Graf Bintang

4.3 Graf Middle

Definisi 4.3.1

Graf middle pada graf yang dinotasikan adalah graf yang

himpunan titiknya adalah . Dua

titik adjacent jika dan hanya jika:

(i) adjacent dengan karena sisi

dan sisi incident pada titik yang sama di graf .

(ii) adjacent dengan karena sisi

incident dengan titik (Vaidya & Bantva, 2010:104).

4.4 Pembentukan Graf Middle pada Graf Khusus

4.4.1 Graf Middle dari Graf Path

Berikut akan diberikan contoh pembentukan graf middle dari graf path .

44

Contoh :

Graf path mempunyai himpunan titik

dan himpunan sisi . Graf middle dari graf adalah

graf yang mempunyai himpunan titik jadi himpunan titik

adalah { . Dua titik adalah

adjacent di jika:


dan sisi incident di titik

adjacent dengan karena sisi







incident dengan titik .







45













Berikut adalah pembentukan graf middle dari graf path yang

ditunjukkan pada Gambar 4.21.

Gambar 4.21 Graf dan Graf

46


graf middle yang dibentuk dari graf path berdasarkan definisi 4.3.1.

Contoh :

Misalkan, suatu graf path dengan titik yang dinotasikan dengan .

Berikut adalah pembentukan graf middle dari graf path yang ditunjukkan pada

Gambar 4.22.


Pada Gambar 4.23 diberikan graf , ditunjukkan pelabelan pada

graf dan diperoleh .

Gambar 4.23 Graf dan Pelabelan pada Graf

Contoh :

47



Gambar 4.24.





Contoh :



Gambar 4.26.

48





Contoh :



Gambar 4.28.


12

7

49




Contoh :



Gambar 4.30.


Selanjutnya pada Gambar 4.31 dijelaskan tentang pelabelan pada

graf middle dari graf dan diperoleh . Pertama, beri label pada

suatu titik misalkan titik . Karena titik dan berjarak satu maka harus

50

diberikan label dengan selisih minimal tiga, misalkan titik diberi label .

Sedangkan titik dan berjarak dua maka harus diberikan label dengan selisih

minimal dua, misalkan titik diberi label . Karena titik dan berjarak dua

maka titik diberi label . Karena titik dan berjarak dua maka titik

diberi label . Karena titik dan berjarak satu maka titik diberi label .

Sedangkan titik dan berjarak tiga maka harus diberikan label dengan selisih

minimal satu, misalkan titik diberi label . Karena titik dan berjarak satu

maka titik diberi label . Karena titik dan berjarak dua maka titik

diberi label . Karena titik dan berjarak dua maka titik diberi label .

Kemudian untuk titik diberi label karena pada titik dan berjarak dua.

Gambar 4.31 Pelabelan pada Graf

Contoh :



Gambar 4.32.

51


Pada Gambar 4.33 ditunjukkan pelabelan pada graf dan

diperoleh .


Pada pelabelan Gambar 4.33 di atas, label digunakan dua kali dalam

melabeli suatu titik sehingga pelabelan di atas bukan suatu fungsi (pemetaan)

melainkan suatu fungsi surjektif. Sehingga pembentukan graf middle dari graf

path hanya sampai .

52

4.4.2 Graf Middle dari Graf Sikel

Berikut akan diberikan contoh pembentukan graf middle dari graf sikel .

Contoh:

Graf sikel mempunyai himpunan titik dan

himpunan sisi . Graf middle dari graf adalah graf yang

mempunyai himpunan titik jadi himpunan titik adalah

{ . Dua titik adalah adjacent di jika:


dan sisi di titik













53





Berikut adalah pembentukan graf middle dari graf sikel yang ditunjukkan pada

Gambar 4.34.



graf middle yang dibentuk dari graf sikel berdasarkan definisi 4.3.1.

Contoh :

Misalkan, suatu graf sikel dengan titik yang dinotasikan dengan .

Pada Gambar 4.35 diberikan graf , pelabelan pada graf dan

diperoleh .

54


Contoh :



Gambar 4.36.


1

55

Pada Gambar 4.37 ditunjukkan pelabelan pada dan

diperoleh .


Contoh :


Berikut adalah pembentukan graf middle dari graf sikel yang ditunjukkan pada

Gambar 4.38.

56


Selanjutnya pada gambar 4.39 dijelaskan tentang pelabelan pada

graf middle dari graf dan diperoleh . Pertama, beri label pada

suatu titik misalkan titik . Karena titik dan berjarak tiga maka harus

diberikan label dengan selisih minimal satu, misalkan titik diberi label .

Karena titik dan berjarak tiga maka titik diberi label . Karena titik

dan berjarak tiga maka titik diberi label . Karena titik dan berjarak

tiga maka titik diberi label . Sedangkan titik dan berjarak satu maka

harus diberikan label dengan selisih minimal tiga, misalkan titik diberi label .

Karena titik dan berjarak satu maka titik diberi label . Sedangkan titik

dan berjarak dua maka harus diberikan label dengan selisih minimal dua,

misalkan titik diberi label . Karena titik dan berjarak dua maka titik

57

diberi label . Kemudian untuk titik diberi label karena pada titik dan

berjarak dua.


Contoh:

Misalkan, suatu graf sikel dengan titik yang dinotasikan dengan . Berikut

adalah pembentukan graf middle dari graf sikel yang ditunjukkan pada Gambar

4.40.

58

14


Pada Gambar 4.41 ditunjukkan pelabelan pada graf dan

diperoleh


Pada pelabelan Gambar 4.41 di atas, label dan digunakan dua kali

dalam melabeli suatu titik sehingga pelabelan di atas bukan suatu fungsi

59

(pemetaan) melainkan suatu fungsi surjektif. Sehingga pembentukan graf middle

dari graf sikel hanya sampai .

4.4.3 Graf Middle dari Graf Bintang

Berikut akan diberikan contoh pembentukan graf middle dari graf bintang.

Karena graf bintang dan graf bintang sudah dijelaskan pada

pembentukan graf path dan graf path , maka contoh pembentukan graf

middle dari graf bintang dimulai dari .

Contoh :

Graf bintang mempunyai himpunan titik

dan himpunan sisi . Graf middle dari graf adalah graf

yang mempunyai himpunan titik jadi himpunan titik

adalah { . Dua titik adalah adjacent di

jika:





60









Berikut adalah pembentukan graf middle dari graf bintang yang

ditunjukkan pada Gambar 4.42.



graf middle yang dibentuk dari graf bintang berdasarkan definisi 4.3.1.

61

Contoh :

Misalkan, suatu graf bintang dengan titik yang dinotasikan dengan

dan diperoleh . Selanjutnya akan dijelaskan tentang pelabelan

pada graf bintang . Pertama, beri label pada suatu titik misalkan

titik . Karena titik dan berjarak satu maka harus diberikan label dengan

selisih minimal tiga, misalkan titik diberi label . Sedangkan titik dan

berjarak dua maka harus diberikan label dengan selisih minimal dua, misalkan


label . Karena titik dan berjarak satu maka titik diberi label .

Sedangkan titik dan berjarak tiga maka harus diberikan label dengan selisih

minimal satu, misalkan titik diberi label . Kemudian titik diberi label

karena titik dan berjarak tiga.


62

Contoh:

Misalkan, suatu graf bintang dengan titik yang dinotasikan dengan

. Berikut adalah pembentukan graf middle dari graf bintang yang

ditunjukkan pada 4.44.


Pada Gambar 4.45 ditunjukkan pelabelan pada dan

diperoleh .


Pada pelabelan Gambar 4.45 di atas, label dan digunakan dua kali

dalam melabeli suatu titik sehingga pelabelan di atas bukan suatu fungsi

63

(pemetaan) melainkan suatu fungsi surjektif. Sehingga pembentukan graf middle

dari graf bintang hanya sampai .

64

BAB V

PENUTUP

5.1 Simpulan

Berdasarkan pembahasan dari bab sebelumnya mengenai pelabelan

dan pembentukan graf middle pada beberapa graf khusus, dapat diambil

kesimpulan sebagai berikut.

5.1.1 Hasil pelabelan pada graf path , graf sikel , dan graf bintang

adalah sebagai berikut.

1. Pelabelan pada graf path untuk mempunyai ,

mempunyai , mempunyai ,

mempunyai , mempunyai , mempunyai

dan mempunyai .

2. Pelabelan pada graf sikel untuk mempunyai ,


mempunyai , mempunyai , mempunyai

.

3. Pelabelan pada graf bintang untuk mempunyai

.

5.1.2 Hasil pelabelan pada graf middle dari graf path , graf sikel ,

graf bintang adalah sebagai berikut.

65

1. Pelabelan pada graf middle dari graf path untuk


mempunyai , mempunyai dan

mempunyai .

2. Pelabelan pada graf middle dari graf sikel untuk

mempunyai , mempunyai dan

mempunyai .

3. Pelabelan pada graf middle dari graf bintang untuk

mempunyai .

5.2 Saran

1. Dalam penelitian ini pembahasan mengenai pelabelan dan

pembentukan graf middle hanya meliputi graf path , graf sikel , dan graf

bintang . Penulis berharap penulis lain dapat menemukan pelabelan

dan pembentukan graf middle dari graf khusus lainnya.

2. Disarankan penulis lain dapat mengaplikasikan pelabelan pada

kehidupan nyata.

66

DAFTAR PUSTAKA

Budayasa, I. K. 2007. Teori Graf dan Aplikasinya. Surabaya: Unesa University

Press.

Budiasti, H. 2010. Pelabelan Total Titik Tak Beraturan pada Graf Bipartisi

Lengkap. Skripsi. Semarang: FMIPA Universitas Negeri Semarang.

Chang, G. J. dkk. 2000. On )-labelings of Graphs. Discrete Mathematics,

220: 57–66.

Chia, Ma-Lia. 2011. -Labeling of Graphs. Taiwanese Journal of

Mathematics, 15(6): 2439-2457.

Clipperton, J. dkk. 2005. Labeling of Simpel Graphs. REU Paper,

Valparais Universit. Tersedia di

http://www.valpo.edu/mcs/pdf/zslabeling.pdf [diakses 12-01-2012].

Clipperton, J. 2008. Labeling of Simple Graphs. Rose-Hulman Institute

of Tecnology Undergraduate Math Journal, volume 9. Tersedia di

http://www.rose-hulman.edu/mathjournal//archives/2008/vol9-

n2/paper2/v9n2-2pd.pdf [diakses 12-01-2012].

Griggs, J. R. & R. K. Yeh. 1992. Labeling Graphs with a Condition at Distance 2.

SIAM J. DISC. MATH.,5(4): 586-595.

Huda, N & Amri, Z. 2012. Pelabelan Graceful, Skolem Graceful dan Pelabelan

pada Graf H-Bintang dan A-Bintang. Jurnal Matematika Murni dan

Terapan, 6(1): 30-37.

Rossen, K. H. 2003. Discrete Matematics and its Applications, fifth edition. New

York: VAGA.

Siang, J. J. 2002. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer.

Yogyakarta: ANDI Offset.

Sugiarto. 2006. Pengantar Dasar Matematika. Semarang.

Sutarno, H. dkk. 2003. Matematika Diskrit. Jakarta: JICA.

http://www.valpo.edu/mcs/pdf/zslabeling.pdf

http://www.rose-hulman.edu/mathjournal/archives/2008/vol9-n2/paper2/v9n2-2pd.pdf

http://www.rose-hulman.edu/mathjournal/archives/2008/vol9-n2/paper2/v9n2-2pd.pdf

67

Vaidya, S. K. & D. D. Bantva, D. D. 2010. The L(2,1)-Labeling of Some Middle

Graphs. Journal of Applied Computer Science & Mathematics, 9(4): 104-

107.

Yeh, R. K. 2006. A survey on labeling graphs with a condition at distance two.

Discrete

Mathematics, 306: 1217-1231.

Lingscheit, M., K. Ruff & Ward, J. 2009. Minimal and Surjective Graf

Labeling. Rose-Hulman Mathjournal, volume 10. Tersedia di

https://www.rose-hulman.edu/mathjournal/archives/2009/vol10-

n1/paper12/v10n1-12pd.pdf. [diakses 12-01-2012].

Bartle, G. R & D. R. Sherbert. 1994. Introduction to Real Analysis. Singapore:

Jhon Wiley & Sons, INC.

https://www.rose-hulman.edu/mathjournal/archives/2009/vol10-n1/paper12/v10n1-12pd.pdf

https://www.rose-hulman.edu/mathjournal/archives/2009/vol10-n1/paper12/v10n1-12pd.pdf

pelabelan dan pembentukan graf middle pada …lib.unnes.ac.id/19104/1/4111409019.pdf · 1 pelabelan...

Documents