bilangan kromatik lokasi pada graf...

BILANGAN KROMATIK LOKASI

PADA GRAF BUKU

SKRIPSI

Maiyudi Mariska Windra Yahya

11150940000046

PROGRAM STUDI MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UIN SYARIF HIDAYATULLAH JAKARTA

2020 M / 1441 H

i

BILANGAN KROMATIK LOKASI PADA GRAF BUKU

Skripsi

Diajukan kepada

Universitas Islam Negeri Syarif Hidayatullah Jakarta

Fakultas Sains dan Teknologi

Untuk Memenuhi Salah Satu Persyaratan dalam

Memperoleh Gelar Sarjana Matematika (S.Mat)

Oleh:

Maiyudi Mariska Windra Yahya

11150940000046

PROGRAM STUDI MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UIN SYARIF HIDAYATULLAH JAKARTA

2020 M / 1441 H

iii

LEMBAR PENGESAHAN

Skripsi ini berjudul “Bilangan Kromatik Lokasi Pada Graf Buku” yang ditulis oleh

Maiyudi Mariska Windra Yahya NIM. 11150940000046 telah diuji dan dinyatakan

lulus dalam sidang Munaqosah Fakultas Sains dan Teknologi Universitas Islam Negeri

Syarif Hidayatullah Jakarta pada hari Senin, 18 Mei 2020. Skripsi ini telah diterima

untuk memenuhi salah satu persyaratan dalam memperoleh gelar sarjana strata satu (S1)

Program Studi Matematika.

Menyetujui,

Pembimbing I Pembimbing II

Dr. Nur Inayah, M.Si Wisnu Aribowo, M.Si

NIP. 19740125 200312 2 001 NUPN. 9920113332

Penguji I

Penguji II

Yanne Irene, M.Si Muhaza Liebenlito, M.Si

NIP. 19741231 200501 2 018 NIDN. 2003098802

Mengetahui,

Dekan Fakultas Sains dan Teknologi Ketua Program Studi

Matematika

Prof. Dr. Lily Surayya Eka Putri, M. Env.Stud

Dr. Suma’inna, M.Si

NIP. 19690404 200501 2 005 NIP. 19791208 200701 2 015

v

PERSEMBAHAN

Segala perjuangan saya hingga titik ini saya persembahkan kepada

kedua orang tua yang paling berharga dalam hidup saya, yaitu

Ayah Agus Tamar dan Ibu Winarni.

Terima kasih telah menjadi orang tua yang sempurna.

MOTTO

“Sesungguhnya sesudah kesulitan itu ada kemudahan“

(Q.S. Al-Insyirah:6)

“Hai orang-orang yang beriman, Jadikanlah sabar dan shalatmu

sebagai penolongmu, sesungguhnya Allah beserta orang-orang yang

sabar“

(Q.S. Al-Baqarah:153)

vi

KATA PENGANTAR

Assalamu’alaikum Warahmatullahi Wabarakatuh

Alhamdulillah, dengan memanjatkan puj dan syukur atas kehadirat Allah

SWT yang telah memberikan rahmat dan hidayah-Nya sehingga penulis dapat

menyelesaikan skripsi ini dengan judul “Bilangan Kromatik Lokasi pada Graf

Buku”. Tidak lupa shalawat serta salam semoga senantiasa tercurahkan kepada

baginda Nabi Muhammad SAW beserta keluarga dan para sahabatnya hingga pada

umatnya sampai akhir zaman.

Dalam menyelesaikan penyusunan skripsi ini, penulis mendapatkan

bimbingan dan bantuan dari berbagai pihak serta bentuk kontribusi lainnya sampai

skripsi ini dapat terselesaikan. Untuk itu, pada kesempatan ini penulis ingin

menyampaikan terima kasih kepada:

1. Ibu Prof. Dr. Lily Surraya Eka Putri,M.Env.Stud, selaku Dekan Fakultas

Sains dan Teknologi Universitas Islam Negri Syarif Hidayatullah Jakartta.

2. Ibu Dr. Suma’inna, M.Si selaku Ketua Program Studi Matematika Fakultas

Sains dan Teknologi dan Ibu Irma Fauziah, M.Si, selaku Sekretaris Program

Studi Matematika Fakultas Sains dan Teknologi.

3. Ibu Dr. Nur Inayah, M.Si selaku Dosen Pembimbing I dan Bapak Wisnu

Aribowo, M.Si selaku Dosen Pembimbing II yang telah menyediakan

waktunya untuk memberikan bimbingan, pengarahan, motivasi, serta saran

dalam menyelesaikan skripsi ini.

4. Seluruh Ibu dan Bapak Dosen Program Studi Matematika yang telah

memberikan ilmu–ilmunya dan pengalaman yang bermanfaat selama

penulis dimasa studi.

5. Orang tua penulis, Pak Agus Tamar dan Ibu Winarni, serta adik kandung

penulis, Salwa Salsabilah, yang tidak pernah berhenti memberikan doa,

vii

kasih sayang, semangat, serta dukungan moril maupun materil sekaligus

menjadi motivasi terbesar penulis sehingga skripsi ini dapat terselesaikan.

6. Teman seperjuangan skripsi penulis Rizki Dini Febri Anggraini yang telah

menemani penulis dalam berdiskusi, memberikan masukan serta semangat

dalam mengerjakan skripsi.

7. Kak Woro dan Kak Bagus yang telah memberikan masukan dan arahan serta

membantu dalam penulisan hingga skripsi ini dapat terselesaikan.

8. Tanjung, Rahilda dan Alun yang telah memberikan semangat untuk penulis

serta berbagi suka dan duka selama masa perkuliahan.

9. Seluruh teman – teman dari Matematika 2015 yang tidak dapat disebutkan

satu persatu. Terimakasih untuk semuanya.

10. Keluarga Himpunan Mahasiswa Matematika yang telah memberikan ilmu,

kepercayaan, dan pengalaman yang luar biasa.

11. Seluruh pihak yang telah membantu penulis dalam menyelesaikan skripsi

yang tidak dapat disebutkan satu persatu.

Penulis menyadari penulisan skripsi ini tidaklah sempurna. Kritik dan saran

yang membangun demi perbaikan dan penyempurnaan skripsi ini dapat

disampaikan melalui [email protected]. Akhir kata, penulis berharap

semoga skripsi ini dapat bermanfaat. Aamiin.

Wassalamu’alaikum Warahmatullahi wabarakatuh

Jakarta. Mei 2020

Penulis

viii

DAFTAR ISI

BILANGAN KROMATIK LOKASI PADA GRAF BUKU............................... i

PERNYATAAN ..................................................................................................... ii

LEMBAR PENGESAHAN ................................................................................. iii

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH

UNTUK KEPENTINGAN AKADEMIS ........................................................... iv

PERSEMBAHAN .................................................................................................. v

MOTTO ................................................................................................................. v

KATA PENGANTAR .......................................................................................... vi

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

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

ABSTRAK ........................................................................................................... xii

ABSTRACT ........................................................................................................ xiii

I PENDAHULUAN ............................................................................................. 1

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

1.2 Perumusan Permasalahan .......................................................................... 3

1.3 Pembatasan Permasalahan ......................................................................... 4

1.4 Tujuan Penelitian ....................................................................................... 4

1.5 Manfaat Penelitian ..................................................................................... 4

II LANDASAN TEORI ...................................................................................... 5

2.1 Konsep Dasar Graf .................................................................................... 5

2.2 Beberapa Graf Khusus ............................................................................... 8

2.2.1 Graf Lintasan ..................................................................................... 8

2.2.2 Graf Lingkaran .................................................................................. 8

2.2.3 Graf Bintang ...................................................................................... 9

2.3 Konsep Bilangan Kromatik Lokasi pada Suatu Graf ................................ 9

2.3.1 Pewarnaan Titik ................................................................................ 9

2.3.2 Dimensi Partisi ................................................................................ 10

2.4 Bilangan Kromatik Lokasi ...................................................................... 10

2.5 Graf Hasil Kali Kartesian ........................................................................ 13

2.6 Graf Buku ................................................................................................ 15

III PEMBAHASAN ........................................................................................... 16

3.1 Bilangan Kromatik Lokasi pada Graf Buku untuk 𝑛 = 1 ....................... 16

ix








3.9 Konstruksi Hipotesis ............................................................................... 30

3.10 Bilangan Kromatik Lokasi Graf Buku 𝐵𝑛 ............................................. 31

IV PENUTUP .................................................................................................... 38

4.1 Kesimpulan .............................................................................................. 38

4.2 Saran ........................................................................................................ 38

REFERENSI ........................................................................................................ 39

DAFTAR GAMBAR

2.1 Graf G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Ilustrasi untuk (a) Graf tidak berarah (b) Graf berarah . . . . . . . . 62.3 Ilustrasi untuk (a) Graf berhingga (b) Graf tidak berhingga . . . . . 62.4 Graf Lintasan P2 dan P4 . . . . . . . . . . . . . . . . . . . . . . . 82.5 Graf Lingkaran C3, C4 dan C5 . . . . . . . . . . . . . . . . . . . . 92.6 (a) Graf S4 (b) Graf S8 . . . . . . . . . . . . . . . . . . . . . . . . 92.7 Pewarnaan pada Graf H . . . . . . . . . . . . . . . . . . . . . . . 102.8 Pewarnaan kromatik lokasi Graf G2 dengan 3 warna . . . . . . . . . 122.9 Pewarnaan kromatik lokasi Graf G3 dengan 4 warna . . . . . . . . . 132.10 Graf Sederhana P2 dan S3 . . . . . . . . . . . . . . . . . . . . . . 142.11 Graf Hasil Kali Kartesian P2 × S3 . . . . . . . . . . . . . . . . . . 152.12 (a) Graf B3 dan (b) Graf B4 . . . . . . . . . . . . . . . . . . . . . . 15

3.1 Graf Buku B1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2 Pewarnaan Lokasi 3 warna pada Graf B1 . . . . . . . . . . . . . . . 173.3 Graf Buku B2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.4 Pewarnaan Lokasi 4 warna pada Graf B2 . . . . . . . . . . . . . . . 183.5 Graf Buku B3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.6 Pewarnaan Lokasi 4 warna pada Graf B3 . . . . . . . . . . . . . . . 203.7 Graf Buku B4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.8 Pewarnaan Lokasi 4 warna pada Graf B4 . . . . . . . . . . . . . . . 213.9 Graf Buku B5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.10 Pewarnaan Lokasi 4 warna pada Graf B5 . . . . . . . . . . . . . . . 233.11 Graf Buku B6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.12 Pewarnaan Lokasi 4 warna pada Graf B6 . . . . . . . . . . . . . . . 253.13 Graf Buku B7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.14 Pewarnaan Lokasi 5 warna pada Graf B7 . . . . . . . . . . . . . . . 273.15 Graf Buku B7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.16 Pewarnaan Lokasi 5 warna pada Graf B7 . . . . . . . . . . . . . . . 293.17 Graf Buku Bn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.18 Ilustrasi Lema 3.10.3 . . . . . . . . . . . . . . . . . . . . . . . . . 323.19 Ilustrasi Kasus 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.20 Ilustrasi Kasus 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

x

3.21 Ilustrasi Kasus 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.22 Ilustrasi Kasus 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

xi

xii

ABSTRAK

Maiyudi Mariska Windra Yahya, Bilangan Kromatik Lokasi pada Graf Buku,

dibawah bimbingan Dr. Nur Inayah, M.Si dan Wisnu Aribowo, M.Si.

Misalkan 𝐺 = (𝑉, 𝐸) adalah graf terhubung dan 𝑐 suatu pewarnaan-𝑘 sejati dari 𝐺

degan warna 1,2, … , 𝑘. Misalkan pula Π = {𝐶1, 𝐶2, … , 𝐶𝑘} merupakan partisi dari

𝑉(𝐺) yang diinduksi oleh pewarnaan 𝑐. Kode warna, 𝑐Π(𝑣) dari 𝑣 adalah 𝑘-

pasangan terurut (𝑑(𝑣, 𝐶1), 𝑑(𝑣, 𝐶2), . . . . , 𝑑(𝑣, 𝐶𝑘)) dengan 𝑑(𝑣, 𝐶𝑖) =

min{𝑑(𝑣, 𝑥)|𝑥 ∈ 𝐶𝑖} untuk 1 ≤ 𝑖 ≤ 𝑘. Jika semua titik di G mempunyai kode

warna berbeda, maka 𝑐 disebut pewarnaan-𝑘 lokasi dari 𝐺. Bilangan kromatik

lokasi dari 𝐺, dinotasikan dengan 𝜒𝐿(𝐺), adalah bilangan terkecil 𝑘 sehingga

𝐺 mempunyai pewarnaan-𝑘 lokasi. Pada penulisan ini akan menentukan bilangan

kromatik lokasi dari graf buku 𝐵𝑛. Bilangan kromatik lokasi pada graf buku 𝐵𝑛

adalah:

𝜒𝐿(𝐵𝑛) = min {𝑘: 𝑛 ≤ 2 (𝑘 − 2

2) + 2(𝑘 − 1) − 1}

Untuk 𝑘 ≥ 4, atau dengan

𝜒𝐿(𝐵𝑛) = ⌈√𝑛 −3

4+

3

2⌉

Kata Kunci : Kode warna, Bilangan kromatik lokasi, Graf buku

xiii

ABSTRACT

Maiyudi Mariska Windra Yahya, The Locating-Chromatic Number of Book

Graph, under the guidance of Dr. Nur Inayah, M.Si and Wisnu Aribowo, M.Si.

Let 𝐺 = (𝑉, 𝐸) be a connected graph and 𝑐 be a proper 𝑘-coloring of 𝐺 with

1,2, … , 𝑘 as colors in 𝑐. Let Π = {𝐶1, 𝐶2, … , 𝐶𝑘} be a partition of 𝑉(𝐺), induced by

the coloring 𝑐. The color code 𝑐Π(𝑣) of 𝑣 is 𝑘-ordered pair (𝑑(𝑣, 𝐶1), 𝑑(𝑣, 𝐶2), … ,

𝑑(𝑣, 𝐶𝑘)) where 𝑑(𝑣, 𝐶𝑖) = min{𝑑(𝑣, 𝑥)|𝑥 ∈ 𝐶𝑖} for 1 ≤ 𝑖 ≤ 𝑘. If each of the

vertices of 𝐺 have distinct color code, then 𝑐 is called a 𝑘-locating coloring of 𝐺.

The locating-chromatic number, denoted by 𝜒𝐿(𝐺) is the smallest 𝑘 such that 𝐺 has

a locating 𝑘-coloring. This paper will determine the locating-chromatic number on

book graph 𝐵𝑛. The locating-chromatic number on book graph 𝐵𝑛 is:

𝜒𝐿(𝐵𝑛) = min {𝑘: 𝑛 ≤ 2 (𝑘 − 2

2) + 2(𝑘 − 1) − 1}

For 𝑘 ≥ 4, or

𝜒𝐿(𝐵𝑛) = ⌈√𝑛 −3

4+

3

2⌉

Keywords: Color code, Locating-chromatic number, Book graph

BAB I

PENDAHULUAN

1.1. Latar Belakang Masalah

Matematika sering disebut sebagai mother of science yang berarti induk dari

segala ilmu pengetahuan. Artinya, setiap cabang ilmu pengetahuan banyak yang

berakar dari matematika. Peran matematika tidak lepas dari kehidupan sehari-hari

baik secara langsung maupun tidak langsung. Dalam Al-qur’an terdapat sebuah

motivasi untuk mempelajari matematika sebagaimana yang ada dalam surat Yunus

ayat 5:

Artinya:

”Dia-lah yang menjadikan matahari bersinar dan bulan bercahaya dan ditetapkan-

Nya manzilah-manzilah (tempat-tempat) bagi perjalanan bulan itu, supaya kamu

mengetahui bilangan tahun dan perhitungan (waktu). Allah tidak menciptakan yang

demikian itu melainkan dengan hak. Dia menjelaskan tanda-tanda (kebesaran-

Nya) kepada orang-orang yang mengetahui.”

Maka dari itu akan sangat merugi apabila kecerdasan otak manusia yang dibe-

rikan oleh Allah SWT tidak digunakan untuk mempelajari bilangan dan perhitung-

an. Suatu bilangan dan perhitungan dapat dipelajari dalam ilmu matematika, yaitu

seperti aljabar, statistika, geometri, teori graf, dan lain-lain.

Teori graf merupakan salah satu cabang dari matematika yang mempelajari

konsep terkait himpunan titik yang dihubungkan dengan himpunan sisi. Sampai saat

ini, teori graf merupakan pokok bahasan yang mendapat banyak perhatian karena

model-modelnya sangat berguna untuk diaplikasikan dalam kehidupan sehari-hari

1

seperti halnya digunakan dalam jaringan komunikasi, ilmu komputer, transportasi,

pembuatan peta dan masih banyak aplikasi lainnya. Teori graf juga banyak dipakai

pada bidang terapan seperti kajian mengenai bilangan kromatik lokasi dari suatu

graf. Konsep bilangan kromatik lokasi graf pertama kali dikaji oleh Chartrand dkk

[1] pada tahun 2002, dengan mengembangkan dua konsep graf, yaitu pewarnaan

titik dan dimensi partisi dari suatu graf.

Chartrand dkk (2002) telah mendapatkan bilangan kromatik lokasi dari bebe-

rapa graf, diantaranya pada graf lintasan, graf lingkaran dan graf bintang ganda.

Adapun hasil bilangan kromatik lokasi menurut Chartrand dkk [1]:

1. Graf lintasan Pn diperoleh χL(Pn) = 3 untuk n ≥ 3;

2. Graf Lingkaran Cn diperoleh dua hasil yaitu χL(Cn) = 3 untuk n ganjil dan

χL(Cn) = 4 untuk n genap;

3. Graf bintang ganda Sa,b diperoleh χL(Sa,b) = b+1 bila 1 ≤ a ≤ b dan b ≥ 2.

Selanjutnya pada tahun 2011, Asmiati dkk. telah berhasil menentukan bilang-

an kromatik lokasi pada graf amalgamasi bintang [2]. Bilangan kromatik lokasi

pada graf amalgamasi bintang seragam Sk,m yang merupakan amalgamasi dari k

buah graf bintang K1,m bila ni = m, untuk setiap i diperoleh jika

H(a) = (m+ a− 1)

m+ a− 1m− 1

dengan a ≥ 0, k ≥ 2, dan m ≥ 3 maka:

χL(Sk,m) =

m ; untuk 2 ≤ k ≤ H(0),m ≥ 3m+ 1; untuk H(a− 1) < k ≤ H(a), a ≥ 1Pada tahun 2012, Ali Behtoei dan Behnaz Omoomi telah memaparkan hasil

dari bilangan kromatik lokasi untuk operasi kartesian dari graf Pm×Pn dengan n ≥

m ≥ 2,Km×Pn denganm ≥ 3, n ≥ 2 danKm×Kn denganm ≥ 2, n ≥ 3,m ≤ n

[3]. Adapun hasil bilangan kromatik lokasi untuk operasi kartesian sebagai berikut:

(i) untuk n ≥ m ≥ 2, χL(Pm × Pn) = 4,

2

(ii) untuk m ≥ 3, n ≥ 2,

χL(Km × Pn) =

m+ 2, jika m ≤ n− 1m+ 1, jika m ≥ n− 1(iii) untuk m ≥ 2, n ≥ 3, dan m ≤ n, dimana m0 := max{k|k ∈ N, k(k − 1) −

1 ≤ n}

χL(Km ×Kn) =

n+ 1, jika m ≤ m0 − 1n+ 2, jika m0 + 1 ≤ m ≤ n2Penelitian terkait topik bilangan kromatik lokasi pada teori graf semkain ber-

kembang, diantaranya pada tahun 2013 dan 2014, Des Welyyanti dkk telah menen-

tukan bilangan kromatik lokasi untuk graf pohon n-ary lengkap T (n, k) dengan

k = 1, 2, 3 [4] dan bilangan kromatik lokasi untuk graf tak terhubung [5]. Berikut

ini adalah hasil bilangan kromatik lokasi untuk graf pohon n-ary lengkap T (n, k)

dengan k = 1, 2, 3.

(i) χL (T (n, 1)) = χL (T (n, 2)) = n+ 1 untuk k = 1 atau k = 2, dan n ≥ 2,

(ii) χL (T (n, 3)) = n+ 2, untuk k = 3, dan n ≥ 3.

Selanjutnya pada tahun 2018, Chintia Deva Rianti dan Narwen menentukan

bilangan kromatik lokasi pada graf spinner (C3×P2�K1) dan diperoleh bilangan

kromatik lokasi pada graf spinner χL(C3 × P2 �K1) = 4 [6].

Masih banyak kelas graf yang belum ditemukan pada kajian bilangan kromatik

lokasi, namun karena keterbatasan sumberdaya, penulis tertarik pada pembahasan

bilangan kromatik lokasi pada graf bukuBn. Graf buku merupakan hasil kali opera-

si kartesian antara graf lintasan yang memiliki dua titik dengan graf bintang dengan

(n+ 1) titik yaitu Bn = P2 × Sn.

1.2. Perumusan Permasalahan

Berdasarkan latar belakang yang telah diuraikan, maka permasalahan pada pe-

nulisan ini adalah bagaimana menentukan bilangan kromatik lokasi pada graf buku

Bn.

3

1.3. Pembatasan Permasalahan

Dalam penulisan ini, penulis hanya mengkaji bilangan kromatik lokasi dari

graf khusus yaitu graf buku Bn.

1.4. Tujuan Penelitian

Tujuan penulisan ini adalah untuk menentukan bilangan kromatik lokasi untuk

graf buku Bn.

1.5. Manfaat Penelitian

Manfaat dari penelitian ini adalah:

1. Dapat menentukan bilangan kromatik lokasi untuk graf Bn.

2. Memberikan sumbangan pikiran untuk penelitian selanjutnya serta menam-

bah wawasan bagi penulis dan pembaca mengenai bilangan kromatik lokasi

untuk graf Bn.

4

BAB II

LANDASAN TEORI

2.1. Konsep Dasar Graf

GrafG adalah tripel terurut (V (G), E(G), ψG) yang terdiri dari himpunan titik

tak kosong V (G), himpunan sisi E(G), yang terpisah dari himpunan V (G), dan

fungsi insidensi ψG yang menghubungkan setiap sisi dari G dengan pasangan tak

terurut dari titikG. Jika e adalah sisi dan u dan v adalah titik-titik sehingga ψG(e) =

uv, kemudian e dikatakan terkait dengan u dan v; titik-titik u dan v disebut ujung

dari e [7]. Contoh:

G = (V (G), E(G), ψG)

dimana

V (G) = {v1, v2, v3, v4, v5}

E(G) = {e1, e2, e3, e4, e5, e6, e7, e8}

dan ψG dapat didefinisikan sebagai

ψG(e1) = v1v2, ψG(e2) = v2v2, ψG(e3) = v2v4, ψG(e4) = v3v4

ψG(e5) = v4v5, ψG(e6) = v5v4, ψG(e7) = v1v5, ψG(e8) = v1v5

Gambar 2.1 Graf G

Graf G pada Gambar 2.1 memiliki 5 titik dan 8 sisi. Graf G terdiri dari him-

punan titik V (G) = {v1, v2, v3, v4, v5} dan himpunan sisi E(G) = {e1, e2, e3, e4,

5

e5, e6, e7, e8}. Sebuah graf yang hanya terdiri dari satu buah titik dan tidak memi-

liki sisi disebut dengan graf trivial. Banyaknya titik di dalam sebuah graf disebut

order dan dinotasikan dengan |V (G)|, sementara banyaknya sisi di dalam sebuah

graf disebut size dan dinotasikan dengan |E(G)|.

Order dan size dari graf G berturut-turut adalah lima dan delapan, dinotasikan

dengan |V (G)| = 5, |E(G)| = 8. Misal u dan v adalah sembarang titik pada graf G

yang mengandung sisi u − v, maka G dikatakan graf terhubung. Jika terdapat dua

titik u dan v dimana tidak mengandung sisi u− v pada graf G, maka graf G disebut

graf tidak terhubung [9].

Graf terhubung dengan sisi berarah disebut dengan directed graph atau graf

berarah, sebaliknya graf terhubung dengan sisi tanpa arah disebut dengan undire-

cted graph atau graf tidak berarah. Berdasarkan jumlah titik dan sisi suatu graf

G = (V,E) dikatakan graf berhingga apabila sisi dan titik berhingga, dan sebalik-

nya apabila sisi dan titik tak berhingga, maka dikatakan graf tidak berhingga [8].

Gambar 2.2 Ilustrasi untuk (a) Graf tidak berarah (b) Graf berarah

Gambar 2.3 Ilustrasi untuk (a) Graf berhingga (b) Graf tidak berhingga

Pada Gambar 2.1 v3 disebut sebagai titik akhir (end vertex) yakni titik yang

memiliki tepat satu buah sisi yaitu e4. Sisi e5, e6 dan sisi e7, e8 disebut sebagai

sisi paralel (multiple edges), yakni dua buah sisi atau lebih yang memliki titik-

6

titik ujung yang sama. Sisi e2 disebut dengan loop. Loop sendiri adalah sisi yang

menghubungkan sebuah titik kepada dirinya sendiri [10].

Sisi dan titik dalam graf mempunyai hubungan yang biasa dikenal dengan ber-

tetangga (adjacent) dan bersisian (incident). Vasudev (2006) mendefinisikan jika

e = (uv) merupakan sisi di graf G, maka u dan v dikatakan titik yang bertetangga

(adjacent vertices). Sedangkan titik u dan sisi e dikatakan saling (incident) be-

gitupun dengan titik v dan sisi e. Jika dua buah sisi berbeda e dan f keduanya

bersisian dengan sebuah titik yang sama maka kedua sisi tersebut dikatakan berte-

tangga (adjacent edges) [8]. Pada Gambar 2.1 titik v3 bertetangga (adjacent verti-

ces) dengan titik v4. Sisi e4 bersisian (incident) dengan titik v3 dan titik v4. Sisi e5

bertetangga (adjacent edges) dengan sisi e3, e4, e6, e7, e8.

Derajat (degree) dari suatu titik v pada graf G, dinotasikan dengan d(v), me-

rupakan jumlah atau banyaknya sisi yang menempel dengan suatu titik vi (loop

dihitung sebagai dua sisi). Daun (pendant vertex) adalah titik yang berderajat sa-

tu [11]. Pada Gambar 2.1, derajat dari masing-masing titik pada graf G adalah

d(v1) = 3, d(v4) = d(v5) = d(v2) = 4, d(v3) = 1. Titik v3 disebut sebagai da-

un karena d(v3) = 1.

Istilah lain yang sering muncul pada pembahasan graf adalah jalan (walk), lin-

tasan (path), dan sirkuit (circuit). Menurut Deo (1989), Jalan (walk) adalah barisan

berhingga dari titik dan sisi, dimulai dan diakhiri dengan titik, sedemikian sehing-

ga setiap sisi menempel dengan titik sebelum dan sesudahnya. Tidak ada sisi yang

muncul lebih dari sekali dalam satu walk. Lintasan (path) merupakan jalan yang se-

mua titiknya berbeda. Sirkuit (circuit) adalah lintasan tertutup (closed path), yaitu

lintasan yang memiliki titik awal dan titik akhir yang sama. Sirkuit dibedakan men-

jadi dua macam, yaitu sirkuit genap dan sirkuit ganjil. Sirkuit genap adalah sirkuit

yang jumlah titiknya genap, dan sirkuit ganjil adalah sirkuit yang jumlah titiknya

ganjil [12]. Pada Gambar 2.1 contoh jalan (walk) adalah v1-e7-v5-e5-v4-e3-v2-e1-v1-

e8-v5; contoh lintasan (path) adalah v5-v1-v2-v4-v3; contoh sirkuit (circuit) adalah

v1-e8-v5-e5-v4-e3-v2-e1-v1.

7

2.2. Beberapa Graf Khusus

Graf khusus yang akan dibahas pada penulisan ini meliputi graf lintasan (Pn),

graf siklus (Cn), dan graf bintang (Sn).

2.2.1. Graf Lintasan

Graf lintasan Pn adalah graf terhubung sederhana dengan |V (Pn)| = |E(Pn)|+

1 yang digambarkan pada semua titik dan sisinya terletak pada garis lurus tunggal.

Graf lintasan dengan n titik dan (n− 1) sisi yang dinotasikan Pn [10]. Gambar 2.4

merupakan contoh graf lintasan dengan n = 2 dan n = 4. Terlihat bahwa pada

graf P2 memiliki jumlah titik 2 dan jumlah sisi 1, sedangkan pada graf P4 memiliki

jumlah titik 4 dan jumlah sisi 3.

Gambar 2.4 Graf Lintasan P2 dan P4

Keterangan :

V (P ) = Himpunan titik-titik (vertex)

E(P ) = Himpunan sisi (edges)

|V (P )| = Banyaknya titik pada graf P

|E(P )| = Banyaknya sisi pada graf P

2.2.2. Graf Lingkaran

Graf lingkaranCn dengan n titik (n ≥ 3) merupakan graf dengan himpunan ti-

tik {v1, v2, . . . , vn} dan himpunan sisi {(v1, v2), (v2, v3), . . . , (v(n−1), vn), (vn, v1)}

[8]. Gambar 2.5 merupakan contoh graf lingkaran C3, C4, dan C5. Terlihat bahwa

pada graf C3 memliki jumlah titik dan sisi sebanyak 3, pada graf C4 memiliki jum-

lah titik dan sisi sebanyak 4, dan graf C5 memiliki jumlah titik dan sisi sebanyak

5.

8

Gambar 2.5 Graf Lingkaran C3, C4 dan C5

2.2.3. Graf Bintang

Graf bintang Sn adalah graf dengan (n + 1) titik, dimana terdapat titik pusat

dengan satu titik berderajat n dan n titik berderajat satu. Gambar 2.6(a) adalah graf

bintang S4 dengan 5 titik, sedangkan gambar 2.6(b) adalah graf bintang S8 dengan

9 titik [10].

Gambar 2.6 (a) Graf S4 (b) Graf S8

2.3. Konsep Bilangan Kromatik Lokasi pada Suatu Graf

Bilangan kromatik lokasi merupakan konsep perpaduan dari pewarnaan titik

dan dimensi partisi pada suatu graf. Pada bagian ini akan dibahas tentang awal

munculnya konsep yang mendasari lahirnya bilangan kromatik lokasi.

2.3.1. Pewarnaan Titik

Menurut Chartrand dan Zhang (2009), Pewarnaan titik pada suatu graf G =

(V,E) merupakan suatu pemetaan c : V → N, dimana N adalah himpunan bi-

langan asli {1, 2, . . . , k} sedemikian sehingga c(u) 6= c(v) untuk setiap u, v ∈

V (G) yang bertetangga. Jika setiap warna yang digunakan sebanyak k warna, ma-

ka graf G mempunyai k-pewarnaan. Bilangan bulat terkecil k sedemikian sehing-

ga G mempunyai suatu pewarnaan-k titik sejati disebut bilangan kromatik dari G,

9

dan dinotasikan dengan χ(G). Jelas bahwa untuk setiap graf G berorde n, berlaku

1 ≤ χ(G) ≤ n [13].

Gambar 2.7 menunjukkan tiga cara melakukan pewarnaan pada graf H . Pe-

warnaan pada gambar 2.7(a) menggunakan 5 warna, pewarnaan pada gambar 2.7(b)

menggunakan 4 warna, sedangkan pewarnaan pada gambar 2.7(c) menggunakan 3

warna. Karena syarat bilangan kromatik adalah bilangan bulat terkecil k sehingga

H mempunyai suatu k-pewarnaan, maka χ(H) = 3.

Gambar 2.7 Pewarnaan pada Graf H

2.3.2. Dimensi Partisi

Konsep dimensi partisi diperkenalkan oleh Chartrand dkk (1998), sebagai sa-

lah satu konsep yang menjadi latar belakang munculnya bilangan kromatik lokasi.

Misalkan G = (V,E) suatu graf, v ∈ V (G), dan S ⊂ V (G). Jarak dari titik v

ke himpunan S, dinotasikan dengan d(v, S) adalah min{d(v, x)|x ∈ S

}dengan

d(v, x) adalah jarak dari titik v ke x. Misalkan Π = {S1, S2, . . . , Sk} adalah partisi

dari V (G) dengan {S1, S2, . . . , Sk} kelas-kelas dari Π. Representasi v terhadap Π,

dinotasikan dengan r(v|Π), adalah koordinat(d(v, S1), d(v, S2), . . . , d(v, Sk)

). Se-

lanjutnya, Π disebut partisi pembeda dari V (G) jika r(u|Π) 6= r(v|Π) untuk setiap

dua titik berbeda u, v ∈ V (G). Dimensi partisi dari G, dinotasikan dengan pd(G),

adalah nilai k terkecil sehingga G mempunyai partisi pembeda dengan k kelas [14].

2.4. Bilangan Kromatik Lokasi

Bilangan kromatik lokasi merupakan konsep pengembangan dari pewarnaan

titik dan dimensi partisi suatu graf yang pertama kali dikaji oleh Chartrand dkk

10

(2002).

Misalkan G = (V,E) adalah graf terhubung dan c suatu pewarnaan-k sejati

dari G. Misalkan Π = {C1, C2, . . . , Ck} merupakan partisi dari himpunan titik

V (G) berdasarkan suatu pewarnaan titik, maka representasi v terhadap Π disebut

kode warna dari v dinotasikan dengan cΠ(v). Kode warna cΠ(v) dari titik v ∈ V (G)

didefinisikan sebagai k-vektor:

cΠ(v) ={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 titik di

G mempunyai kode warna yang berbeda, maka c disebut pewarnaan lokasi dari

G. Nilai terkecil k sedemikian sehingga G mempunyai pewarnaan lokasi dengan

k warna disebut sebagai bilangan kromatik lokasi dari G, dan dinotasikan dengan

χL(G) [1].

Berikut ini adalah teroema dasar tentang bilangan kromatik lokasi menurut

Chartrand dkk.

Teorema 2.4.1 Misalkan c adalah pewarnaan lokasi pada graf terhubung G dan

N(v) merupakan himpunan dari tetangga titik v. 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) 6= c(v). Dalam hal khusus, jika u dan v adalah titik-titik yang

tidak bertetangga di G sedemikian sehingga N(u) = N(v), maka c(u) 6= c(v).

Bukti. Misalkan c adalah suatu pewarnaan lokasi pada graf terhubung G dan mi-

salkan Π = {C1, C2, . . . , Ck} adalah partisi dari titik-titik G kedalam kelas warna

Ci. Untuk suatu titik u, v ∈ V (G), andaikan c(u) = c(v) sedemikian sehingga

titik u dan v berada dalam kelas warna yang sama, misal Ci dari Π. Akibatnya,

d(u,Ci) = d(v, Ci) = 0. Karena d(u,w) = d(v, w) untuk setiapw ∈ V (G)−{u, v}

maka d(u,Cj) = d(v, Cj) untuk setiap j 6= i, 1 ≤ j ≤ k. Akibatnya cΠ(u) = cΠ(v)

sehingga c bukan pewarnaan lokasi. Jadi, c(u) 6= c(v). �

Sebagai contoh, misal diberikan suatu grafG2 dengan V (G2) = {v1, v2, v3, v4, v5, v6}.

Gambar 2.8 memiliki kelas warna Π = {C1, C2, C3}, dengan partisiC1 = {v1, v3, v5},

C2 = {v2, v6}, dan C3 = {v4}. Selanjutnya akan diperoleh kode warna sebagai ber-

11

ikut:

Gambar 2.8 Pewarnaan kromatik lokasi Graf G2 dengan 3 warna

1. cΠ(v1) =(d(v1, C1), d(v1, C2), d(v1, C3)

)= (0, 1, 3)

2. cΠ(v2) =(d(v2, C1), d(v2, C2), d(v2, C3)

)= (1, 0, 2)

3. cΠ(v3) =(d(v3, C1), d(v3, C2), d(v3, C3)

)= (0, 1, 1)

4. cΠ(v4) =(d(v4, C1), d(v4, C2), d(v4, C3)

)= (1, 2, 0)

5. cΠ(v5) =(d(v5, C1), d(v5, C2), d(v5, C3)

)= (0, 1, 1)

6. cΠ(v6) =(d(v6, C1), d(v6, C2), d(v6, C3)

)= (1, 0, 2)

Dari contoh diatas dapat dilihat grafG2 memiliki titik dengan kode warna yang

sama, yaitu cΠ(v2) = cΠ(v6) dan cΠ(v3) = cΠ(v5), sehingga tidak memenuhi syarat

pewarnaan lokasi pada graf G2, akibatnya graf G2 membutuhkan pewarnaan baru

yaitu C4. Misalkan terdapat graf G3 dengan kelas warna Π = {C1, C2, C3, C4}, de-

ngan partisi C1 = {v1, v3}, C2 = {v2, v6}, C3 = {v4}, dan C4 = {v5}. Selanjutnya

akan diperoleh kode warna sebagai berikut:

12

Gambar 2.9 Pewarnaan kromatik lokasi Graf G3 dengan 4 warna

1. cΠ(v1) =(d(v1, C1), d(v1, C2), d(v1, C3), d(v1, C4)

)= (0, 1, 3, 2)


)= (1, 0, 2, 3)


)= (0, 1, 1, 2)


)= (1, 2, 0, 1)


)= (2, 1, 1, 0)


)= (1, 0, 2, 1)

Dapat dilihat pada gambar 2.9 memiliki kode warna yang berbeda. Maka Π dengan

4 warna adalah bilangan kromatik lokasi pada graf G3 sehingga χL(G3) = 4.

2.5. Graf Hasil Kali Kartesian

Hasil kali kartesian adalah hasil kali dari graf G1 =(V (G1), E(G1)

)dan

G2 =(V (G2), E(G2)

)yang dinotasikan G1 ×G2 = G = (V,E) sehingga

V (G) ={

(u1, u2)|ui ∈ V (G1), uj ∈ V (G2)}

dan dua titik (u1, u2) ∈ V (G) dan (v1, v2) ∈ V (G) bertetangga di G = G1 × G2jika dan hanya jika u1 = v1 dan u2v2 ∈ E(G2) atau u2 = v2 dan u1v1 ∈ E(G1) [9].

Berikut ini adalah contoh graf hasil kali kartesian:

13

Gambar 2.10 Graf Sederhana P2 dan S3

Pada gambar 2.10, diketahui V (P2) = {x, y} dan V (S3) = {0, 1, 2, 3} maka

hasil kali kartesian P2 × S3 menghasilkan:

V (P2 × S3) = (x, y)× (0, 1, 2, 3)

={

(x, 0), (x, 1), (x, 2), (x, 3), (y, 0), (y, 1), (y, 2), (y, 3)}

E(P2 × S3) = {e1, e2, e3, e4, e5, e6, e7, e8, e9, e10}

e1 = (x, 1)− (y, 1)

e2 = (x, 1)− (x, 0)

e3 = (y, 1)− (y, 0)

e4 = (x, 0)− (y, 0)

e5 = (x, 0)− (x, 2)

e6 = (y, 0)− (y, 2)

e7 = (x, 2)− (y, 2)

e8 = (x, 0)− (x, 3)

e9 = (y, 0)− (y, 3)

e10 = (x, 3)− (y, 3)

Hasil kali kartesian graf P2 × S3 diperoleh 8 titik dan 9 sisi, dapat dilihat pada

gambar 2.11 berikut ini:

14

Gambar 2.11 Graf Hasil Kali Kartesian P2 × S3

2.6. Graf Buku

Graf buku merupakan suatu graf yang dibentuk dari hasil kali kartesian antara

graf lintasan dengan dua titik dan graf bintang dengan n+ 1 titik yang dinotasikan

Bn = P2 × Sn [16].

Gambar 2.12 (a) Graf B3 dan (b) Graf B4

Pada gambar 2.12(a) merupakan graf buku dengan n = 3 yang memiliki titik

V (B3) = {u0, v0, u1, v1, u2, v2, u3, v3}

Pada gambar 2.12(b) merupakan graf buku dengan n = 4 yang memiliki titik

V (B4) = {u0, v0, u1, v1, u2, v2, u3, v3, u4, v4}

15

BAB III

PEMBAHASAN

Pada bab ini akan diberikan penjelasan hasil penelitian mengenai bilangan kro-

matik lokasi dari graf buku Bn dengan n ≥ 1. Penelitian ini diawali dengan me-

nentukan pewarnaan titik-titik dan menghitung jarak dari semua titik yang sudah

diberi warna ke kelas warna yang ada pada graf buku. Setelah itu akan menda-

patkan kode warna dari hasil perhitungan jarak tiap warna, apabila kode warna

yang dihasilkan berbeda maka jumlah warna terkecil akan menjadi bilangan kro-

matik lokasi pada graf buku. Graf buku yang dibahas pada bab ini adalah graf

B1, B2, B3, B4, B5, B6, B7, danB8.

3.1. Bilangan Kromatik Lokasi Graf Buku untuk n = 1

Gambar 3.1 Graf Buku B1

Pada Gambar 3.1 graf B1 memiliki himpunan titik V (B1) = {u0, v0, u1, v1}.

Misalkan titik u0 diberi pewarnaan C1, maka menurut syarat pewarnaan titik warna

dari semua titik yang bertetangga dengan titik u0 haruslah berbeda. Sehingga titik

v0 diberi warna C2, dapat dilihat pada gambar diatas titik v0 dan u1 tidak saling

bertetangga maka titik u1 dapat diberi warna C2 begitupun dengan titik v1 tidak

bertetangga dengan u0, maka titik v1 dapat diberi warna C1. Akan tetapi pewarnaan

graf B1 dengan dua warna tidak memenuhi syarat pewarnaan lokasi, karena setelah

dihitung jarak tiap warna akan terdapat kode warna yang sama yaitu: cΠ(u0) =

cΠ(v1) dan cΠ(v0) = cΠ(u1).

16

Oleh karena itu terdapat pewarnaan C3, apabila titik v1 diberi warna C3 maka

diperoleh kelas warna Π = {C1, C2, C3} dengan titik-titik pada graf B1 yang telah

dipartisi sebagai berikut C1 = {u0}, C2 = {v0, u1}, C3 = {v1}. Pada graf B1 akan

ditentukan terlebih dahulu batas bawah bilangan kromatik lokasi graf Bn. Selanjut-

nya akan diilustrasikan pewarnaan lokasi graf B1 dengan tiga warna pada Gambar

3.2 dan akan didapatkan kode warna dari graf B1 sebagai berikut:

Gambar 3.2 Pewarnaan Lokasi 3 warna pada Graf B1

1. cΠ(u0) =(d(u0, C1), d(u0, C2), d(u0, C3)

)= (0, 1, 2)

2. cΠ(v0) =(d(v0, C1), d(v0, C2), d(v0, C3)

)= (1, 0, 1)

3. cΠ(u1) =(d(u1, C1), d(u1, C2), d(u1, C3)

)= (1, 0, 1)

4. cΠ(v1) =(d(v1, C1), d(v1, C2), d(v1, C3)

)= (2, 1, 0)

Dapat dilihat bahwa terdapat kode yang sama, yaitu: cΠ(v0) = cΠ(u1) maka

hal ini kontradiksi, akibatnya tidak memenuhi syarat pewarnaan lokasi. Oleh karena

itu, tiga warna tidak cukup untuk pewarnaan lokasi pada graf B1. Maka dibutuhkan

sekurang-kurangnya empat warna untuk mewarnai graf B1, dimana pewarnaan C4

dapat mewakili titik v0 atau u1. Sehingga diperoleh batas bawah pewarnaan lokasi

χL(Bn) ≥ 4 dengan n ≥ 1.

17



Pada Gambar 3.3 graf B2 memiliki himpunan titik V (B2) = {V (B1), u2, v2}.

Misalkan pada graf B2 diberi pewarnaan yang sama seperti graf B1 dimana titik u1

diberi warna C4, dan dapat dilihat pada graf B2 bahwa titik u2 bertetangga dengan

u0 maka kode warna c(u2) 6= c(u0) sedangkan titik v2 bertetangga dengan v0 maka

c(v2) 6= c(v0). Andaikan titik u2 diberi warna C3 dan titik v2 diberi warna C1maka akan diperoleh kelas warna Π = {C1, C2, C3, C4} dengan titik-titik yang telah

dipartisi sebagai berikut C1 = {u0, v2}, C2 = {v0}, C3 = {v1, u2}, C4 = {u1}.

Selanjutnya akan diilustrasikan pewarnaan lokasi grafB2 dengan empat warna pada

Gambar 3.4 dan akan didapatkan kode warna sebagai berikut:


1. cΠ(u0) =(d(u0, C1), d(u0, C2), d(u0, C3), d(u0, C4)

)= (0, 1, 1, 1)


)= (1, 0, 1, 2)


)= (1, 2, 1, 0)

18


)= (2, 1, 0, 1)


)= (1, 2, 0, 2)


)= (0, 1, 1, 3)

Dapat dilihat kode warna dari titik-titik graf B2 berbeda, maka C merupakan

pewarnaan lokasi dengan empat warna sehingga χL(B2) = 4.




Misalkan pada graf B3 diberi pewarnaan yang sama seperti graf B2, dan dapat di-

lihat pada graf B3 bahwa titik u3 bertetangga dengan u0 maka kode warna c(u3) 6=

c(u0) sedangkan titik v3 bertetangga dengan v0 maka kode warna c(v3) 6= c(v0).

Andaikan titik u3 diberi warna C4 dan titik v3 diberi warna C1 maka akan diperoleh

kelas warna Π = {C1, C2, C3, C4} dengan titik-titik yang telah dipartisi sebagai

berikut C1 = {u0, v2, v3}, C2 = {v0}, C3 = {v1, u2}, C4 = {u1, u3}. Selanjutnya

akan diilustrasikan pewarnaan lokasi graf B3 dengan empat warna pada Gambar

3.6 dan akan didapatkan kode warna sebagai berikut:

19



)= (0, 1, 1, 1)


)= (1, 0, 1, 2)


)= (1, 2, 1, 0)


)= (2, 1, 0, 1)


)= (1, 2, 0, 2)


)= (0, 1, 1, 3)


)= (1, 2, 2, 0)


)= (0, 1, 2, 1)



20









berikut C1 = {u0, v2, v3}, C2 = {v0, u4}, C3 = {v1, u2}, C4 = {u1, u3, v4}. Se-

lanjutnya akan diilustrasikan pewarnaan lokasi graf B4 dengan empat warna pada




)= (0, 1, 1, 1)

21


)= (1, 0, 1, 1)


)= (1, 2, 1, 0)


)= (2, 1, 0, 1)


)= (1, 2, 0, 2)


)= (0, 1, 1, 2)


)= (1, 2, 2, 0)


)= (0, 1, 2, 1)


)= (1, 0, 2, 1)


)= (2, 1, 2, 0)





Pada Gambar 3.9 graf B5 memiliki himpunan titik V (B5) = {V (B4), u5,

v5}. Misalkan pada graf B5 diberi pewarnaan yang sama seperti graf B4, dan dapat

dilihat pada grafB5 bahwa titik u5 bertetangga dengan u0 maka kode warna c(u5) 6=


22



berikut C1 = {u0, v2, v3}, C2 = {v0, u4, u5}, C3 = {v1, u2, v5}, C4 = {u1, u3, v4}.





)= (0, 1, 1, 1)


)= (1, 0, 1, 1)


)= (1, 2, 1, 0)


)= (2, 1, 0, 1)


)= (1, 2, 0, 2)


)= (0, 1, 1, 2)


)= (1, 2, 2, 0)


)= (0, 1, 2, 1)


)= (1, 0, 2, 1)


)= (2, 1, 2, 0)


)= (1, 0, 1, 2)

23


)= (2, 1, 0, 2)





Pada Gambar 3.11 grafB6 memiliki himpunan titik V (B6) = {V (B5), u6, v6}.




Andaikan titik u6 diberi warna C3 dan titik v6 diberi warna C4 maka akan di-

peroleh kelas warna Π = {C1, C2, C3, C4} dengan titik-titik yang telah diparti-

si sebagai berikut C1 = {u0, v2, v3}, C2 = {v0, u4, u5}, C3 = {v1, u2, v5, u6},

C4 = {u1, u3, v4, v6}. Selanjutnya akan diilustrasikan pewarnaan lokasi graf B6dengan empat warna pada Gambar 3.12 dan akan didapatkan kode warna sebagai

berikut:

24



)= (0, 1, 1, 1)


)= (1, 0, 1, 1)


)= (1, 2, 1, 0)


)= (2, 1, 0, 1)


)= (1, 2, 0, 2)


)= (0, 1, 1, 2)


)= (1, 2, 2, 0)


)= (0, 1, 2, 1)


)= (1, 0, 2, 1)


)= (2, 1, 2, 0)


)= (1, 0, 1, 2)


)= (2, 1, 0, 2)


)= (1, 2, 0, 1)

25


)= (2, 1, 1, 0)






Misalkan pada graf B7 diberi pewarnaan yang sama seperti graf B6, dan dapat dili-

hat pada graf B7 bahwa titik u7 bertetangga dengan u0 maka warna c(u7) 6= c(u0)

dan titik v7 bertetangga dengan v0 maka warna c(v7) 6= c(v0). Andaikan titik

u7 diberi warna C2 dan titik v7 diberi warna C1 maka akan diperoleh kelas war-

na Π = {C1, C2, C3, C4} dengan titik yang telah dipartisi sebagai berikut C1 =

{u0, v2, v3, v7}, C2 = {v0, u4, u5, u7}, C3 = {v1, u2, v5, u6}, C4 = {u1, u3, v4, v6}.



26



)= (0, 1, 1, 1)


)= (1, 0, 1, 1)


)= (1, 2, 1, 0)


)= (2, 1, 0, 1)


)= (1, 2, 0, 2)


)= (0, 1, 1, 2)


)= (1, 2, 2, 0)


)= (0, 1, 2, 1)


)= (1, 0, 2, 1)


)= (2, 1, 2, 0)


)= (1, 0, 1, 2)


)= (2, 1, 0, 2)

27


)= (1, 2, 0, 1)


)= (2, 1, 1, 0)


)= (1, 0, 2, 2)


)= (0, 1, 2, 2)







lihat pada graf B1 sampai graf B7 terdapat kombinasi dua warna untuk pasangan

titik terluar, yaitu titik {(u1 = 4, v1 = 3), (u2 = 3, v2 = 1), (u3 = 4, v3 = 1), (u4 =

2, v4 = 4), (u5 = 2, v5 = 3), (u6 = 3, v6 = 4), dan (u7 = 2, v7 = 1)}. Karena

kombinasi dua titik dari 4 warna sudah tidak bisa digunakan lagi, akibatnya pada

graf B8 harus terdapat warna baru yaitu C5. Andaikan titik u8 diberi warna C5 dan

titik v8 diberi warna C1 maka akan diperoleh kelas warna Π = {C1, C2, C3, C4, C5}

28

dengan titik-titik yang telah dipartisi sebagai berikut C1 = {u0, v2, v3, v7}, C2 =

{v0, u4, u5, u7}, C3 = {v1, u2, v5, u6}, C4 = {u1, u3, v4, v6}, C5 = {u8}. Selanjut-

nya akan diilustrasikan pewarnaan lokasi graf B8 dengan lima warna pada Gambar

3.16 dan akan didapatkan kode warna sebagai berikut:


1. cΠ(u0) =(d(u0, C1), d(u0, C2), d(u0, C3), d(u0, C4), d(u0, C5)

)= (0, 1, 1, 1, 1)

2. cΠ(v0) =(d(v0, C1), d(v0, C2), d(v0, C3), d(v0, C4), d(v0, C5)

)= (1, 0, 1, 1, 2)


)= (1, 2, 1, 0, 2)


)= (2, 1, 0, 1, 3)


)= (1, 2, 0, 2, 2)


)= (0, 1, 1, 2, 3)


)= (1, 2, 2, 0, 2)


)= (0, 1, 2, 1, 3)


)= (1, 0, 2, 1, 2)


)= (2, 1, 2, 0, 3)

29


)= (1, 0, 1, 2, 2)


)= (2, 1, 0, 2, 3)


)= (1, 2, 0, 1, 2)


)= (2, 1, 1, 0, 3)


)= (1, 0, 2, 2, 2)


)= (0, 1, 2, 2, 3)


)= (1, 2, 2, 2, 0)


)= (0, 1, 2, 2, 1)


pewarnaan lokasi dengan lima warna sehingga χL(B8) = 5.

3.9. Konstruksi Hipotesis

Berdasarkan hasil penelitian yang telah dijelaskan diatas, penulis mendapatk-

an bilangan kromatik lokasi pada graf B1 sampai graf B7 adalah 4, yang diperoleh

dengan memberi semua kombinasi dua warna yang memungkinkan pada pasangan

titik terluar, dimana pasangan titik terluar yang bertetangga dengan titik u0 dan ti-

tik v0 tidak boleh diberi kode warna yang sama. Sehingga pada kasus B8 haruslah

terdapat warnaC5, karena kombinasi dua warna pada pasangan titik terluar dari em-

pat kelas warna (C1, C2, C3, C4) yang penulis jabarkan diatas hanya dapat mewakili

graf B1 sampai B7.

Bilangan kromatik lokasi dapat diberi pewarnaan dengan 5 kelas warna (C1, C2

, C3, C4, C5) untuk mewakili pewarnaan pada graf B8 sampai graf B13 dengan dua

kombinasi warna pada pasangan titik terluar yaitu : B8 = (C1, C5), B9 = (C2, C5),

B10 = (C3, C5), B11 = (C5, C3), B12 = (C4, C5), B13 = (C5, C4). Sehingga pe-

nulis mengkonstruksikan suatu hipotesis atas rumus bilangan kromatik lokasi pada

graf Buku Bn adalah sebagai berikut:

30

χL(Bn) =

4 , jika 1 ≤ n ≤ 7

5 , jika 8 ≤ n ≤ 13

6 , jika 14 ≤ n ≤ 21

7 , jika 22 ≤ n ≤ 31...

atau secara rumusan umum

χL(Bn) = min

{k : n ≤ 2

(k − 2

2

)+ 2(k − 1)− 1

}, untuk k ≥ 4

3.10. Bilangan Kromatik Lokasi Graf Buku Bn

Gambar 3.17 Graf Buku Bn

Sebelum membuktikan hipotesis umum, penulis akan terlebih dahulu mem-

buktikan beberapa lema yang akan digunakan untuk hasil umum.

Lema 3.10.1 Misalkan terdapat suatu partisi Π untuk pewarnaan graf Bn dengan

n ≥ 1, dan himpunan titik V (Bn) = {ui, vi| i = 0, 1, 2, . . . , n}. Untuk setiap titik

ui dan vi, i = 0, 1, 2, . . . , n harus termuat dalam kelas warna berbeda di Π, dengan

kata lain c(ui) 6= c(vi), untuk i = 0, 1, 2, . . . n.

Bukti. Jelas bahwa setiap titik ui bertetangga dengan titik vi, sehingga menurut sifat

pewarnaan titik pada suatu graf haruslah c(ui) 6= c(vi) untuk i = 0, 1, 2, . . . , n. �

31


n ≥ 1, dan himpunan titik V (Bn) = {ui, vi| i = 0, 1, 2, . . . , n}. Titik u0 dengan uidan titik v0 dengan vi untuk i = 1, 2, . . . , n harus termuat dalam kelas warna ber-

beda di Π dengan kata lain c(u0) 6= c(ui) dan c(v0) 6= c(vi) untuk i = 1, 2, . . . , n.

Bukti. Jelas bahwa titik u0 bertetangga dengan titik ui untuk i = 1, 2, . . . , n, dan

titik v0 bertetangga dengan titik vi untuk i = 1, 2, . . . , n. Sehingga menurut sifat

pewarnaan titik pada suatu graf haruslah c(u0) 6= c(ui) dan c(v0) 6= c(vi) untuk

i = 1, 2, . . . , n. �


n ≥ 1, dan himpunan titik V (Bn) = {ui, vj| i, j = 0, 1, 2, . . . , n}. Untuk setiap pa-

sangan terurut kode warna titik pada bagian lembaran terluar selain(c(u0), c(v0)

),

yaitu pasangan terurut(c(ui), c(vi)

)dan pasangan terurut

(c(uj), c(vj)

)untuk

i, j = 1, 2, . . . , n harus memiliki kode warna yang berbeda dengan kata lain(c(ui),

c(vi))6=(c(uj), c(vj)

).

Bukti. Asumsikan sebaliknya(c(ui), c(vi)

)=(c(uj), c(vj)

). Misalkan terdapat

pewarnaan C1 = (u0), C2 = (v0), Cx := c(ui) = c(uj) dan Cy := c(vi) = c(vj)

seperti pada gambar 3.18, maka kode warna yang diperoleh sebagai berikut:

Gambar 3.18 Ilustrasi Lema 3.10.3

1. cΠ(ui) =(d(ui, C1), d(ui, C2), . . . , d(ui, Cx), . . . , d(ui, Cy), . . . )

)= (1, 2, . . . , 0, . . . , 1, . . . )

32

2. cΠ(uj) =(d(uj, C1), d(uj, C2), . . . , d(uj, Cx), . . . , d(uj, Cy), . . . )

)= (1, 2, . . . , 0, . . . , 1, . . . )

Untuk mencari kode warna diatas yang belum diperoleh, misalkan w ∈ V (Bn)

sembarang dengan c(w) = Ck, dan misalkan terdapat sembarang pasangan titik

{ua, va} dan {ub, vb}.

Kasus 1

Apabila w = ut untuk suatu t ∈ {1, 2, . . . , n} selain {a, b} maka pada gambar 3.19

diperoleh d(ua, Ck) = 2 dan d(ub, Ck) = 2 yang berarti d(ua, Ck) = 2 = d(ub, Ck)

untuk setiap k = 3, 4, . . . , x− 1, x+ 1, . . . , y − 1, y + 1, . . . .

Gambar 3.19 Ilustrasi Kasus 1

Kasus 2

Apabila w = vt untuk suatu t ∈ {1, 2, . . . , n} selain {a, b} maka pada gambar 3.20

diperoleh d(ua, Ck) = 3 dan d(ub, Ck) = 3 yang berarti d(ua, Ck) = 3 = d(ub, Ck)

untuk setiap k = 3, 4, . . . , x− 1, x+ 1, . . . , y − 1, y + 1, . . . .

33


karena (i) d(ua, C1) = 1 = d(ub, C1)

(ii) d(ua, C2) = 2 = d(ub, C2)

(iii) d(ua, Cx) = 0 = d(ub, Cx)

(iv) d(ua, Cy) = 1 = d(ub, Cy)

(v) d(ua, Ck) = d(ub, Ck)

untuk k = 3, 4, . . . , x− 1, x+ 1, . . . , y − 1, y + 1, . . .

Maka cΠ(ua) = cΠ(ub) yang berarti C bukan pewarnaan kromatik lokasi. �

Lema 3.10.4 Apabila pewarnaan kromatik lokasi untuk graf buku Bn memerlukan

k warna maka haruslah n ≤ 2(k−2

2

)+ 2(k − 1)− 1 dengan k ≥ 4

Bukti. Mulai pewarnaan graf dengan memberi warna C1 dan C2 untuk titik-titik

yang ada di tengah, yaitu c(u0) = C1 dan c(v0) = C2. Dari lema 3.10.2 haruslah

c(ui) 6= C1 dan c(vi) 6= C2 untuk setiap i = 1, 2, . . . , n.

Kasus 1

Misalkan(c(ua), c(va)

)sama sekali tidak mengandung warna C1 maupun C2. Ma-

ka total warna yang bisa dipilih adalah(k−2

2

)× 2 karena disetiap bagian luar dari

lembar buku akan membutuhkan 2 warna yang harus berbeda dari lema 3.10.1, yang

berarti ada(k−2

2

)kemungkinan. Namun, karena c(ua) dan c(va) bisa dibalik tanpa

konsekuensi, maka total yang bisa dipakai adalah(k−2

2

)× 2.

34

Kasus 2

Jika c(ua) = 2, maka total kemungkinan warnanya yang bisa dipakai adalah (k−1)

karena c(va) hanya bisa diberi warna 1, 3, 4, . . . , k. Dimana warna 1 hanya dapat

dipakai pada graf buku Bn untuk n ≥ 2. Seperti pada ilustrasi dibawah ini.


Kasus 3

Jika c(va) = 1, maka total warna yang bisa dipakai adalah (k − 1) karena c(ua)

hanya bisa diberi warna 2, 3, 4, . . . , k. Dimana warna 2 hanya dapat dipakai pada

graf buku Bn untuk n ≥ 2. Seperti pada ilustrasi dibawah ini.


35

Karena pewarnaan c(va) = 1 dan c(ua) = 2 sudah digunakan pada kasus 2, maka

pewarnaan ini tidak dapat digunakan lagi, jadi total pewarnaan = (k−1)−1. Maka

jika χL(Bn) memakai k warna, harus memenuhi

n ≤ 2(k − 2

2

)+ (k − 1) + (k − 1)− 1

n ≤ 2(k − 2

2

)+ 2(k − 1)− 1

�

Teorema 3.10.5 Bilangan Kromatik Lokasi untuk graf buku Bn adalah

χL(Bn) = min

{k : n ≤ 2

(k − 2

2

)+ 2(k − 1)− 1

}, untuk k ≥ 4

Bukti. Pertama-tama, akan ditunjukkan keberadaan bilangan χL(Bn) tersebut. Ka-

rena n ∈ N jelas bahwa{k : n ≤ 2

(k−2

2

)+ 2(k − 1)− 1

}merupakan himpunan

bagian dari himpunan bilangan asli. Maka dari well-ordering principle, himpunan

tersebut pasti punya elemen terkecil. Misal

k∗ := min

{k : n ≤ 2

(k − 2

2

)+ 2(k − 1)− 1

}Dari Lema 3.10.4, telah terbukti bahwa terdapat pewarnaan kromatik lokasi dengan

k∗ warna. Sekarang akan ditunjukkan bahwa χL(Bn) = k∗, yaitu bahwa pewarnaan

kromatik lokasi graf Bn minimal membutuhkan k∗ warna. Asumsikan sebaliknya,

yaitu terdapat pewarnaan kromatik lokasi yang menggunakan tepat (k∗− 1) warna.

Ini berarti

(k∗ − 1) ∈{k : n ≤ 2

(k − 2

2

)+ 2(k − 1)− 1

}yang mengakibatkan

(k∗ − 1) ≥ min{k : n ≤ 2

(k − 2

2

)+ 2(k − 1)− 1

}= k∗

Ini merupakan suatu kontradiksi, yang berarti tidak mungkin ada pewarnaan kro-

matik lokasi graf buku Bn yang menggunakan (k∗ − 1) warna. Maka haruslah

χL(Bn) = k∗ = min

{k : n ≤ 2

(k − 2

2

)+ 2(k − 1)− 1

}, untuk k ≥ 4

�

36

Akibat 3.10.6 Bilangan kromatik lokasi untuk graf buku Bn adalah

χL(Bn) =

⌈√n− 3

4+

3

2

⌉Bukti. Misal k adalah warna yang dibutuhkan untuk pewarnaan kromatik lokasi

graf buku Bn, maka

n ≤ 2(k − 2

2

)+ 2(k − 1)− 1

n ≤ (k − 2)(k − 3)2

× 2 + 2k − 2− 1

(k2 − 5k + 6 + 2k − 3) ≥ n

k2 − 3k + 3 ≥ n(k − 3

2

)2− 9

4+ 3 ≥ n(

k − 32

)2+

3

4≥ n(

k − 32

)2≥ n− 3

4

k ≥√n− 3

4+

3

2

Maka k terkecil yang mungkin adalah

kmin =

⌈√n− 3

4+

3

2

⌉

�

37

BAB IV

PENUTUP

4.1. Kesimpulan

Bilangan kromatik lokasi pada graf buku yang telah ditemukan adalah:

χL(Bn) = min

{k : n ≤ 2

(k − 2

2

)+ 2(k − 1)− 1

}, untuk k ≥ 4

atau

kmin =

⌈√n− 3

4+

3

2

⌉

4.2. Saran

Saran yang dapat diberikan pada penelitian ini yaitu melakukan penilitian un-

tuk menentukan bilangan kromatik lokasi pada graf buku secara umum Bm,n =

Pm× Sn atau graf lain melalui operasi – operasi yang ada pada graf seperti operasi

join, amalgamasi, korona, dll.

38

REFERENSI

[1] Chartrand, G., Erwin, D., Henning, M., Slater, P., and Zhang, P., ”The

locating-chromatic number of a graph”, Bull. Inst. Combin. Appl., vol. 36,

pp. 89 – 101, 2002.

[2] Asmiati, H. Assiyatun and E.T Baskoro, ”Locating-chromatic number of

amalgamation of stars”, ITB J.Sci., vol. 43A, no.1,pp. 1-8, 2011.

[3] A. Behtoei and B. Omoomi, ”On the Locating Chromatic Number of the Car-

tesian Product of Graphs”, Ars Comb., vol. 126, pp. 221–235, 2012.

[4] D. Welyyanti, E.T. Baskoro, R.Simanjuntak and S. Uttunggadewa, ”On

locating-chromatic number of complete n-ary Tree”, AKCE Int. J.Graph

Comb., vol.3, no.3, pp.309-315, 2013.

[5] D. Welyyanti, E.T. Baskoro, R.Simanjuntak and S. Uttunggadewa, ”The

Locating-Chromatic Number of Disconnected Graphs”, Far East J.Math. Sci.,

vol. 94, no. 2, pp. 169–182, 2014.

[6] C.D. Rianti and N., ”Bilangan Kromatik Lokasi Dari Graf Spinner”, Jurnal

Matematika UNAND,vol. VII, no. 4, pp. 19-23, 2018.

[7] E. K. Lloyd, J. A. Bondy, and U. S. R. Murty, Graph Theory with Applications,

Math. Gaz., vol. 62, no. 419, p. 63, 1978.

[8] Vasudev C(2006), Graph Theory with Applications. New Delhi: New Age In-

ternational.

[9] Chartrand, dkk. (2005). Applied and Algoritmic Graph Theory. New York:

Mac Graw-Hill, inc.

[10] Gross, J.L dan Jay Yellen.(2006). Graph Theory and Its Applications, 2nd

edition. Chapman and Hall/CRC. New York.

39

[11] G. Chartrand dan P. Zhang, Introduction to Graph Theory, New York:

McGraw Hill, 2005.

[12] Deo. N. 1989. Graph Theory with Applications to Engineering and computer

Science. Prentice Hall Inc, New York.

[13] Chartrand, G., and Zhang, P., (2009): Chromatic Graph Theory, Chapman and

Hall/CRC,New York.

[14] Chartrand, G., Salehi, E., and Zhang, P., (1998): On the partition dimension

of graph, Congr. Numer., 130, 157 – 168.

[15] Chartrand, G., dkk., 2016, Graphs and Digraphs, Sixth Edition, Chapman and

Hall/CRC, London

[16] J. A. Gallian, A Dynamic Survey of Graph Labeling, Electron. J. Comb.,

pp.1219, 2009.

40

DAFTAR GAMBARPENDAHULUANLatar Belakang MasalahPerumusan PermasalahanPembatasan PermasalahanTujuan PenelitianManfaat Penelitian

LANDASAN TEORIKonsep Dasar GrafBeberapa Graf KhususGraf LintasanGraf LingkaranGraf Bintang

Konsep Bilangan Kromatik Lokasi pada Suatu GrafPewarnaan TitikDimensi Partisi

Bilangan Kromatik LokasiGraf Hasil Kali KartesianGraf Buku

PEMBAHASANBilangan Kromatik Lokasi Graf Buku untuk n=1Bilangan Kromatik Lokasi Graf Buku untuk n=2Bilangan Kromatik Lokasi Graf Buku untuk n=3Bilangan Kromatik Lokasi Graf Buku untuk n=4Bilangan Kromatik Lokasi Graf Buku untuk n=5Bilangan Kromatik Lokasi Graf Buku untuk n=6Bilangan Kromatik Lokasi Graf Buku untuk n=7Bilangan Kromatik Lokasi Graf Buku untuk n=8Konstruksi HipotesisBilangan Kromatik Lokasi Graf Buku Bn

PENUTUPKesimpulanSaran

REFERENSIHALAMAN PENGESAHANHALAMAN PERNYATAANHALAMAN PERSEMBAHANHALAMAN MOTTOKATA PENGANTARDAFTAR ISIDAFTAR GAMBARINTISARIABSTRACTPENDAHULUANLatar Belakang MasalahPerumusan PermasalahanPembatasan PermasalahanTujuan PenelitianManfaat Penelitian

LANDASAN TEORIKonsep Dasar GrafBeberapa Graf KhususGraf LintasanGraf LingkaranGraf Bintang

Konsep Bilangan Kromatik Lokasi pada Suatu GrafPewarnaan TitikDimensi Partisi

Bilangan Kromatik LokasiGraf Hasil Kali KartesianGraf Buku

PEMBAHASANBilangan Kromatik Lokasi Graf Buku untuk n=1Bilangan Kromatik Lokasi Graf Buku untuk n=2Bilangan Kromatik Lokasi Graf Buku untuk n=3Bilangan Kromatik Lokasi Graf Buku untuk n=4Bilangan Kromatik Lokasi Graf Buku untuk n=5Bilangan Kromatik Lokasi Graf Buku untuk n=6Bilangan Kromatik Lokasi Graf Buku untuk n=7Bilangan Kromatik Lokasi Graf Buku untuk n=8Konstruksi HipotesisBilangan Kromatik Lokasi Graf Buku Bn

PENUTUPKesimpulanSaran

REFERENSI

bilangan kromatik lokasi pada graf...

Documents