III. 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 : ( ) → {1,2,3, … , } dengan syarat untuk setiap dua titik yang bertetangga harus memiliki warna yang berbeda. Minimum banyaknya
warna yang digunakan untuk pewarnaan titik pada graf disebut bilangan kromatik, yang dinotasikan ( ). v2
1
v1
1
v3
2
v5
2
v6 2
v4 1
v7
2
Gambar 15. Contoh bilangan kromatik dengan ( ) = 2 Berikut ini diberikan definisi bilangan kromatik lokasi graf yang diambil dari (Chartrand, dkk, 2002). Misalkan c ( ) ≠ ( ) untuk u dan
suatu pewarnaan titik pada graf G dengan
yang bertetangga di G. Misalkan
himpunan titik–titik
yang diberi warna i, yang selanjutnya disebut kelas warna, maka Π = { ,
,…,
}
21
adalah himpunan yang terdiri dari kelas – kelas warna dari V(G). Kode warna dari v adalah k-pasang terurut
( ,
), ( ,
), … , ( ,
) dengan
( ,
( )
) =
} untuk 1 ≤ ≤ . Jika setiap G mempunyai kode warna yang
min{ ( , )| ∈
berbeda, maka c disebut pewarnaan lokasi G. Banyaknya warna minimum yang digunakan untuk pewarnaan lokasi disebut bilangan kromatik lokasi dari G, dan ( ). Karena setiap pewarnaan lokasi juga merupakan
dinotasikan dengan
pewarnaan, maka ( ) ≤
( ).
Teorema 3.1 (Chartrand dkk, 2002) Misal graf terhubung
. Jika
dan
( , ) = ( , ) untuk setiap
khusus, jika
dan
( )≠
sehingga
adalah suatu pewarnaan lokasi pada
adalah dua titik pada graf
sedemikian sehingga
∈ ( ) ∖ { , }, maka ( ) ≠ ( ). Dalam hal
adalah titik-titik yang tidak bertetangga di
sedemikian
( ) , maka ( ) ≠ ( ).
Bukti: Misalkan
adalah suatu pewarnaan lokasi pada graf terhubung
misalkan Π = { ,
,…,
Untuk titik berada ( ,
,
dalam )= ( ,
maka ( , sehingga
} adalah partisi dari titik-titik
ke dalam kelas warna
( ), andaikan ( ) = ( ) sedemikian sehingga titik
kelas
warna
)= 0. Karena
)= ( ,
yang
sama,
misal
dari
( , ) = ( , ) untuk setiap
) untuk setiap
≠ , 1 ≤ ≤ . Akibatnya,
bukan pewarnaan lokasi. Jadi ( ) ≠ ( ).
dan
Π.
.
dan
Akibatnya,
∈ ( )∖{ , } ( )=
( ) ■
22
Akibat 3.1 (Chartrand dkk, 2002) Jika suatu titik yang bertetangga dengan
Bukti: Misalkan
adalah suatu graf terhubung yang memuat ( )≥
daun di , maka
adalah suatu titik yang bertetangga dengan
. Berdasarkan Teorema 3.1, setiap pewarnaan lokasi dari , = 1,2, … , . Karena
yang berbeda untuk setiap maka
+ 1. daun
+ 1.
,…,
di
mempunyai pewarnaan
bertetangga dengan semua
harus mempunyai warna yang berbeda dengan semua daun
( )≥
,
,
. Akibatnya ■
v22
v3 3
v1
v 71
v8 2 v9
2 1
v4
v6 3
4
v5 1
Gambar 16. Contoh pewarnaan lokasi minimum pada Graf
Teorema 3.2 (Chartrand dkk, 2003) Misalkan maka
( )≤
adalah derajat maksimum di graf
+ 1.
Beberapa teorema penelitian sebelumnya yang mendukung penelitian ini adalah sebagai berikut. Teorema 3.3 (Chartrand dkk, 2002) Bilangan kromatik lokasi graf lintasan ( ≥ 3) adalah 3.
23
Bukti: Perhatikan bahwa
( ) = 2 . Jelaslah bahwa
derajat titik
= 2 maka
( ) ≤ 2 + 1. Akibatnya
( ) ≤ 3.
( )≤
≥ 3 . Berdasarkan Teorema 3.2.
untuk
maksimum. Karena pada Jadi,
( ) = 1 dan ,
( ) ≤ 3. 1
2
3
v1
v2
v3
1 v4
2
v5
+ 1, dengan
( )≥3
■
1
2
1
v6
vn1
vn
Gambar 17. Pewarnaan lokasi minimum pada graf lintasan
Teorema 3.4 (Chartrand dkk, 2002)
Untuk bilangan bulat
dan
Bukti: Berdasarkan Akibat 3.1, diperoleh batas bawah yaitu
,
1≤
≤
dan
≥ 2,
,
=
dengan
+1.
Selanjutnya, akan ditentukan batas atasnya, yaitu
≤
,
≥
+ 1.
+ 1. Misalkan
adalah pewarnaan titik menggunakan ( + 1) warna sebagaimana terlihat pada Gambar 18. Perhatikan bahwa kode warna dari setiap titik adalah pewarnaan lokasi.Jadi,
,
≤
+ 1.
,
berbeda, akibatnya
■
24
1
2
2 b 1
a
3
1
v
u
a 1
b
Gambar 18. Pewarnaan lokasi minimum pada Graf
Teorema 3.5 (Chartrand dkk, 2002) mempunyai bilangan kromatik
u2
k
1
2
v1
v2
v3
1 v4
2
vnk 1
Gambar 19. Pohon T dari berorde
Bukti: Pertama misalkan = , misalkan
pada
=
,
,
,…,
. Berikanlah warna
jika ≥ 3 dan
dengan
∈ {3, 4, … , − 2, }. Untuk
didapat dari lintasan
( − 1) titik baru dengan
∈ {3, 4, … , − 2, }.
jika dan hanya jika
u1
k 1 uk 1
Misalkan
≥ 5 yang
Terdapat pohon berorde
1
2
untuk
,
= 3, misalkan
. Sehingga diasumsikan bahwa 4 ≤ :
,
,…,
pada
, warna 1 pada pada
≤
=
,
− 2.
dengan menambahkan
dan hubungkan setiap
ganjil, dan warna
Gambar 19. Dengan demikian
( )=
, untuk 1 ≤ ≤
jika
−1
genap , warna 2
, untuk 1 ≤ ≤
( ) adalah pewarnaan lokasi,
− 1 lihat ( )≤ .
25
( )≥
berdasarkan akibat 3.1
( )= .
maka
Lemma 3.2 (Asmiati dkk, 2011) Misalkan menggunakan paling sedikit pewarnaan
lokasi
jika
( ) = 1,2,3, … ,
− 1 dan
yang berbeda.
=
Bukti:
Misalkan
1,2,3, … ,
− 1}. Misalkan
(
∈
∖
) = 1,2,3, … ,
( ) = 1,2,3, … ,
dan
≠
kelas-kelas warna |Π| ≥
−1
dan
Jelas bahwa ordinat ke-
Jika
(
( )≠ (
={ ( ( ≥ 2,
) =
≥ 2 dan
=
. Karena ( , ) = ( , ) untuk
sama. Jadi
bukan pewarnaan lokasi, suatu
−1 ∪
=
sedemikian sehingga ( ∈ ,
atau ke- . )≠
,
,
(
) = 1,2,3, … ,
−1 ,
( ) dari terhadap
≠ , maka
∉ ) atau ( ∈ ,
Selanjutnya akan ditunjukkan bahwa kode warna untuk setiap
adalah
mengakibatkan
. Pandang ( ) = ( ), ≠ . Karena
dan
,
− 1 adalah dua himpunan
≠ . Misalkan Π suatu partisi dari
kontradiksi. Akibatnya
terdapat warna
≥ 2. Pewarnaan
adalah pewarnaan lokasi dari
( ) = 1,2,3, … ,
maka kode warna dari
,
( ) = ( ),
hanya
( ) = ( ), untuk suatu ≠ . Andaikan
setiap
adalah pewarnaan lokasi dari
warna dengan
dan
■
∈
,
.
∉ ).
( ), karena kedua kode warna tersebut berbeda pada
), untuk setiap
≠
, dibagi menjadi dua kasus.
26
Kasus 1:
Jika ( ) = ( ), maka berdasarkan premis dari teorema ini, (
)≠
(
) karena kedua kode warna tersebut berbeda sekurang-kurangnya
Kasus 2: Misalkan
(
).
( )=
( )= (
Jika
( )=
dan
pada ordinat yang ke
≠ . Jadi
dan
≠
, dengan
(
. Maka
)≠
.
), maka kode warna dari ( )=
komponen yang bernilai 1. Akibatnya
(
( ) memuat sedikitnya dua ).
Berdasarkan semua kasus di atas, dapat dilihat bahwa kode warna untuk semua titik di
,
berbeda, maka
merupakan pewarnaaan lokasi.
Lemma 3.3 (Asmiati dkk, 2011) Misalkan +
menggunakan ≤
( ).
Bukti: Misal
warna dan
( )=(
adalah pewarnaan lokasi dari
adalah pewarnaan lokasi dari , + −1 + − 1) , ≥ 0, maka −1
,
+
menggunakan
suatu titik tetap , misal ( ) warna dari titik tengah = 1,2,3, … ,
warna yang digunakan oleh
■
. maka banyak kombinasi
−1
adalah
Karena satu warna digunakan untuk titik pusat amalgamasi (
+
− 1)
untuk
,
untuk
diperoleh nilai maksimum dari maka
≤
( ).
setiap
adalah
= 1,2,3, … , .
( )=(
+
warna, Untuk
− 1)
+
−1 . −1
, maka terdapat
Dari +
Lemma −1 , −1
3.2, ≥ 0, ■
27
Teorema 3.6 (Asmiati dkk, 2011) Jika ≥ 0,
≥ 2, dan
,
≥ 3, maka =
+
+
− 1)
Bukti: Pertama-tama akan dicari batas bawah dan batas atas dari 2≤
(0) =
≤
(1) Batas bawah dari
− 1.
,
titik = 1,2,3, … , . Dengan demikian Misalkan
untuk
,
untuk
.
Berdasarkan Akibat 3.1, setiap titik
(2) Batas atas dari
−1 −1
2 ≤ ≤ (0), ≥ 3 ( − 1) < < ( ), ≥ 1
; ;
+
( )=(
bertetangga dengan (
− 1)daun, untuk
menggunakan
warna. Tanpa
,
,
adalah pewarnaan dari
,
≥
.
mengurangi keumuman , misal ( ) = 1 dan ( ) = + 1 untuk
= 1,2,3, … , .
Karena daun-daun harus mempunyai kode warna yang berbeda, maka daun-daun = 1,2, … ,
− 1 diberi warna oleh {1,2, … ,
Maka, berdasarkan Lemma 3.1, ,
≤
Selanjutnya, ( − 1) <
adalah pewarnaan lokasi. Dengan demikian
. akan
<
}\{ + 1} untuk sebarang .
( ),
dicari
batas
bawah
≥ 1 , yaitu sebagai berikut.
dan
batas
atas
untuk
28
(1) Batas bawah dari Karena
>
sisi lain, jika
,
( − 1), maka berdasarkan Lemma 2.3, >
( ) maka berdasarkan Lemma 3.3,
Dengan demikian, (2) Batas atas dari
≥
,
,
+
( − 1) <
jika
Karena ( ) = 1 dan warna dari titik tengah ( − 1) <
<
( ),
( ) = 1,2,3, … ,
Lemma 3.3, ( − 1) <
<
)≥
,
+
−1
≠
+1 , untuk sebarang −1
(
) = 1,2,3, … ,
( ).
+
+ 1.
. Karena
,
≤
5
1
6
6
4 3
1
2
1
5
4 6
4
1
2
3
5
1
6
2
5 3
Gambar 20. Pewarnaan lokasi minimum pada graf
. Akibatnya
− 1 . Berdasarkan
4 3
2
+
( ).
adalah 2,3, … ,
adalah pewarnaan lokasi. Jadi,
<
+ . Pada
≥ 1 maka banyak titik tengah yang mempunyai warna
yang sama tidak lebih dari
jika
(
≥
,
,
+
untuk ■
29
1
3
3
1 2
2
4
2
4
3
3
4
2
1
1 4
2
1 3
3
1 4
3
2 1
2
4
Gambar 21. Pewarnaan lokasi minimum pada graf
,
