KLASIFIKASI GRAF PETERSEN BERBILANGAN KROMATIK LOKASI EMPAT ATAU LIMA (Tesis)
Oleh : Devriyadi Saputra S NPM. 1427031001
MAGISTER MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG BANDAR LAMPUNG 2017
A
Judul Tesis
: KLASIFIKASI GRAF PETERSEN BERBILANGAN KROMATIK LOKASI EMPAT ATAU LIMA
Nama Mahasiswa
: Devriyadi Saputra S
Nomor Pokok Mahasiswa : 1427031001 Magister
: Matematika
Jurusan
: Matematika
Fakultas
: Matematika dan Ilmu Pengetahuan Alam
MENYETUJUI 1.
Komisi Pembimbing
Pembimbing I
Pembimbing II
Dr. Asmiati, S.Si., M.Si.
Drs. Mustofa Usman, M.A, Ph.D.
NIP. 19760411 200012 2 001
NIP. 19570101 198404 1 001
2.
Ketua Jurusan Matematika
Drs. Tiryono Ruby, M.Sc., Ph.D. NIP.19620704 198803 1 002
ii
MENGESAHKAN 1.
Tim Penguji
Ketua
: Dr. Asmiati, S.Si.,M.Si. NIP. 19760411 200012 2 001
Sekretaris
: Drs. Mustofa Usman, M.A., Ph.D. NIP. 19570101 198404 1 001
Penguji
……………………
: Dra. Wamiliana, M.A., Ph.D. NIP. 19631108 198902 2 001
2.
……………………
……………………
Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam
Prof. Warsito, S.Si., D.E.A., Ph.D. NIP. 19690530 199512 1 001
3.
Direktur Pascasarjana Universitas Lampung
Prof. Dr. Sudjarwo, M.S. NIP. 19530528 198103 1 002
Tanggal Lulus Ujian Tesis : 6 Januari 2017 iii
PERNYATAAN TESIS MAHASISWA Yang bertanda tangan di bawah ini :
Nama
: Devriyadi Saputra S
NPM
: 1427031001
Magister
: Matematika
Jurusan
: Matematika
Dengan ini menyatakan bahwa penelitian ini adalah hasil pekerjaan saya sendiri, dan sepanjang pengetahuan saya tidak berisi materi yang telah dipublikasikan atau ditulis orang lain atau telah dipergunakan dan diterima sebagai sebagai persyaratan penyelesaian pada universitas atau insitusi lain.
Bandar Lampung, Januari 2017 Yang Menyatakan,
Devriyadi Saputra S NPM. 1427031001
iv
MOTTO “Kita akan sukses jika belajar dari kesalahan” “Semua mimpimu akan terwujud asalkan kamu punya keberanian untuk mengejarnya”
v
PERSEMBAHAN Dengan mengucap puji syukur kehadirat Allah SWT kupersembahkan karya ini untuk : 1.
Kedua orang tua yang memotivasi dalam penyelesaian penelitian ini.
2.
Istriku Lina Dewi Kurniawati yang telah turut membantu dan memotivasi dalam penyelesaian penelitian ini.
3.
Anakku Alif Devna Alfaeyza yang menjadi motivasiku untuk segera menyelesaikan penelitian ini.
4.
Teman-teman dewan guru dan Siswa/I SMKN 1 Mesuji Timur yang mendukung saya untuk segera menyelesaikan penelitian ini.
vi
SANWACANA Puji syukur kehadirat Allah SWT atas rahmat dan karunia-Nya sehingga tesis ini dapat diselesaikan. Tesis dengan judul “Klasifikasi Graf Petersen Berbilangan Kromatik Lokasi Empat atau Lima” disusun sebagai salah satu syarat memperoleh gelah Magister Sains (M.Si.) di Universitas Lampung. Dengan ketulusan hati penulis ingin mengucapkan terima kasih kepada : 1.
Dr. Asmiati, S.Si., M.Si. selaku Dosen Pembimbing I, terima kasih untuk bimbingan dan kesediaan waktunya selama penyusunan tesis ini.
2.
Drs. Mustofa Usman, M.A., Ph.D. selaku Dosen Pembimbing II, terima kasih untuk bantuan dan masukannya selama penyusunan tesis.
3.
Dra. Wamiliana, M.A., Ph.D. selaku Dosen Penguji, terima kasih atas kesediannya untuk menguji, memberikan saran dan kritik yang membangun dalam penyelesaian tesis ini.
4.
Drs. Tiryono Ruby, M.Sc., Ph.D. selaku Pembimbing Akademik dan Ketua Jurusan Matematika FMIPA Universitas Lampung atas bimbingan dan nasehatnya selama ini.
5.
Seluruh dosen dan karyawan Prodi Magister Matematika.
6.
Terima kasih yang sedalam-dalamnya untuk orang tua saya yang telah mendidik saya sampai sekarang dan doa restu yang tak pernah putus.
7.
Terima kasih juga kepada istri dan anak saya yang telah menyemangati saya sampai sekarang.
8.
Teman terdekat seatap seperjuangan, terimakasih atas kebersamaannya dan motivasinya.
9.
Semua pihak yang telah membantu dalam penyusunan tesis ini.
10.
Almamater tercinta Universitas Lampung.
Akhir kata, semoga tesis ini dapat bermanfaat bagi kita semua. Bandar Lampung,
Januari 2017
Penulis
Devriyadi Saputra S vii
KLASIFIKASI GRAF PETERSEN BERBILANGAN KROMATIK LOKASI EMPAT ATAU LIMA
Oleh : Devriyadi Saputra S NPM. 1427031001
ABSTRAK Misalkan c suatu pewarnaan titik pada graf G dengan c(u) ≠ c(v) untuk u dan v bertetangga di G. Misalkan Ci himpunan titik-titik yang diberi warna i, yang selanjutnya disebut kelas warna, maka Π = {C1, C2, …, Ck} adalah himpunan yang terdiri dari kelas-kelas warna dari V(G). Kode warna cΠ(v) dari v adalah kpasang terurut (d(v, C1), d(v, C2), …, d(v, Ck)) dengan d(v,Ci) = min {d(v, x)|x Ci} untuk 1 ≤ i ≤ k. Jika setiap G mempunyai kode warna yang berbeda, maka c disebut pewarnaan lokasi G. Banyaknya warna minimum yang digunakan untuk pewarnaan lokasi disebut bilangan kromatik lokasi dari G, dan dinotasikan dengan . Berdasarkan hasil penelitian yang sudah dilakukan, diperoleh bilangan kromatik lokasi Graf Petersen Pn,1 adalah 4 untuk n ganjil dan 5 untuk lainnya; (
)
dan
(
)
untuk 5 ≤ n ≤ 20.
Kata Kunci : Graf, bilangan kromatik lokasi, Graf Petersen
viii
DAFTAR ISI Halaman Judul ................................................................................................. i Persetujuan ...................................................................................................... ii Pengesahan ...................................................................................................... iii Pernyataan ....................................................................................................... iv Motto ............................................................................................................... v Persembahan ................................................................................................... vi Sanwacana ....................................................................................................... vii Abstrak ............................................................................................................ viii Daftar Isi .......................................................................................................... ix Daftar Gambar ................................................................................................. x I.
PENDAHULUAN 1.1. Latar Belakang ............................................................................. 1 1.2. Perumusan Masalah ...................................................................... 3 1.3. Tujuan Penelitian .......................................................................... 3 1.4. Manfaat Penelitian ........................................................................ 4
II.
TINJAUAN PUSTAKA 2.1. Konsep Dasar Graf ....................................................................... 5 2.2. Graf Petersen ................................................................................ 8 2.3. Bilangan Kromatik Lokasi Graf ................................................... 8
III.
METODE PENELITIAN 3.1. Waktu dan Tempat Penelitian ...................................................... 15 3.2. Metode Penelitian ......................................................................... 15
IV.
HASIL DAN PEMBAHASAN 4.1. Bilangan kromatik lokasi Graf Petersen Pn,1 dengan n ganjil ...... 17 4.2. Bilangan kromatik lokasi Graf Petersen Pn,1 dengan n genap ...... 27 4.3. Bilangan kromatik lokasi Graf Petersen Pn,2 dengan n ganjil ...... 36 4.4. Bilangan kromatik lokasi Graf Petersen Pn,2 dengan n genap ...... 46
V.
PENUTUP 5.1. Kesimpulan ................................................................................... 57 5.2. Saran ............................................................................................. 57
DAFTAR PUSTAKA ..................................................................................... 58
ix
DAFTAR GAMBAR Gambar 1.1 Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7 Gambar 4.8 Gambar 4.9 Gambar 4.10 Gambar 4.11 Gambar 4.12 Gambar 4.13 Gambar 4.14 Gambar 4.15 Gambar 4.16 Gambar 4.17 Gambar 4.18 Gambar 4.19 Gambar 4.20 Gambar 4.21 Gambar 4.22 Gambar 4.23 Gambar 4.24 Gambar 4.25 Gambar 4.26 Gambar 4.27 Gambar 4.28 Gambar 4.29 Gambar 4.30 Gambar 4.31 Gambar 4.32 Gambar 4.33
Contoh graf Petersen P3,1 ……………………………………... Contoh graf dengan 7 titik dan 8 sisi …………………………. Graf Petersen P8,1 ……………………………………………... Pewarnaan lokasi minimum pada Sa,b …………………………. Pewarnaan lokasi graf Petersen P8,1 berbilangan kromatik lokasi 4 ………………………………………………………... Pewarnaan lokasi graf Petersen P8,1 berbilangan kromatik lokasi 5 ………………………………………………………... Konstruksi batas bawah Graf Petersen Pn,1 untuk n ganjil ......... Konstruksi batas atas Graf Petersen P3,1 ……………………… Konstruksi batas atas Graf Petersen P5,1 ……………………… Konstruksi batas atas Graf Petersen P7,1 ……………………… Konstruksi batas atas Graf Petersen P9,1 ……………………… Konstruksi batas atas Graf Petersen P11,1 ……………………... Konstruksi batas atas Graf Petersen P13,1 ……………………... Konstruksi batas atas Graf Petersen P15,1 ……………………... Konstruksi batas atas Graf Petersen Pn,1 ……………………… Konstruksi batas bawah Graf Petersen Pn,1 untuk n genap ........ Konstruksi batas atas Graf Petersen P4,1 ……………………… Konstruksi batas atas Graf Petersen P6,1 ……………………… Konstruksi batas atas Graf Petersen P8,1 ……………………… Konstruksi batas atas Graf Petersen P10,1 ……………………... Konstruksi batas atas Graf Petersen P12,1 ……………………... Konstruksi batas atas Graf Petersen P14,1 ……………………... Konstruksi batas atas Graf Petersen Pn,1 untuk n genap ………. Konstruksi batas bawah Graf Petersen Pn,2 untuk n ganjil dengan 3 warna .......................................................................... Konstruksi batas bawah Graf Petersen Pn,2 untuk n ganjil dengan 4 warna .......................................................................... Konstruksi batas atas Graf Petersen P5,2 ……………………… Konstruksi batas atas Graf Petersen P7,2 ……………………… Konstruksi batas atas Graf Petersen P11,2 ……………………... Konstruksi batas atas Graf Petersen P13,2 ……………………... Konstruksi batas atas Graf Petersen P17,2 ……………………... Konstruksi batas atas Graf Petersen P9,2 ……………………… Konstruksi batas atas Graf Petersen P15,2 ……………………... Konstruksi batas atas Graf Petersen P19,2 ……………………... Konstruksi batas atas Graf Petersen P4,2 ……………………… Konstruksi batas bawah Graf Petersen Pn,2 untuk 5 ≤ n ≤ 20 dan n genap dengan 4 warna ………………………………….. Konstruksi batas atas Graf Petersen P6,2 ……………………… Konstruksi batas atas Graf Petersen P10,2 ……………………... Konstruksi batas atas Graf Petersen P14,2 ……………………... Konstruksi batas atas Graf Petersen P18,2 ……………………...
3 5 8 11 13 14 17 18 19 20 21 22 23 24 25 27 28 29 30 31 32 33 34 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
x
Gambar 4.34 Gambar 4.35 Gambar 4.36 Gambar 4.37
Konstruksi batas atas Graf Petersen P8,2 ……………………… Konstruksi batas atas Graf Petersen P12,2 ……………………... Konstruksi batas atas Graf Petersen P16,2 ……………………... Konstruksi batas atas Graf Petersen P20,2 ……………………...
52 53 54 55
xi
BAB I PENDAHULUAN
1.1. Latar Belakang Teori graf merupakan salah satu bidang ilmu matematika. Pada awalnya, teori graf diperkenalkan oleh Leonard Euler (1736) pada bukunya Solution Problematis Ad Geometriam Situs Pertinentis. Buku tersebut berisi tentang penyelesaian masalah jembatan Konigsberg yaitu kasus transportasi dimana hanya melewati sekali jalan dari empat daerah yang dihubungkan oleh tujuh jembatan dan kembali ke tempat awal. Berdasarkan representasi graf yang digunakannya, Euler membuktikan bahwa tidak mungkin melewati setiap jembatan tepat satu kali dan kembali ke posisi awal. Saat ini, perkembangan teori graf maju pesat. Teori graf banyak digunakan untuk menyelesaikan masalah yang ada dalam kehidupan. Tidak hanya untuk bidang matematika saja, namun juga bidang ilmu yang lainnya. Kajian tentang pewarnaan lokasi pada suatu graf adalah suatu kajian yang menarik dalam teori graf. Konsep pewarnaan lokasi pertama kali dikaji oleh Chartrand dkk. (tahun 2002), sebagai pengembangan dua konsep dalam graf yaitu pewarnaan titik pada graf dan dimensi partisi graf. Misalkan c suatu pewarnaan titik pada graf G dengan menggunakan warna 1,2,…,k untuk suatu bilangan positif k. Secara ekuivalen, c merupakan partisi Π dari V(G) ke dalam kelas-kelas warna yang saling bebas C1,C2,…,Ck yang mana titik-titik di Ci berwarna i, 1 ≤ i ≤ k. Jarak titik v ke suatu Ci, dinotasikan dengan d(v, Ci) adalah min {d(v, x)|x ϵ Ci}. Kode warna, cΠ (v) dari suatu titik v adalah kpasang terurut yaitu: cΠ(v) = (d(v, C1), d(v, C2), …, d(v,Ck)) Jika setiap titik di G memiliki kode warna yang berbeda terhadap partisi Π, maka c disebut pewarnaan lokasi G. Banyaknya warna minimum yang digunakan untuk
1
pewarnaan lokasi disebut bilangan kromatik lokasi dari G, dan dinotasikan dengan χL(G). Chartrand dkk. (2002), telah menentukan pewarnaan lokasi pada graf terhubung G. Jika u dan v adalah dua titik yang berbeda di G sedemikian sehingga d(u, w) = d(v, w) untuk setiap w ϵ V(G) – {u, v}, maka c(u) ≠ c(v). Secara khusus, jika u dan v titik-titik yang tidak bertetangga di G sedemikian sehingga N(u) ≠ N(v), maka c(u) ≠ c(v). Kemudian telah ditentukan bilangan kromatik lokasi pada beberapa kelas graf, diantaranya pada graf lintasan Pn untuk n ≥ 3 diperoleh χL(Pn) = 3; pada graf siklus diperoleh dua hasil yaitu untuk n ganjil diperoleh χL(Cn) = 3, dan untuk n genap diperoleh χL(Cn) = 4; pada graf bintang ganda (Sa,b), 1 ≤ a ≤ b dan b ≥ 2, diperoleh χL(Sa,b) = b + 1. Chartrand dkk. (2003), telah menunjukkan graf berorde n dengan bilangan kromatik lokasinya (n – 1) dan juga graf-graf yang mempunyai bilangan kromatik lokasi dengan batas atasnya (n – 2). Selain itu, Chartrand dkk. (2002) menunjukkan bahwa terdapat pohon berorde n ≥ 5 yang mempunyai bilangan kromatik k jika dan hanya jika k ϵ (3, 4, …, n – 2, n). Asmiati (2011) dalam makalahnya membahas bilangan kromatik lokasi dari amalgamasi graf bintang Sk,m. Sk,m diperoleh salinan k dari bintang K1,m dengan mengidentifikasi daun dari setiap bintang. Selanjutnya juga menentukan kondisi yang cukup subgraf terhubung
memenuhi
. Asmiati
(2013) dalam makalahnya mengkarakterisasi semua graf pohon berbilangan kromatik lokasi 3. Selanjutnya juga memberikan rumpun graf pohon dengan bilangan kromatik lokasi 4. Rinaldy (2016) telah berhasil menentukan bilangan kromatik lokasi graf Petersen Pn,k untuk P3,1, P4,1, P4,2, P5,1, P5,2, P6,1, P6,2, P6,3, P7,1, P7,2, dan P7,3. Bilangan kromatik lokasi pada graf Petersen Pn,k tersebut yaitu : χL (P3,1) = 4, χL (P4,1) = 5, χL (P4,2) = 4, χL (P5,1) = 4, χL (P5,2) = 4, χL (P6,1) = 5, χL (P6,2) = 5, χL (P6,3) = 5, χL (P7,1) = 5, χL (P7,2) = 5, χL (P7,3) = 5.
2
Permasalahan penentuan bilangan kromatik lokasi pada suatu graf merupakan permasalahan yang sulit, karena belum adanya teorema yang digunakan untuk menentukan bilangan kromatik lokasi pada sembarang graf. Oleh karena itu, pada penelitian ini akan dikaji tentang klasifikasi graf Petersen Pn,k berbilangan kromatik lokasi empat atau lima. 1.2. Perumusan Masalah Pada penelitian ini diberikan graf Petersen Pn,k adalah graf dengan 2n titik dengan n ≥ 3,{u1, u2, …, un} modulo n dan ui
{v1, v2, …, vn} dan sisi ui
ui+1 modulo n, vi
vi+k
vi.
Gambar 1.1. Contoh graf Petersen P3,1 Berdasarkan hasil penelitian Rinaldy (2016), diperoleh bilangan kromatik lokasi terendah dari graf Petersen adalah empat. Berdasarkan hal tersebut akan dilanjutkan dengan mengklasifikasi graf Petersen Pn,k berbilangan kromatik lokasi empat atau lima. 1.3. Tujuan Penelitian Tujuan dari penelitian tugas akhir ini adalah mengklasifikasi graf Petersen Pn,k berbilangan kromatik lokasi empat atau lima.
3
1.4. Manfaat Penelitian Manfaat yang didapat dari penelitian ini adalah mendapatkan klasifikasi graf Petersen Pn,k berbilangan kromatik lokasi empat atau lima. Klasifikasi graf Petersen Pn,k yang diperoleh sebagai parameter untuk mengklasifikasi graf Petersen dengan bilangan kromatik lokasi yang lebih tinggi.
4
BAB II TINJAUAN PUSTAKA
Pada bagian ini akan diberikan konsep dasar graf, graf Petersen dan bilangan kromatik lokasi pada suatu graf sebagai landasan teori pada penelitian ini. 2.1. Konsep Dasar Graf Teori dasar mengenai graf yang akan digunakan dalam penelitian ini diambil dari Deo (1989). Graf G adalah himpunan terurut (V(G), E(G)) dengan V(G) menyatakan himpunan titik (vertex) tak kosong dan E(G) menyatakan himpunan sisi (edge) yakni pasangan tak terurut dari V(G). Banyaknya himpunan titik V(G) disebut orde dari graf G. Misalkan v dan w adalah titik pada graf G, jika v dan w dihubungkan oleh sisi e, maka v dan w dikatakan bertetangga (adjacent), sedangkan titik v dan w dikatakan menempel (incident) dengan sisi e, demikian juga sisi e dikatakan menempel dengan titik v dan w. Himpunan tetangga (neighborhood) dari suatu titik v, dinotasikan dengan N(v) adalah himpunan titiktitik yang bertetangga dengan v.
Gambar 2.1. Contoh graf dengan 7 titik dan 8 sisi Pada Gambar 2.1. graf G(V, E), V(G) = {v1, v2, v3, v4, v5, v6, v7} dan E(G) = {e1, e2, e3, e4, e5, e6, e7, e8}. Titik v1 bertetangga dengan titik v2 dan v5 dinotasikan N(v1) = {v2, v5}, sedangkan v1 dan v2 menempel pada e1. Sebaliknya, sisi e1 menempel pada titik v1 dan v2. Derajat suatu titik v pada graf G adalah banyaknya sisi yang menempel pada titik v, dinotasikan dengan d(v). Pada Gambar 2.1, d(v1) = d(v3) = d(v4) = d(v6) = 2,
5
d(v2) = 4, d(v5) = 3, dan d(v7)=3. Daun (pendant vertex) adalah titik yang memiliki derajat 1. Pada Gambar 2.1, titik v7 adalah daun karena berderajat satu. Loop adalah sisi yang memiliki titik awal dan titik akhir yang sama. Sisi paralel adalah sisi yang memiliki dua titik ujung yang sama. Graf yang tidak mempunyai sisi ganda atau loop disebut graf sederhana. Graf pada Gambar 2.1. bukan merupakan graf sederhana karena pada graf tersebut terdapat loop yaitu pada titik v2. Istilah-istilah yang sering muncul pada pembahasan graf adalah jalan (walk), lintasan (path) dan sirkuit (circuit). Jalan (walk) adalah barisan berhingga dari titik dan sisi, dimulai dan diakhiri oleh titik sedemikian sehingga setiap sisi menempel dengan titik sebelum dan sesudahnya. Contoh jalan berdasarkan Gambar 2.1. adalah v1 – e1 – v2 – e2 – v2 – e3 – v3 – e4 – v4 – e5 – v5 – e7 – v6 – e8 – v7. Lintasan adalah jalan yang melewati titik yang berbeda–beda. Graf G dikatakan graf terhubung jika terdapat lintasan yang menghubungkan setiap dua titik yang berbeda. Pada Gambar 2.1. contoh lintasan adalah v1 – e1 – v2 – e3 – v3 – e4 – v4 – e5 – v5 – e7 – v6 – e8 – v7. Jarak diantara dua titik x dan y adalah panjang lintasan terpendek diantara kedua titik tersebut, dinotasikan dengan d(x, y). Sirkuit (circuit) adalah lintasan tertutup (closed path), yaitu lintasan yang memiliki titik awal dan titik akhir yang sama. Sirkuit dibedakan menjadi dua macam, yaitu sirkuit genap dan sirkuit ganjil. Sirkuit genap adalah sirkuit dengan banyaknya titik genap dan sirkuit ganjil adalah sirkuit dengan banyaknya titik ganjil. Contoh sirkuit berdasarkan Gambar 2.1. adalah v1 – e1 – v2 – e3 – v3 – e4 – v4 – e5 – v5 – e6. Contoh sirkuit tersebut adalah contoh sirkuit ganjil. Lemma yang menyatakan kaitan antara jumlah derajat semua titik pada suatu graf G dengan banyak sisinya adalah sebagai berikut: Lemma 2.1. (Deo, 1989) Misalkan G(V,E) adalah graf terhubung dengan |E| = e, maka :
6
∑ Bukti : Dalam sebarang graf, masing-masing sisi menghubungkan dua titik, sehingga setiap sisi menyumbangkan tepat dua untuk jumlah derajat titik. Sebagai contoh pada Gambar 2.1. (7 titik dan 8 sisi) adalah ∑ ∑ ∑ ∑ Teorema 2.1. (Deo, 1989) Untuk sembarang graf G, banyaknya titik yang berderajat ganjil selalu genap. Bukti : Misalkan Vgenap dan Vganjil masing-masing adalah himpunan titik yang berderajat genap dan himpunan titik yang berderajat ganjil pada G(V, E). maka persamaan dapat ditulis sebagai berikut : ∑
∑
( )
∑
Karena d(vj) untuk setiap vj ϵ Vgenap, maka suku pertama dari ruas kanan persamaan harus bernilai genap. Ruas kiri pada persamaan di atas juga harus bernilai genap. Nilai genap pada ruas kiri hanya benar bila suku kedua dari ruas kanan juga bernilai genap. Karena d(vk) untuk setiap vk ϵ Vganjil, maka banyaknya titik vk di dalam Vganjil harus genap agar jumlah seluruh derajatnya bernilai genap. Jadi banyaknya titik yang berderajat ganjil selalu genap.
7
2.2. Graf Petersen Graf Petersen Pn,k adalah graf dengan 2n titik {u1, u2, …, un} {v1, v2, …, vn} dan sisi ui
ui+1 modulo n, vi
vi+k modulo n dan ui
vi.
Gambar 2.2. Graf Petersen P8,1 2.3. Bilangan Kromatik Lokasi Graf Bilangan kromatik lokasi graf pertama kali dikaji oleh Chartrand dkk. (2002). Konsep ini merupakan pengembangan dari konsep dimensi partisi dan pewarnaan graf. Pewarnaan titik pada graf adalah c = V(G)
{1, 2, …, k} dengan syarat
untuk setiap titik bertetangga harus memiliki warna yang berbeda. Minimum banyaknya warna yang digunakan untuk pewarnaan titik pada graf G disebut bilangan kromatik lokasi, yang dinotasikan dengan
.
Berikut ini diberikan definisi bilangan kromatik lokasi graf yang diambil dari Chartrand dkk. (2002). Misalkan c suatu pewarnaan titik pada graf G dengan c(u) ≠ c(v) untuk u dan v bertetangga di G. Misalkan Ci himpunan titik-titik yang diberi warna i, yang selanjutnya disebut kelas warna, maka Π = {C1, C2, …, Ck} adalah himpunan yang terdiri dari kelas-kelas warna dari V(G). Kode warna cΠ(v) dari v adalah k-pasang terurut (d(v, C1), d(v, C2), …, d(v, Ck)) dengan d(v,Ci) = min {d(v, x)|x
Ci} untuk 1 ≤ i ≤ k. Jika setiap G mempunyai kode warna yang
berbeda, maka c disebut pewarnaan lokasi G. Banyaknya warna minimum yang 8
digunakan untuk pewarnaan lokasi disebut bilangan kromatik lokasi dari G, dan dinotasikan dengan
. Karena setiap pewarnaan lokasi juga merupakan suatu
pewarnaan, maka
.
Berikut ini merupakan teorema dasar dari bilangan kromatik lokasi suatu graf yang diberikan oleh Chartrand dkk. (2002). Teorema 2.2. (Chartrand dkk., 2002) Misalkan c adalah pewarnaan pada graf terhubung G. Jika u dan v adalah dua titik yang berbeda di G sedemikian sehingga d(u, w) = d(v, w) untuk setiap w
V(G) – {u, v}, maka c(u) ≠ c(v).
Secara khusus, jika u dan v titik-titik yang tidak bertetangga di G sedemikian sehingga N(u) ≠ N(v), maka c(u) ≠ c(v). Bukti : Misalkan c adalah suatu pewarnaan lokasi pada graf terhubung G dan misalkan Π = {C1, C2, …, Ck} adalah partisi dari titik-titik G ke dalam kelas warna Ci. Untuk setiap titik u, v
V(G), andaikan c(u) = c(v) sedemikian sehingga
titik u dan v berada dalam kelas warna yang sama, misalkan Ci dari Π. Akibatnya d(u, Ci) = d(v, Ci) = 0. Karena d(u, w) = d(v, w) untuk setiap w
V(G) – {u, v},
maka d(u, Ci) = d(v, Cj) untuk setiap i ≠ j, 1 ≤ j ≤ k. Akibatnya cΠ(u) = cΠ(v) sehingga c bukan pewarnaan lokasi, jadi c(u) ≠ c(v). Akibat dari teorema tersebut, dapat ditentukan batas bawah trivial bilangan kromatik lokasi graf. Akibat 2.1. (Chartrand dkk., 2002) Misalkan G adalah graf terhubung dengan satu titik yang bertetangga dengan k daun, maka
.
Bukti : Misalkan v adalah satu titik yang bertetangga dengan k daun x1, x2, …, xk di G. Berdasarkan Teorema 2.2, setiap pewarnaan lokasi di G mempunyai warna yang berbeda untuk setiap xi, i = 1, 2, …, k. Karena v bertetangga dengan semua xi, maka v harus mempunyai warna yang berbeda dengan semua daun xi. Akibatnya
.
9
Teorema 2.3. (Chartrand dkk., 2002) Misalkan k adalah derajat maksimum di graf G, maka
.
Bukti : Misalkan v adalah satu titik yang berderajat maksimum k daun x1, x2, …, xk di G. Berdasarkan Teorema 2.2 dan Akibat 2.1, setiap pewarnaan lokasi di G mempunyai warna yang berbeda setiap xi, i = 1, 2, …, k. Karena v berderajat maksimum k dengan xi, maka v harus mempunyai warna yang berbeda dengan semua daun xi. Akibatnya,
.
Teorema 2.4. (Chartrand dkk., 2002) Bilangan kromatik lokasi graf lintasan Pn(n≥ 3) adalah 3. Bukti : Perhatikan bahwa
dan
. Jelaslah bahwa
untuk n ≥ 3. Berdasarkan Teorema 2.3
, dengan k derajat titik
maksimum. Karena pada Pn, k = 2, maka Jadi terbukti
. Akibatnya
.
.
Teorema 2.5. (Chartrand dkk., 2002) Untuk bilangan bulat a dan b dengan 1 ≤ a ≤ b dan b ≥ 2, maka
(
)
.
Bukti : Berdasarkan Akibat 2.1, diperoleh batas bawah yaitu Selanjutnya, akan ditentukan batas atasnya, yaitu
(
)
(
)
.
. Misalkan c
adalah pewarnaan titik menggunakan (b + 1) warna sebagaimana terlihat pada Gambar 2.3. Perhatikan bahwa kode warna dari setiap titik Sa,b berbeda. Akibatnya c adalah pewarnaan lokasi. Jadi
(
)
.
1
2
2 b+1 u
a
3 1 v a+1
b
Gambar 2.3. Pewarnaan lokasi minimum pada Sa,b
10
Teorema 2.6. (Chartrand dkk., 2002) Pada graf lingkaran Cn untuk n ≥3, jika n adalah bilangan ganjil dan
jika n adalah bilangan
genap. Bukti : Kasus 1 n ≥ 3 adalah ganjil. Misal Cn : v1, v2, …, vn, v1. Ditetapkan warna 1 untuk v1, warna 2 untuk vi jika i adalah genap, dan warna 3 untuk vi jika i ≥ 3 dan i ganjil. Berdasarkan Akibat 2.1, perlu ditunjukkan bahwa ini adalah pewarnaan lokasi untuk membuktikan bahwa
. Pertimbangkan dua subkasus.
Subkasus 1.1 n = 4k + 1, dengan k ≥ 1. Untuk 1 ≤ i ≤ k, cΠ(v2i) = (2i – 1, 0, 1) dan untuk k + 1 ≤ i ≤ 2k, cΠ(v2i) = (2k + 2 – 2i, 0, 1). Juga, untuk 1 ≤ i ≤ k, cΠ(v2i + 1) = (2i, 1, 0) dan untuk k + 1 ≤ i ≤ 2k, cΠ(v2i +1) = (2k + 1 – 2i, 1, 0). Karena semua vector cΠ(vi) berbeda, maka pewarnaan ini adalah pewarnaan lokasi dan
.
Subkasus 1.2 n = 4k + 3, dengan k ≥ 0. Bukti
mirip dengan Subkasus 1.1.
Kasus 2 n ≥ 4 adalah genap. Misal Cn : v1, v2, …, vn, v1. Ditetapkan warna 1 untuk v1, warna 2 untuk vi jika i adalah genap, dan warna 3 untuk vi jika i ≥ 3 dan i ganjil, dan warna 4 untuk vi jika i ≥ 4 dan i genap. Akan ditunjukkan bahwa ini adalah pewarnaan lokasi Cn, dengan demikian membuktikan bahwa
.
Pertimbangkan dua subkasus. Subkasus 2.1 n = 4k, dengan k ≥ 1. Untuk 1 ≤ i ≤ k, cΠ(v2i+1) = (2i, 2i – 1, 0, 1) dan untuk k + 1 ≤ i ≤ 2k – 1, cΠ(v2i+1) = (4k – 2i, 4k + 1 – 2i, 0, 1). Untuk 2 ≤ i ≤ k, cΠ(v2i) = (2i – 1, 2i – 2, 1, 0) dan untuk k+1 ≤ i ≤ 2k, cΠ(v2i) = (4k + 1 – 2i, 4k + 2 – 2i, 1, 0). Karena semua vector cΠ(vi) berbeda, maka pewarnaan ini adalah pewarnaan lokasi dan
.
11
Subkasus 2.2 n = 4k + 2, dengan k ≥ 1. Bukti bahwa
mirip dengan Subkasus 2.1.
Tetap hanya untuk menunjukkan
jika n genap. Diasumsikan secara
kebalikannya, bahwa terdapat c pewarnaan lokasi dari Cn yang menggunakan tiga warna, misalkan 1, 2, 3 untuk n ≥ 4. Setidaknya salah satu warna, misalkan 2, digunakan untuk mewarnai sejumlah t titik Cn, dimana 2 ≤ t ≤ n/2. Selanjutnya dicari siklus dari Cn, dimulai dengan v1, misal
, menjadi titik pada
Cn yang berwarna 2. Karena tidak ada dua titik yang berdekatan, selanjutnya untuk
setiap
bilangan
{
bulat
j
dengan
1
≤
j
≤
t,
interval
Ij
=
}(dihitung modulo n) tidak kosong.
Pertama, ditunjukkan bahwa tidak ada interval yang berkardinal ganjil yaitu 3 atau lebih, diasumsikan secara kontradiksi, bahwa beberapa interval Ij terdiri atas bilangan ganjil dari titik atau lebih. Tanpa menghilangkan secara umum, diasumsikan bahwa (
)
dan
(
berwarna 1. Namun,
)
, yang tidak mungkin.
Kedua, ditunjukkan bahwa tidak ada interval yang berbilangan genap pada titik, diasumsikan secara kontradiksi, terdapat interval berbilangan genap pada titik. Karena C2k memiliki susunan genap, harus ada bilangan genap pada interval yang terdiri dari bilangan genap pada titik. Misalkan Ij dan Ik dua interval berbeda yang terdiri dari bilangan genap pada titik. Diasumsikan, tanpa menghilangkan secara umum, bahwa
berwarna 1. Tepat satu dari
dikatakan berbekas. Maka
(
)
(
dan )
berwarna 1, , kontradiksi.
Kensekuensinya, semua interval t = n/2 terdiri tepat satu titik. Seharusnya, ada bilangan bulat terkecil ij (1 ≤ j ≤ n/2) sehingga
dan
berwarna berbeda,
katakanlah 1 dan 3, secara berturut-turut. Seharusnya, ada bilangan bulat ik > ij sehingga
berwarna 3 dan
berwarna 1. Namun, kemudian
(
)
12
(
)
, menghasilkan kontradiksi akhir. Oleh karena itu,
jika n genap. Selanjutnya, akan diberikan contoh menentukan bilangan kromatik lokasi pada suatu graf Petersen P8,1 sebagai berikut ini :
Gambar 2.4. Pewarnaan lokasi graf Petersen P8,1 berbilangan kromatik lokasi 4 Diberikan graf Petersen P8,1, akan ditentukan terlebih dahulu batas bawah bilangan kromatik lokasi dari graf Petersen P8,1. Karena n = 8 dan merupakan bilangan genap maka bisa diambil batas bawah yaitu
(
)
. Titik-titik
pada V(P8,1) dipartisi sebagai berikut : C1 = {u1, u5, v3, v7}; C2 = {u2, u8, v1, v4, v6}; C3={u4, u7, v5, v8}; C4 = {u3, u6, v2}. Kode warnanya adalah cΠ(u1) = (0, 1, 2, 2); cΠ(u2) = (1, 0, 2, 1); cΠ(u3) = (1, 1, 1, 0); cΠ(u4) = (1, 1, 0, 1); cΠ(u5) = (0, 2, 1, 1); cΠ(u6) = (1, 1, 1, 0); cΠ(u7) = (1, 1, 0, 1); cΠ(u8) = (1, 0, 1, 2); cΠ(v1) = (1, 0, 1, 1); cΠ(v2) = (1, 1, 2, 0); cΠ(v3) = (0, 1, 2, 1); cΠ(v4) = (1, 0, 1, 2); cΠ(v5) = (1, 1, 0, 2); cΠ(v6) = (1, 0, 1, 1); cΠ(v7) = (0, 1, 1, 2); cΠ(v8) = (1, 1, 0, 2). Karena terdapat kode warna titik di V(P8,1) berbeda, maka pewarnaan tersebut bukan merupakan (
pewarnaan lokasi. Sehingga, untuk batas bawah dari P8,1,
(
) )
. Sehingga didapat pertidaksamaan ...................................................... (1)
13
Gambar 2.5. Pewarnaan lokasi graf Petersen P8,1 berbilangan kromatik lokasi 5. Selanjutnya, akan ditentukan batas atas bilangan kromatik lokasi graf Petersen P8,1. Titik-titik pada V(P8,1) dipartisi sebagai berikut : C1 = {u1, u3, u7, v8}; C2 = {u2, u6, u8, v3, v5, v7}; C3 = {u5, v1, /v4}; C4 = {u4, v6}; C5 = {v2}. Kode warnanya adalah cΠ(u1) = (0, 1, 1, 3, 2); cΠ(u2) = (1, 0, 2, 2, 1); cΠ(u3) = (0, 1, 2, 1, 2); cΠ(u4) = (1, 2, 1, 0, 3); cΠ(u5) = (2, 1, 0, 1, 4); cΠ(u6) = (1, 0, 1, 1, 5); cΠ(u7)=(0, 1, 2, 2, 4); cΠ(u8) = (1, 0, 2, 3, 3); cΠ(v1) = (1, 2, 0, 3, 1); cΠ(v2) = (2, 1, 1, 3, 0); cΠ(v3) = (1, 0, 1, 2, 1); cΠ(v4) = (2, 1, 0, 1, 2); cΠ(v5) = (3, 0, 1, 1, 3); cΠ(v6) = (2, 1, 2, 0, 4); cΠ(v7) = (1, 0, 2, 1, 3); cΠ(v8) = (0, 1, 1, 2, 2). Karena kode warna semua titik di V(P8,1) berbeda, maka pewarnaan tersebut merupakan pewarnaan lokasi. Sehingga didapat pertidaksamaan batas atas dari P8,1,
(
)
Berdasarkan Pertidaksamaan (1) dan (2), maka diperoleh
............................ (2) (
)
.
14
BAB III METODE PENELITIAN
3.1. Waktu dan Tempat Penelitian Penelitian ini dilakukan di Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung. Waktu penelitian dilakukan pada semester ganjil tahun ajaran 2016-2017. 3.2. Metode Penelitian Rinaldy (2016) telah berhasil menentukan bilangan kromatik lokasi graf Petersen Pn,k untuk P3,1, P4,1, P4,2, P5,1, P5,2, P6,1, P6,2, P6,3, P7,1, P7,2, dan P7,3. Bilangan kromatik lokasi pada graf Petersen Pn,k tersebut yaitu: χL (P3,1) = 4, χL (P4,1) = 5, χL (P4,2) = 4, χL (P5,1) = 4, χL (P5,2) = 4, χL (P6,1) = 5, χL (P6,2) = 5, χL (P6,3) = 5, χL (P7,1) = 5, χL (P7,2) = 5, χL (P7,3) = 5. Penelitian ini merupakan penelitian lanjutan yang telah dilakukan oleh Rinaldy (2016). Penelitian ini bertujuan untuk mengklasifikasi graf Petersen Pn,k berbilangan kromatik lokasi empat dan lima. Langkah-langkah untuk menentukan klasifikasi graf Petersen Pn,k berbilangan kromatik lokasi empat dan lima adalah sebagai berikut : 1.
Mempelajari materi tentang graf Petersen Pn,k dan bilangan kromatik lokasi suatu graf.
2.
Batas bawah trivial dari χL (Pn,k) dapat ditentukan berdasarkan Teorema 2.6, yaitu
jika n adalah bilangan ganjil dan
jika n adalah
bilangan genap. Akan tetapi, jika batas bawahnya tidak dapat ditentukan secara trivial, maka digunakan pembuktian dengan kontradiksi. 3.
Penentuan batas atas dari χL (Pn,k). Pada graf Petersen χL (Pn,k) dapat dilakukan counting dalam menentukan batas atasnya. Hal ini dilakukan untuk memperlihatkan struktur dari graf Petersen Pn,k.
15
4.
Mengklasifikasi graf-graf Petersen berbilangan kromatik lokasi empat atau lima.
5.
Memperoleh klasifikasi graf Petersen berbilangan kromatik lokasi empat atau lima.
16
BAB V PENUTUP
5.1. Kesimpulan Berdasarkan hasil dan pembahasan serta diskusi dari penelitian yang sudah dilakukan, diperoleh bahwa : 1.
Bilangan kromatik lokasi Graf Petersen Pn,1 yaitu : (
2.
(
)
3.
(
)
)
{
untuk 5 ≤ n ≤ 20.
5.2. Saran Penelitian ini dapat dilanjutkan dengan mengklasifikasi bilangan kromatik lokasi Graf Petersen Pn,k dengan k > 1.
57
DAFTAR PUSTAKA
Asmiati, H. Assiyatun, E.T. Baskoro. 2011. Locating-chromatic number of amalgamation of stars, ITB J. Sci. 43A, 1–8. Asmiati, Baskoro, E.T. 2013. Characterizing of graphs containing cycle with locating-chromatics number three, AIP conf. Proc, 1450, 351-357. Chartrand, G, Erwin, D, Henning, M.A, Slater, PJ, dan Zhang, P. 2002. The locating-chromatics number of graph, Bull.Inst. Combin. Apll., 36, 89-101. Chartrand, G, Erwin, D, Henning, M.A, Slater, PJ, dan Zhang, P. 2003. Graph of order n with locating-chromatics number n-1, Discrate Math, 269, 65-79. Deo, Narsing. 1989. Graph teory with applications to engineering and computer science. Prentice-Hall of India Private Limited. Rinaldy. Erick. 2016. “Bilangan Kromatik Lokasi Beberapa Graf Petersen”. Skripsi. FMIPA. Universitas Lampung.
58
