MIDDLE PADA BEBERAPA GRAF KHUSUS

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

1

ii

PENGESAHAN Skripsi yang berjudul Pelabelan Khusus

dan Pembentukan Graf Middle pada Beberapa Graf

disusun oleh : Meliana Deta Anggraeni 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. NIP. 196310121988031001

Drs Arief Agoestanto, M.Si. 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

ii

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

Meliana Deta Anggraeni NIM. 4111409019

iii

iv

MOTTO DAN PERSEMBAHAN MOTTO o Mengetahui kekurangan diri adalah tangga untuk menggapai citacita, 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. Adik dan kekasih tersayang. Almamaterku.

2. 3.

iv

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,

v

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,

Penulis

vi

Agustus 2013

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 bilanganbilangan 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

.

.

vii

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

viii

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

ix

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

Gambar 2.4 Graf terhubung

yang dibangun oleh dan Graf tidak terhubung

Gambar 2.5 Graf tidak terhubung dengan

....... 10 ............................. 11

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



......................... 27



......................... 28



......................... 28



......................... 28


pad Graf Path dengan

........................... 28

x

xi



......................... 29


pada Graf Path

......................................... 29


pada Graf Sikel dengan

.............. 31



.............. 33



.............. 34



........... 35



, jika

maka

.................................................................................... 41 Gambar 4.16 Pelabelan


, jika

maka

..................................................................................... 42 Gambar 4.17 Pelabelan


maka

, jika

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



maka

, jika

,

........................................................................... 43


pada Graf Bipartit Lengkap


dan pelabelan

................... 45

pada Graf Bintang

... 47

Gambar 4.21 Graf

dan Graf

................................................................. 50

Gambar 4.22 Graf

dan Graf

................................................................. 50

Gambar 4.23 Graf Gambar 4.24 Graf Gambar 4.25 Graf Gambar 4.26 Graf Gambar 4.27 Graf

dan Pelabelan dan Graf

pada Graf

................................................................. 51


................ 51

pada Graf

................ 51

................................................................. 52

dan Pelabelan

pada Graf

xi

................. 52

xii

Gambar 4.28 Graf

dan Graf

Gambar 4.29 Graf Gambar 4.30 Graf


Gambar 4.31 Pelabelan Gambar 4.32 Graf

dan Graf

Gambar 4.35 Graf Gambar 4.36 Graf



Gambar 4.41 Pelabelan Gambar 4.42 Graf Gambar 4.43 Graf Gambar 4.44 Graf


.......................................... 59

.......................................... 61

.......................................... 62

.............................................................. 64


................ 58

............................................................... 62 pada Graf

dan Graf

pada Graf

............................................................... 60 pada Graf

dan Graf

........................................... 55

................................................................ 59 pada Graf

dan Graf

........................................... 54

................................................................ 57


................ 53

................................................................ 55 pada Graf

dan Graf

pada Graf

................................................................. 53 pada Graf


................................................................. 53

pada Graf

................ 65

................................................................ 66 pada Graf

xii

........................................... 67

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

xiii

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 bilanganbilangan bulat positif, yang disebut label (Chang, 2000). Jika suatu pelabelan hanya menggunakan domain berupa titik maka disebut pelabelan titik, dan apabila

1

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 , dan graf bintang

, graf sikel

(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 , dan graf bintang

pada graf path

?

2. Bagaimana cara menentukan graf middle dari graf path graf bintang

, graf sikel

, dan pelabelan

, graf sikel

,

nya?

1.3 Pembatasan Masalah 1. Pelabelan

.

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

, graf bintang

, dan graf middle.

, graf

3

1.4 Tujuan Penulisan Tujuan dari penelitian ini adalah sebagai berikut. 1. Mengetahui pelabelan bintang

pada graf path

, graf sikel

, dan graf

.

2. Mengetahui cara menentukan graf middle dari graf path graf bintang

, dan pelabelan

, graf sikel

,

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.

BAB II LANDASAN TEORI

2.1 Graf 2.1.1 Definisi Graf

adalah pasangan

, di mana

berhingga titik-titik (vertices) yang tak kosong dan

adalah himpunan adalah himpunan sisi

(mungkin kosong), sedemikian sehingga setiap sisi (edge) di pasangan tak berurutan dari titik-titik di dengan

. Himpunan titik dari

, sedangkan himpunan sisi dinotasikan dengan

adalah dinotasikan (Budayasa,

2007: 1). Jumlah titik dari graf

disebut order graf

sedangkan jumlah sisi dari graf dengan

yang dinotasikan dengan

disebut size graf

yang dinotasikan

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

Contoh :

Gambar 2.1 Graf dengan 5 titik dan 6 sisi

6

7

Dalam sebuah graf, seperti terlihat pada Gambar 2.1, dimungkinkan adanya suatu sisi yang dikaitkan dengan pasangan ujungnya sama disebut loop/gelang. Pada Gambar 2.1, sisi

. Sisi yang dua titik merupakan sebuah

loop. Dalam sebuah graf dimungkinkan adanya lebih dari satu sisi yang dikaitkan dengan sepasang titik. Pada Gambar 2.1, sisi pasangan titik

dan sisi

dikaitkan dengan

. 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

disebut saling berinsidensi atau titik

, maka

dan

terkait (incident) dengan sisi

(Sutarno dkk., 2003: 60). Contoh : Pada Gambar 2.1 di atas, sisi dengan titik

dan

adalah sisi-sisi yang terkait

.

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, titik

dan

dan

adalah dua titik yang saling bertetangga, sedangkan

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

dengan

(Siang, 2002: 205).

dan derajat maksimumnya dinotasikan

Contoh : Pada Gambar 2.1, terlihat bahwa untuk setiap titik adalah

, dan

,

di

,

derajat titiknya . Sehingga

.

2.1.5 Definisi Misalkan G adalah sebuah graf. Sebuah jalan (walk) di berhingga (tak kosong)

yang suku-sukunya bergantian

titik dan sisi, sedemikian sehingga . Titik

dan

Sedangkan titik-titik

dan

adalah titik-titik akhir sisi

, untuk

berturut-turut disebut titik awal dan titik akhir disebut titik-titik internal dari

jalan

adalah banyaknya sisi dalam

jalan

berbeda, maka

dalam jalan

adalah barisan

. Jika semua sisi

.

. Panjang dari dalam

disebut jejak (trail). Jika semua titik

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 dan

disebut graf bagian dari graf . Jika

graf bagian rentang (spanning subgraf) dari

dan

, ditulis , maka

(Budayasa, 2007: 5).

, jika disebut

10

Contoh :

Gambar 2.3

Graf Bagian dari

Graf bagian dari

yang dibangun oleh

yang himpunan titiknya adalah sisi

yang dibangun oleh

yang dibangun oleh adalah

adalah sebuah graf bagian dari

Pada Gambar 2.3, graf

adalah graf

, sedangkan graf bagian dari

adalah sebuah graf bagian dari

yang himpunan sisinya

dan himpunan titiknya beranggotakan semua titik

Pada Gambar 2.3, graf

.

dan himpunan sisinya beranggotakan semua

yang mempunyai titik-titik akhir di

bagian dari graf

sisi

yang dibangun oleh

adalah graf bagian dari graf

yang terkait dengan yang dibangun oleh

. 2.1.7 Definisi Sebuah graf dua titik

dikatakan terhubung (connected graph) jika untuk setiap

yang berbeda terdapat sebuah lintasan yang menghubungkan kedua

titik tersebut. Sebaliknya graf (Rosen, 2003: 570).

disebut tidak terhubung (disconnected graph)

11

Contoh :

Gambar 2.4 Graf terhubung

dan Graf tidak terhubung

2.1.8 Definisi Sebuah komponen graf (titik dan sisi) dari . Graf

adalah sebuah graf bagian terhubung maksimal

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


.

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 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 maka

dan

di

terdapat sebuah sisi yang menghubungkannya,

disebut graf lengkap. Graf lengkap dengan


(Sutarno dkk, 2003: 82). Contoh :

Gambar 2.8 Graf Lengkap

2.2.4 Definisi Graf Bintang bintang memiliki jika

adalah graf bipartit lengkap yang berbentuk titik (Huda, 2012: 32). Sebuah graf

(himpunan titik dari graf

. Graf

disebut graf bipartit

) dapat dipartisi menjadi dua himpunan

bagian

dan

sedemikian sehingga setiap sisi dari

titik di

dan sebuah titik di . Dinotasikan

menghubungkan sebuah

bipartit dari

(Sutarno dkk,

2003: 84). Apabila

sederhana dan bipartit dengan partisi

sehingga setiap titik di

adjacent dengan setiap titik di , maka

sedemikian disebut graf

14

bipartit lengkap, dinotasikan dengan

dengan

dan

adalah banyaknya titik

di kedua partisi tersebut. Contoh :


2.3 Fungsi (Pemetaan) 2.3.1 Definisi Misalkan

dan

merupakan himpunan tidak kosong, maka cross product

dari dua buah himpunan

dan

himpunan semua pasangan terurut

yang dinotasikan dengan dengan

dan

adalah 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

Pemetaan dari himpunan

ke himpunan

ke himpunan

diberi notasi , yaitu

.

. Secara

umum pemetaan digolongkan menjadi tiga golongan.

2.3.3 Definisi Pemetaan semua elemen di sehingga

adalah pemetaan surjektif jika range dari , dengan kata lain jika untuk setiap

adalah

terdapat

(Bartle & Sherbert, 1994:13).

2.3.4 Definisi Menurut Bartle & Sherbert (1994:13) sebuah pemetaan dikatakan injektif (one-one) jika dan hanya jika untuk semua

maka

,

.

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 : Diberikan graf

sebagai berikut.

Didefinisikan

.

Gambar 2.11 Pelabelan Sisi pada Graf

17

Contoh : Diberikan graf

sebagai berikut.

Didefinisikan

Gambar 2.12 Pelabelan Total pada Graf

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 meliputi graf path

, graf sikel

, graf middle, dan graf khusus yang

, 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 , dan graf bintang

(2)

pada graf path

.

Bagaimana menentukan graf middle dari graf path bintang

, graf sikel

, dan pelabelan

nya.

18

, graf sikel

, graf

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 sikel

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

dengan cara mencari referensi dari

buku-buku dan jurnal yang berkaitan dengan pelabelan middle, dan graf khusus yang meliputi graf path bintang

, graf

, graf sikel

, dan graf

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 terupdate. Misalnya dengan cara mencarinya di situs www.google.com dengan menggunakan kata kunci pelabelan yang meliputi graf path

, graf sikel

, graf middle, dan graf khusus , 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 , dan graf bintang

3.

pada graf path

, graf sikel

, dan graf

.

4.

Memahami definisi graf middle.

5.

Membentuk graf middle dari graf path

6.

Memberikan pelabelan path

, graf sikel

.

Memberikan pelabelan bintang

.

, graf sikel

, graf sikel

, dan graf bintang

.

pada graf middle yang dibentuk dari graf

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

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 adalah fungsi

. Maka pelabelan , dengan

pada graf

berlaku

4.1.2 Definisi Jika terdapat titik

dan

di dalam graf , maka jarak antara titik

adalah banyaknya sisi yang dilewati dari titik pelabelan

, disimbolkan

sedemikian sehingga

memiliki pelabelan

maksimum. Sebuah pelabelan minimal dari

, dari graf

dari graf

menuju titik

dan

. Bilangan

adalah bilangan asli terkecil dengan

sebagai label

disebut pelabelan

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 pelabelan

dari sebuah graf. Jadi dalam pelabelan

harus digunakan sebagai label titik.

18

untuk memperoleh minimal,

19

Gambar 4.1 Graf Pada gambar 4.1 dijelaskan tentang pelabelan . Pertama, beri label 1 pada suatu titik misalkan titik

pada suatu graf . 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 karena pada titik

dan

minimal satu, maka titik graf

adalah

dan

diberi label 7,

berjarak tiga maka harus diberikan label dengan selisih diberi label

. Sehingga diperoleh label terkecil pada

.

Gambar 4.2 Graf

20

Pada Gambar 4.2 dijelaskan tentang pelabelan . Pertama, beri label

pada suatu titik misalkan titik

pada suatu graf . Karena titik

dan

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

diberi label . Karena titik

label . Sedangkan titik

dan

dan

berjarak satu maka titik

berjarak dua maka harus diberikan label dengan

selisih minimal dua, misalkan titik

diberi label

berjarak dua maka titik

. Sedangkan titik

diberi label

. Karena titik dan

dan

berjarak tiga

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

dan karena titik

dan


Sehingga diperoleh label terkecil pada graf

4.2 Pelabelan

diberi

adalah

diberi

diberi label

dan

.

.

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 , maka

titik yang dinotasikan dengan

, dengan

.

Bukti : Misalkan

adalah pelabelan

titik yang dinotasikan dengan

dan andaikan

minimal untuk graf path pada 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

kontradiksi dengan yang diasumsikan bahwa

, maka

.

Kasus II : Jika dimisalkan

, maka kontradiksi dengan yang diasumsikan

bahwa Kasus III : Jika dimisalkan diasumsikan bahwa

, maka kontradiksi dengan yang .

Kasus IV : Jika dimisalkan memberi

atau . Keduanya mungkin untuk

, yang mana kontradiksi dengan

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 jika

dan

(mod8). Menurut definisi dari untuk

dan berdasarkan Lemma 4.2.1.1 maka

.

Untuk setiap

dengan

, maka akan diproses beberapa kasus dengan

menggunakan pola pelabelan yang didefinisikan oleh setiap

dan dapat dilihat bahwa

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 adalah

Andaikan

sehingga

Jika

sedemikian sehingga memiliki derajat

Terdapat titik memiliki derajat , maka titik dan

, misalkan

.

sedemikian dan

ada

sehingga kontradiksi. Jika

, maka kemungkinan untuk

dan . Dalam salah satu kasus, diketahui yang diasumsikan bahwa

untuk

adalah

maka kontradiksi dengan

23

Kasus IV : Akan ditunjukkan bahwa pola pelabelan dari adalah

. Andakain

sehingga

dan titik

. Terdapat titik

dan

ada atau

menghilangkan sifat umum, andaikan adalah

dan

untuk

dan

Jika

dan

Jika

, maka

satunya kemungkinan untuk

, sehingga

. Jika

memiliki derajat

memiliki derajat

ada. Tanpa

ada. Kemungkinan untuk

kontradiksi dengan yang diasumsikan bahwa Selanjutnya, jika

sedemikian

maka titik

adalah

, maka dan

maka ada dan ada. Satu-

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


.



Contoh : Misalkan, suatu graf path dengan titik maka


,

24



Contoh : Misalkan, suatu graf path dengan titik dengan

dan

, maka

atau

yang dinotasikan

dan

6 Gambar 4.5 Pelabelan




Contoh : Misalkan, suatu graf path dengan titik dengan

dan

, maka

atau

yang dinotasikan

dan

6



25


pad Graf Path dengan



Contoh : Misalkan terdapat graf path dengan titik maka

, yang dinotasikan dengan

Selanjutnya pada Gambar 4.10 dijelaskan tentang pelabelan pada graf path

. Karena titik

dan

Pertama, beri label 1 pada suatu titik misalkan titik berjarak satu maka harus diberikan label dengan selisih

minimal tiga, misalkan titik maka titik



dan

dan

berjarak dua maka

harus diberikan label dengan selisih minimal dua, misalkan titik Karena titik dan

dan



berjarak dua maka titik karena pada titik .

dan

berjarak satu

diberi label .



diberi label . Kemudian untuk titik berjarak satu.

dan

diberi label

26


4.2.2 Pelabelan

pada Graf Path

pada Graf Sikel

Lemma 4.2.2.1 Misalkan

adalah bilangan bulat ganjil, jika

Misalkan

adalah pelabelan

maka

.

Bukti :

bilangan ganjil dan mungkin dengan

minimal dari

. Andaikan

di mana

adalah

Maka hanya pelabelan yang

sebagai bilangan bulat maksimum adalah sebagai berikut:

dan Dapat dilihat bahwa Dari pelabelan sisa sikel karena label

dan dan

adalah pelabelan untuk sikel genap. semua gagal sebagai pelabelan pada

yang hilang harus lebih besar daripada yang diasumsikan

. Oleh karena itu, tidak ada pelabelan pada

dengan

ganjil dan

sedemikian sehingga

minimal yang berada

27

Lemma 4.2.2.2 Untuk setiap graf sikel dengan

maka

.

Bukti : Akan ditunjukkan bahwa pola pelabelan dari Kemudian, misalkan

adalah pelabelan

. Diberikan berdekatan dengan

adalah

minimal dari

sedangkan

dan

.

dan andaikan

adalah dua titik yang

. Maka kemungkinan untuk

)} adalah

. Kasus I : Jika misalkan bahwa

maka kontradiksi dengan yang diasumsikan

Jika diambil

karena selisih label pada titik Kasus II : {

maka tidak memenuhi definisi 4.1.1 dan atau

Jika dimisalkan bahwa

hanya 1.


Jika diambil

karena selisih label pada titik

maka tidak memenuhi definisi 4.1.1 dan

hanya 1. Oleh karena itu

Contoh :



.

28

Lemma 4.2.2.3 Untuk setiap graf sikel dengan

maka

Bukti : Dari teorema 4.2.1.2 dapat diketahui bahwa Misalkan

adalah pelabelan

Diberikan dengan

minimal dari

dan misalkan

dan

karena dan andaikan

adalah dua titik yang berdekatan


adalah

dan

Kasus I : Jika dimisalkan


bahwa Kasus II :

atau

Jika dimisalkan

:


bahwa Karena

tidak mungkin terjadi, maka didapatkan

Menurut Lemma 4.2.2.1 untuk sikel ganjil, dapat dilihat bahwa diperoleh

Sehingga, pola pelabelan Oleh karena itu

. Maka

menunjukkan bahwa

29

Contoh :



Lemma 4.2.2.4 Untuk graf sikel dengan

maka

Bukti : Akan ditunjukkan bahwa pola pelabelan dari . Misalkan andaikan

adalah pelabelan

Diberikan

titik yang berdekatan dengan , dan

adalah

minimal dari

, dan misalkan

dan


dan

adalah dua adalah

.

Kasus I : Jika dimisalkan

dan

Untuk

diketahui

,

maka kontradiksi dengan Kasus II :

atau

Jika dimisalkan bahwa

Oleh karena itu

maka kontradiksi dengan yang diasumsikan .

30

Contoh :



Lemma 4.2.2.5 Untuk graf sikel dengan

maka

Misalkan

adalah himpunan titik dari

Bukti :

dan misalakan kemungkinan nilai pada

adalah pelabelan

nilai untuk

minimal dari

berada di dalam

terbesar antara dua titik yang berada di dalam

. Andaikan , maka

Karena jarak

adalah , tidak ada kemungkinan

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 ada

label yang dapat digunakan dari

menjadi berlabel dengan nilai yang diasumsikan bahwa pelabelan

. Maka paling banyak

, seharusnya titik yang tak berlabel , sehigga kontradiksi dengan yang

Dengan demikian menunjukkan bahwa

Sehingga, pola 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.


adalah bilangan bulat genap. Jika

bilangan bulat non negatif

dan

, maka terdapat

sedemikian sehingga

.

Bukti : Misalkan genap. Maka Kasus I :

dan (mod

atau

(mod

adalah bilangan bulat

. Andaikan bahwa

(mod ) :

Jika terdapat bilangan bulat Ini meliputi

sedemikian sehingga di mana

dan

. Karena . Maka,

.

32

Kasus II :

(mod ) :

Jika terdapat bilangan bulat meliputi

. Karena

Maka

sedemikian sehingga dan

(mod ), didapatkan

Dari ini, terdapat bahwa

dan

Ini .

di mana

Maka, Oleh karena itu, jika

adalah bilangan bulat genap dan

terdapat bilangan bulat non negatif

dan

maka

sedemikian sehingga

Contoh : Misalkan genap. Jika

dan


, maka terdapat bilangan bulat non negatif

dan

sedemikian

sehingga

Sehingga diperoleh


adalah bilangan bulat ganjil. Jika

terdapat bilangan bulat non negatif

dan

dan

sedemikian sehingga

, maka

33

Bukti : Misalkan ganjil. Maka

dan (mod ) atau

Kasus I :


(mod ). Andaikan

dan

.

(mod ) :

Jika terdapat bilangan bulat meliputi bahwa

sedemikian sehingga

. Karena

mengimplikasikan bahwa

didapatkan

di mana

dan

. Ini Ini Maka,

. Kasus II :

(mod ) :

Jika terdapat bilangan bulat

sedemikian sehingga

mengimplikasikan bahwa (mod

Karena

, didapatkan

mana

dan Oleh karena itu, jika dan

maka

Maka

Ini dan

Karena

di

maka adalah bilangan bulat ganjil sedemikian sehingga di mana

dan

bilangan bulat non

negatif. Contoh : Misalkan ganjil. Jika

dan dan

sedemikian sehingga


maka terdapat bilangan bulat non negatif

dan

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 untuk semua

adalah pelabelan

minimal dari

. Kemudian, untuk setiap

, sedemikian sehingga

sedemikian sehingga

adalah pelabelan dengan

minimal dari

dan Dengan demikian,

untuk setiap dalam

dengan

dan maka

Karena terdapat Begitu juga, karena

, sedemikian sehingga untuk setiap Secara rekursif, maka akan diperoleh :

di

35

. Oleh karena itu,

Teorema 4.2.2.9 Untuk setiap graf sikel,

dengan

maka

Bukti : Misalkan

dan

adalah titik dari

sehingga untuk

dan

sedemikian

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

Lemma 4.2.2.4, secara berturut-turut yaitu: untuk dan untuk

digunakan

pada Lemma 4.2.2.2 dan digunakan Dapat dilihat bahwa

36

pelabelan yang digunakan untuk dengan

dapat diulang secara tak terbatas untuk setiap

perkalian dari . Demikian juga, pelabelan yang digunakan untuk

dapat diulang secara tak terbatas untuk setiap itu, pelabelan dari

dan

dengan

perkalian dari . Selain

dapat digabung bersama menjadi label

berikut :

seperti

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 Oleh karena itu,

untuk setiap

Kasus III : ganjil dan

dan

.

genap.

atau

Berdasarkan Lemma 4.2.2.3 diketahui bahwa bardasarkan Teorema 4.2.1.2 untuk graf path diketahui bahwa karena

kemudian untuk

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,

Dapat dilihat bahwa pelabelan dari setiap

dengan

dapat diulang secara tak terbatas untuk

perkalian dari . Serta dapat dikombinasikan pelabelan untuk

dengan pelabelan untuk label

dilabeli dengan

seperti berikut :

yang digunakan dalam Lemma 4.2.2.2 menjadi 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

setiap

, dimana

dan

. Untuk

diperoleh

untuk

dapat diketahui bahwa

(berasal dari Lemma 4.2.2.2 dan Lemma 4.2.2.5). Didefinisikan sedemikian sehingga

untuk

. Karena max

Kasus IV : Berdasarkan Lemma 4.2.2.5, maka diperroleh Contoh : Untuk setiap graf sikel yang dinotasikan dengan maka

, dengan

, jika

.



, jika

maka Contoh : Untuk setiap graf sikel yang dinotasikan dengan genap maka

. Misalkan

maka

, dengan .

, jika

38



, jika

maka

Contoh : Untuk setiap graf sikel yang dinotasikan dengan ganjil dan

atau

maka


, dengan

, jika

maka

pada Graf Sikel dengan maka

, jika

39

Contoh : Misalkan untuk setiap graf sikel yang dinotasikan dengan , jika

, dengan

maka

Selanjutnya pada Gambar 4.18 pelabelan

pada graf sikel

Pertama, beri label 1 pada suatu titik misalkan titik

. Karena titik tiga, misalkan titik

dan

berjarak satu maka harus diberi label dengan selisih


titik


label

. Sedangkan pada titik

dan dan

karena pada titik

dan


berjarak satu maka


diberi

berjarak tiga maka harus diberi label

dengan selisih minimal satu, misalkan titik berjarak tiga maka titik

dan


diberi label 5. Kemudian untuk titik

dan

diberi label

berjarak tiga.

pada Graf Sikel dengan maka

, jika

,

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 dan

titik dan

sisi. Misalkan

.

Akan dibuktikan bahwa titik label pada himpunan Teorema 4.2.3.1. Misalkan

adalah pelabelan

dan

memenuhi

minimal dari

dan untuk setiap pasangan dari titik di dalam . Misalkan

. dengan

yaitu

dengan

.

berdekatan dengan setiap

. Sehingga diperlukan

, maka . Kemudian, karena

, maka

Oleh karena itu,

minimal sehingga diperoleh titik

adalah

. Pelabelan pada

berikut sama dengan pelabelan pada titik

maka diperlukan

dengan

menjadi ganjil karena

adalah minimal. Dengan demikian, Karena setiap

Jika

maka sama halnya untuk untuk setiap

maka tiap

dengan

yaitu : karena

untuk menjadi genap. Dengan demikian, .

Sehingga

. Oleh karena itu

diperoleh .

41

Contoh : Pada Gambar 4.19 berikut ini akan diberikan contoh pelabelan pada graf bipartit lengkap. Misalkan terdapat graf bipartit lengkap dengan titik dan


, maka

. Selanjutnya akan dijelaskan tentang pelabelan lengkap dan

pada graf bipartit

. Pertama, beri label 1 pada suatu titik misalkan titik

. Karena titik

berjarak dua maka harus diberikan label dengan selisih minimal dua,

misalkan titik


dan



dan

Sedangkan pada titik

berjarak satu maka harus diberikan label dengan

dan

berjark dua maka titik

selisih minimal tiga, misalkan titik diberi label

karena pada titik


diberi label dan

diberi label .

. Kemudian untuk titik

berjarak dua.

pada Graf Bipartit Lengkap

42

Akibat 4.2.3.2 Untuk graf bintang atau

, maka

.

Bukti : Menurut definisi, graf bintang atau berbentuk

. Oleh karena itu,

adalah graf bipartit lengkap yang .

Contoh : Pada gambar 4.20 berikut ini akan diberikan contoh pelabelan pada graf bintang. Misalkan terdapat graf bintang dengan titik dinotasikan dengan

atau

, maka

dijelaskan tentang pelabelan pada suatu titik misalkan titik

. Selanjutnya akan

pada graf bintang . Karena titik

dan

. Pertama, beri label berjarak satu maka harus

diberikan label dengan selisih minimal tiga, misalkan titik Sedangkan pada titik

dan

titik dan

diberi label

diberi label


. Kemudian untuk titik

berjarak dua.

diberi label

.

berjarak dua maka harus diberikan label dengan

selisih minimal dua, misalkan titik berjarak dua maka titik

yang

. Karena titik dan

diberi label

dan

berjarak dua maka karena pada titik

43


4.3

dan pelabelan

pada Graf Bintang

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 dan sisi

(ii)

incident pada titik yang sama di graf . adjacent dengan

incident dengan titik

4.4

karena sisi

karena sisi (Vaidya & Bantva, 2010:104).

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

graf yang mempunyai himpunan titik adalah adjacent di

jadi himpunan titik

{

.


titik

karena sisi incident di titik





adjacent dengan dan sisi (ii)

Dua

jika:

(i)

adalah


adjacent dengan incident dengan titik

karena sisi .


karena sisi .

adjacent dengan

karena sisi


.


karena sisi .

adalah

45

adjacent dengan

karena sisi


.


karena sisi .


karena sisi .

adjacent dengan

karena sisi


.


karena sisi .


karena sisi .

Berikut adalah pembentukan graf middle dari graf path ditunjukkan pada Gambar 4.21.

Gambar 4.21 Graf

dan Graf

yang

46

Pada gambar berikut ini akan diberikan contoh pelabelan

pada

graf middle yang dibentuk dari graf path berdasarkan definisi 4.3.1. Contoh : Misalkan, suatu graf path dengan titik


Berikut adalah pembentukan graf middle dari graf path

.

yang ditunjukkan pada

Gambar 4.22.

Gambar 4.22 Graf Pada Gambar 4.23 diberikan graf graf

dan diperoleh

Gambar 4.23 Graf Contoh :

dan Graf

, ditunjukkan pelabelan .

dan Pelabelan

pada Graf

pada

47

Misalkan, suatu graf path dengan titik



.


Gambar 4.24.

Gambar 4.24 Graf

dan Graf

Pada Gambar 4.25 diberikan graf

, ditunjukkan pelabelan

graf

.

dan diperoleh

Gambar 4.25 Graf

dan Pelabelan

pada

pada Graf

Contoh : Misalkan, suatu graf path dengan titik


Berikut adalah pembentukan graf middle dari graf path Gambar 4.26.

.


48

Gambar 4.26 Graf

dan Graf



graf

.

dan diperoleh

pada

7

12 Gambar 4.27 Graf

dan Pelabelan

pada Graf




Gambar 4.28 Graf

dan Graf

.


49



graf

.

dan diperoleh

Gambar 4.29 Graf

dan Pelabelan

pada

pada Graf




.


Gambar 4.30.

Gambar 4.30 Graf

dan Graf

Selanjutnya pada Gambar 4.31 dijelaskan tentang pelabelan graf middle dari graf

dan diperoleh

suatu titik misalkan titik

. Karena titik

. Pertama, beri label dan

pada pada

berjarak satu maka harus

50

diberikan label dengan selisih minimal tiga, misalkan titik Sedangkan titik

dan


maka titik


diberi label

. Karena titik dan

dan

berjarak dua





diberi label . Karena titik Kemudian untuk titik

dan

dan

diberi label

.

berjarak tiga maka harus diberikan label dengan selisih

minimal satu, misalkan titik maka titik

.

berjarak dua maka harus diberikan label dengan selisih

minimal dua, misalkan titik

Sedangkan titik

diberi label

dan

diberi label

dan

dan

berjarak satu



diberi label .

karena pada titik

berjarak dua.


dan

pada Graf




.


51

Gambar 4.32 Graf

dan Graf

Pada Gambar 4.33 ditunjukkan pelabelan diperoleh

pada graf

dan

.

Gambar 4.33 Pelabelan Pada pelabelan Gambar 4.33 di atas, label

pada Graf 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


himpunan sisi

dan


mempunyai himpunan titik {

jadi himpunan titik . Dua titik adalah adjacent di

(i)

adjacent dengan

adalah jika:

karena sisi

dan sisi

di titik adjacent dengan

dan sisi


adjacent dengan dan sisi (ii)

adalah graf yang



karena sisi .

adjacent dengan

karena sisi


.


karena sisi .


karena sisi .

53

adjacent dengan

karena sisi


.

adjacent dengan

karena sisi


.

Berikut adalah pembentukan graf middle dari graf sikel


Gambar 4.34.

Gambar 4.34 Graf

dan Graf

Pada gambar berikut ini akan diberikan contoh pelabelan

pada

graf middle yang dibentuk dari graf sikel berdasarkan definisi 4.3.1. Contoh : Misalkan, suatu graf sikel dengan titik Pada Gambar 4.35 diberikan graf diperoleh

.

, pelabelan

yang dinotasikan dengan pada graf

. dan

54

1

Gambar 4.35 Graf

dan Pelabelan

pada Graf

Contoh : Misalkan, suatu graf sikel dengan titik



Gambar 4.36 Graf

dan Graf

.


55


pada

dan

.


pada Graf

Contoh : Misalkan, suatu graf sikel dengan titik


Berikut adalah pembentukan graf middle dari graf sikel Gambar 4.38.

.


56

Gambar 4.38 Graf

dan Graf

Selanjutnya pada gambar 4.39 dijelaskan tentang pelabelan graf middle dari graf

dan diperoleh

suatu titik misalkan titik

. Karena titik

. Pertama, beri label dan

dan

dan

berjarak tiga maka titik

berjarak tiga maka titik

tiga maka titik

diberi label


diberi label . Sedangkan titik

dan

dan


.


dan

dan

diberi label

berjarak

berjarak satu maka

harus diberikan label dengan selisih minimal tiga, misalkan titik Karena titik

pada

berjarak tiga maka harus

diberikan label dengan selisih minimal satu, misalkan titik Karena titik

pada

diberi label . . Sedangkan titik

berjarak dua maka harus diberikan label dengan selisih minimal dua,

misalkan titik

diberi label

. Karena titik

dan


57

diberi label . Kemudian untuk titik

diberi label

karena pada titik

dan

berjarak dua.


pada Graf

Contoh: Misalkan, suatu graf sikel dengan titik


adalah pembentukan graf middle dari graf sikel 4.40.

. Berikut

yang ditunjukkan pada Gambar

58

Gambar 4.40 Graf

dan Graf

Pada Gambar 4.41 ditunjukkan pelabelan

pada graf

dan

diperoleh

14


pada Graf 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

pembentukan graf path

dan graf path

middle dari graf bintang dimulai dari

sudah dijelaskan pada

, maka contoh pembentukan graf

.

Contoh : Graf bintang


dan himpunan sisi


yang mempunyai himpunan titik adalah

{

adalah graf

jadi himpunan titik . Dua titik adalah adjacent di

jika: (i)





60

adjacent dengan

karena sisi

dan sisi

(ii)

incident

adjacent dengan

di titik

karena sisi


.

adjacent dengan

karena sisi


.

adjacent dengan

karena sisi


.

Berikut adalah pembentukan graf middle dari graf bintang

yang

ditunjukkan pada Gambar 4.42.

Gambar 4.42 Graf

dan Graf

Pada gambar berikut ini akan diberikan contoh pelabelan graf middle yang dibentuk dari graf bintang berdasarkan definisi 4.3.1.

pada

61

Contoh : Misalkan, suatu graf bintang dengan titik dan diperoleh

. Selanjutnya akan dijelaskan tentang pelabelan

pada graf bintang titik


. Karena titik

dan

. Pertama, beri label

pada suatu titik misalkan

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 titik


label

. Karena titik

Sedangkan titik

dan

dan

dan



diberi label

diberi label . Kemudian titik

berjarak tiga.

Gambar 4.43 Graf

diberi .

berjarak tiga maka harus diberikan label dengan selisih

minimal satu, misalkan titik karena titik

dan

dan Pelabelan

pada Graf

diberi label

62

Contoh: Misalkan, suatu graf bintang dengan titik


. Berikut adalah pembentukan graf middle dari graf bintang

yang

ditunjukkan pada 4.44.

Gambar 4.44 Graf

dan Graf


pada

dan

.


pada Graf 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

.

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

mempunyai mempunyai

, ,

dan 2. Pelabelan

, ,

mempunyai

. untuk

, ,

,

mempunyai

mempunyai

mempunyai

mempunyai

mempunyai

pada graf sikel

mempunyai

untuk

mempunyai

,

mempunyai

mempunyai

, ,

mempunyai

. 3. Pelabelan

pada graf bintang

untuk

mempunyai

.

5.1.2

Hasil pelabelan graf bintang

pada graf middle dari graf path adalah sebagai berikut.

64

, graf sikel

,

65

1. Pelabelan

pada graf middle dari graf path

mempunyai

,

mempunyai

,

mempunyai

.

2. Pelabelan

,

mempunyai

.

3. Pelabelan mempunyai

mempunyai

,

mempunyai

dan

pada graf middle dari graf sikel

mempunyai

untuk

mempunyai

untuk dan

pada graf middle dari graf bintang

untuk

.

5.2 Saran 1. Dalam penelitian ini pembahasan mengenai pelabelan pembentukan graf middle hanya meliputi graf path bintang

, graf sikel

dan , dan graf

. Penulis berharap penulis lain dapat menemukan pelabelan

dan pembentukan graf middle dari graf khusus lainnya.

2. Disarankan penulis lain dapat mengaplikasikan pelabelan kehidupan nyata.

pada

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 220: 57–66.

)-labelings of Graphs. Discrete Mathematics,

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/vol9n2/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.

66

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): 104107. 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/vol10n1/paper12/v10n1-12pd.pdf. [diakses 12-01-2012].

Bartle, G. R & D. R. Sherbert. 1994. Introduction to Real Analysis. Singapore: Jhon Wiley & Sons, INC.

MIDDLE PADA BEBERAPA GRAF KHUSUS

Recommend Documents