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
Gambar 4.4 Pelabelan
pada Graf Path dengan
......................... 27
Gambar 4.5 Pelabelan
pada Graf Path dengan
......................... 28
Gambar 4.6 Pelabelan
pada Graf Path dengan
......................... 28
Gambar 4.7 Pelabelan
pada Graf Path dengan
......................... 28
Gambar 4.8 Pelabelan
pad Graf Path dengan
........................... 28
x
xi
Gambar 4.9 Pelabelan
pada Graf Path dengan
......................... 29
Gambar 4.10 Pelabelan
pada Graf Path
......................................... 29
Gambar 4.11 Pelabelan
pada Graf Sikel dengan
.............. 31
Gambar 4.12 Pelabelan
pada Graf Sikel dengan
.............. 33
Gambar 4.13 Pelabelan
pada Graf Sikel dengan
.............. 34
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
maka
, jika
............................................................................. 42
Gambar 4.18 Pelabelan
pada Graf Sikel dengan
maka
, jika
,
........................................................................... 43
Gambar 4.19 Pelabelan
pada Graf Bipartit Lengkap
Gambar 4.20 Graf Bintang
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
dan Pelabelan dan Graf
................ 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
dan Pelabelan dan Graf
Gambar 4.31 Pelabelan Gambar 4.32 Graf
dan Graf
Gambar 4.35 Graf Gambar 4.36 Graf
Gambar 4.37 Pelabelan Gambar 4.38 Graf
Gambar 4.39 Pelabelan Gambar 4.40 Graf
Gambar 4.41 Pelabelan Gambar 4.42 Graf Gambar 4.43 Graf Gambar 4.44 Graf
Gambar 4.45 Pelabelan
.......................................... 59
.......................................... 61
.......................................... 62
.............................................................. 64
dan Pelabelan dan Graf
................ 58
............................................................... 62 pada Graf
dan Graf
pada Graf
............................................................... 60 pada Graf
dan Graf
........................................... 55
................................................................ 59 pada Graf
dan Graf
........................................... 54
................................................................ 57
dan Pelabelan dan Graf
................ 53
................................................................ 55 pada Graf
dan Graf
pada Graf
................................................................. 53 pada Graf
Gambar 4.33 Pelabelan Gambar 4.34 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
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 Jika titik-titik pada
titik dinotasikan dengan
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
titik dinotasikan 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 :
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
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
berjarak satu maka titik
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
yang dinotasikan dengan
.
Gambar 4.3 Pelabelan
pada Graf Path dengan
Contoh : Misalkan, suatu graf path dengan titik maka
yang dinotasikan dengan
,
24
Gambar 4.4 Pelabelan
pada Graf Path dengan
Contoh : Misalkan, suatu graf path dengan titik dengan
dan
, maka
atau
yang dinotasikan
dan
6 Gambar 4.5 Pelabelan
pada Graf Path dengan
4 Gambar 4.6 Pelabelan
pada Graf Path dengan
Contoh : Misalkan, suatu graf path dengan titik dengan
dan
, maka
atau
yang dinotasikan
dan
6
7 Gambar 4.7 Pelabelan
pada Graf Path dengan
25
Gambar 4.8 Pelabelan
pad Graf Path dengan
2 Gambar 4.9 Pelabelan
pada 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
diberi label . Karena titik
diberi label . Sedangkan pada titik
dan
dan
berjarak dua maka
harus diberikan label dengan selisih minimal dua, misalkan titik Karena titik dan
dan
berjarak satu maka titik
berjarak satu maka titik
berjarak dua maka titik karena pada titik .
dan
berjarak satu
diberi label .
diberi label . Karena titik
diberi label . Sedangkan pada titik
diberi label . Kemudian untuk titik berjarak satu.
dan
diberi label
26
7 Gambar 4.10 Pelabelan
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.
maka kontradiksi dengan yang diasumsikan
Jika diambil
karena selisih label pada titik
maka tidak memenuhi definisi 4.1.1 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 Misalkan
adalah pelabelan
Diberikan dengan
minimal dari
dan misalkan
dan
karena dan andaikan
adalah dua titik yang berdekatan
. Maka kemungkinan untuk
adalah
dan
Kasus I : Jika dimisalkan
maka kontradiksi dengan yang diasumsikan
bahwa Kasus II :
atau
Jika dimisalkan
:
maka kontradiksi dengan yang diasumsikan
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 :
Gambar 4.12 Pelabelan
pada Graf Sikel dengan
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
. Maka kemungkinan untuk
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 :
Gambar 4.13 Pelabelan
pada Graf Sikel dengan
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 :
1 Gambar 4.14 Pelabelan
pada Graf Sikel dengan
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
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
adalah bilangan bulat
, maka terdapat bilangan bulat non negatif
dan
sedemikian
sehingga
Sehingga diperoleh
Lemma 4.2.2.7 Misalkan
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 :
adalah bilangan bulat
(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
adalah bilangan bulat
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
.
Gambar 4.15 Pelabelan
pada Graf Sikel dengan
, jika
maka Contoh : Untuk setiap graf sikel yang dinotasikan dengan genap maka
. Misalkan
maka
, dengan .
, jika
38
Gambar 4.16 Pelabelan
pada Graf Sikel dengan
, jika
maka
Contoh : Untuk setiap graf sikel yang dinotasikan dengan ganjil dan
atau
maka
Gambar 4.17 Pelabelan
, 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
diberi label . Karena titik
titik
diberi label . Karena titik
label
. Sedangkan pada titik
dan dan
karena pada titik
dan
Gambar 4.18 Pelabelan
berjarak satu maka
berjarak satu maka titik
diberi
berjarak tiga maka harus diberi label
dengan selisih minimal satu, misalkan titik berjarak tiga maka titik
dan
diberi label . Karena titik
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
yang dinotasikan dengan
, 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
diberi label . Karena titik
dan
berjarak dua maka titik
diberi label . Karena titik
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
Gambar 4.19 Pelabelan
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
diberi label . Karena titik
. 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
Gambar 4.20 Graf Bintang
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
{
.
adjacent dengan dan sisi
titik
karena sisi incident di titik
adjacent dengan dan sisi
karena sisi incident di titik
adjacent dengan dan sisi
karena sisi incident di titik
adjacent dengan dan sisi (ii)
Dua
jika:
(i)
adalah
karena sisi incident di titik
adjacent dengan incident dengan titik
karena sisi .
adjacent dengan incident dengan titik
karena sisi .
adjacent dengan
karena sisi
incident dengan titik
.
adjacent dengan incident dengan titik
karena sisi .
adalah
45
adjacent dengan
karena sisi
incident dengan titik
.
adjacent dengan incident dengan titik
karena sisi .
adjacent dengan incident dengan titik
karena sisi .
adjacent dengan
karena sisi
incident dengan titik
.
adjacent dengan incident dengan titik
karena sisi .
adjacent dengan incident dengan titik
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
yang dinotasikan dengan
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
yang dinotasikan dengan
Berikut adalah pembentukan graf middle dari graf path
.
yang ditunjukkan pada
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
yang dinotasikan dengan
Berikut adalah pembentukan graf middle dari graf path Gambar 4.26.
.
yang ditunjukkan pada
48
Gambar 4.26 Graf
dan Graf
Pada Gambar 4.27 diberikan graf
, ditunjukkan pelabelan
graf
.
dan diperoleh
pada
7
12 Gambar 4.27 Graf
dan Pelabelan
pada Graf
Contoh : Misalkan, suatu graf path dengan titik
yang dinotasikan dengan
Berikut adalah pembentukan graf middle dari graf path Gambar 4.28.
Gambar 4.28 Graf
dan Graf
.
yang ditunjukkan pada
49
Pada Gambar 4.29 diberikan graf
, ditunjukkan pelabelan
graf
.
dan diperoleh
Gambar 4.29 Graf
dan Pelabelan
pada
pada Graf
Contoh : Misalkan, suatu graf path dengan titik
yang dinotasikan dengan
Berikut adalah pembentukan graf middle dari graf path
.
yang ditunjukkan pada
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
diberi label . Karena titik
maka titik
diberi label . Karena titik
diberi label
. Karena titik dan
dan
berjarak dua
berjarak dua maka titik
berjarak satu maka titik
diberi label . Karena titik
diberi label . Karena titik
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
berjarak dua maka titik
berjarak dua maka titik
diberi label .
karena pada titik
berjarak dua.
Gambar 4.31 Pelabelan
dan
pada Graf
Contoh : Misalkan, suatu graf path dengan titik
yang dinotasikan dengan
Berikut adalah pembentukan graf middle dari graf path Gambar 4.32.
.
yang ditunjukkan pada
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
mempunyai himpunan titik
himpunan sisi
dan
. Graf middle dari graf
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
karena sisi incident di titik
adjacent dengan dan sisi (ii)
adalah graf yang
karena sisi incident di titik
adjacent dengan incident dengan titik
karena sisi .
adjacent dengan
karena sisi
incident dengan titik
.
adjacent dengan incident dengan titik
karena sisi .
adjacent dengan incident dengan titik
karena sisi .
53
adjacent dengan
karena sisi
incident dengan titik
.
adjacent dengan
karena sisi
incident dengan titik
.
Berikut adalah pembentukan graf middle dari graf sikel
yang ditunjukkan pada
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
yang dinotasikan dengan
Berikut adalah pembentukan graf middle dari graf path Gambar 4.36.
Gambar 4.36 Graf
dan Graf
.
yang ditunjukkan pada
55
Pada Gambar 4.37 ditunjukkan pelabelan diperoleh
pada
dan
.
Gambar 4.37 Pelabelan
pada Graf
Contoh : Misalkan, suatu graf sikel dengan titik
yang dinotasikan dengan
Berikut adalah pembentukan graf middle dari graf sikel Gambar 4.38.
.
yang ditunjukkan pada
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 . Karena titik
diberi label . Sedangkan titik
dan
dan
berjarak satu maka titik
.
diberi label . Karena titik
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
berjarak dua maka titik
57
diberi label . Kemudian untuk titik
diberi label
karena pada titik
dan
berjarak dua.
Gambar 4.39 Pelabelan
pada Graf
Contoh: Misalkan, suatu graf sikel dengan titik
yang dinotasikan dengan
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
Gambar 4.41 Pelabelan Pada pelabelan Gambar 4.41 di atas, label
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
mempunyai himpunan titik
dan himpunan sisi
. Graf middle dari graf
yang mempunyai himpunan titik adalah
{
adalah graf
jadi himpunan titik . Dua titik adalah adjacent di
jika: (i)
adjacent dengan dan sisi
adjacent dengan dan sisi
karena sisi incident di titik
karena sisi incident di titik
60
adjacent dengan
karena sisi
dan sisi
(ii)
incident
adjacent dengan
di titik
karena sisi
incident dengan titik
.
adjacent dengan
karena sisi
incident dengan titik
.
adjacent dengan
karena sisi
incident dengan titik
.
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
yang dinotasikan dengan
. 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
diberi label . Karena titik
label
. Karena titik
Sedangkan titik
dan
dan
dan
berjarak satu maka titik
berjarak satu maka titik
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
yang dinotasikan dengan
. Berikut adalah pembentukan graf middle dari graf bintang
yang
ditunjukkan pada 4.44.
Gambar 4.44 Graf
dan Graf
Pada Gambar 4.45 ditunjukkan pelabelan diperoleh
pada
dan
.
Gambar 4.45 Pelabelan Pada pelabelan Gambar 4.45 di atas, label
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.