II.
TINJAUAN PUSTAKA
Pada bagian ini akan diberikan konsep dasar graf dan bilangan kromatik lokasi pada suatu graf sebagai landasan teori 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
,
himpunan titik
menyatakan himpunan sisi
tak kosong dan
yakni pasangan tak terurut dari dari graf . Misalkan dan sisi
, maka v dan w dikatakan bertetangga
menempel dengan titik , dinotasikan dengan
menyatakan
. Banyaknya himpunan titik
adalah titik pada graf , jika
dikatakan menempel
dengan
dan
disebut orde dihubungkan oleh
, sedangkan titik
dangan sisi , demikian juga sisi dan
. Himpunan tetangga
dan
dikatakan
dari suatu titik
adalah himpunan titik-titik yang bertetangga dengan .
6
Gambar 2.1. Contoh graf dengan 6 titik dan 6 sisi Pada Gambar 2.1, Graf , ,
,
,
,
,
. Titik
, ,
,
,
bertetangga dengan titik
menempel dengan . Sebaliknya adalah 2, derajat
=
dengan
menempel dengan
adalah 3, derajat
dan
adalah 1 dan derajat
,
, dan
=
, sedangkan
dan
. Derajat ,
,
adalah 4.
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 paralel atau loop disebut graf sederhana. Graf pada Gambar 2.1 bukan merupakan graf sederhana karena pada graf tersebut terdapat loop, yaitu pada titik
. Pada graf
terhubung , jarak diantara dua titik dan adalah panjang lintasan terpendek diantara kedua titik tersebut, dinotasikan dengan pembahasan graf adalah jalan
,
. Istilah lain yang sering muncul pada
, lintasan
dan sirkuit
. Jalan
adalah barisan berhingga dari titik dan sisi dimulai dan diakhiri sedemikian sehingga setiap sisi menempel dengan titik sebelum dan sesudahnya. Contoh jalan
7
berdasarkan Gambar 2.1 adalah
.
Lintasan adalah jalan yang melewati titik yang berbeda-beda. Graf G dikaitkan graf terhubung jika terdapat lintasan yang menghubungkan setiap dua titik yang berbeda. Pada Gambar 2.1 Contoh lintasan adalah .
Graf lingkaran adalah graf sederhana yang setiap titik berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan
. Contoh graf lingkaran adalah
.
Sirkuit adalah lintasan tertutup , 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 ganil. Contoh sirkuit berdasarkan pada Gambar 2.1 adalah
.
Lemma 2.1 Deo 1989 Misalkan G V, E adalah graf terhubung dengan |E| = e, maka : 2
8
Sebagai contoh pada graf Gambar 2.1 adalah
2 + 2 + 3 + 1 + 4 + 2 = 14 = dua kali jumlah sisi.
Teorema 2.2 Deo 1989 Untuk sembarang graf G, banyaknya titik yang berderajat ganjil, selalu genap. Bukti : Misalkan V
dan V
masing-masing adalah himpunan-himpunan titik ,
yang berderajat genap dan berderajat ganjil pada
. Maka persamaan dapat
ditulis sebagai berikut :
Karena
untuk setiap
∈
, maka suku pertama dari ruas kanan persamaan
harus bernilai genap. Ruas kiri persamaan juga harus bernilai genap. Nilai genap pada ruas kiri hanya benar bila suku kedua dari ruas kanan juga harus genap. Karena
untuk setiap
∈V
, maka banyaknya titik
di dalam v
harus genap
agar jumlah seluruh derajatnya bernilai genap. Jadi banyaknya titik yang berderajat ganjil selalu genap.
▄
9
2.2
Graf Petersen
Graf Petersen
,
→
,
adalah graf dengan 2 titik {
,…,
∪{ ,…,
→ .
dan
Berikut ini diberikan beberapa contoh graf Petersen
Gambar 2.2 Graf Petersen
,
Gambar 2.3 Graf Petersen
,
dan sisi
→
10
2.3
Bilangan Kromatik Lokasi
Bilangan kromatik lokasi graf pertama kali dikaji oleh Chartrand dkk. pada tahun 2002, dengan mengembangkan dua konsep dalam graf yaitu pewarnaan titik pada graf dan
dimensi partisi graf. Misalkan c suatu pewarnaan sejati di G dengan
adalah himpunan titik-titik yang
untuk u dan v yang bertetangga di G. Misalkan diberi warna
,
,…,
,
=
, yang selanjutnya disebut dengan kelas warna, maka
. Kode
adalah himpunan yang terdiri dari kelas-kelas warna dari dari v adalah k-pasang terurut
warna ,
,
| ∈
untuk 1
,
,
,
,
,
,….,
,
dengan
. Jika setiap titik di G
mempunyai kode warna yang berbeda, maka c disebut pewarnaan lokasi dari G. Banyaknya warna minimum yang digunakan pada pewarnaan bilangan kromatik lokasi dari G, dan dinotasikan dengan
1
.
1
2
2
2
1
1
2 Gambar 2.4. Contoh Bilangan Kromatik dengan
2
Teorema 2.3 (Chartrand dkk. 2002) Misalkan c adalah pewarnaan lokasi pada graf G. Jika
dan
adalah dua titik yang berbeda di G sedemikian sehingga
,
11
,
untuk semua ∈
dan
,
, maka
. Secara khusus, jika
titik-titik yang tidak bertetangga di G sedemikian sehingga
maka
,
.
Bukti : Misalkan adalah suatu pewarnaan lokasi pada graf terhubung G dan misalkan ,
,…,
adalah partisi dari titik-titik G kedalam kelas warna
suatu titik , ∈
, andaikan
sedemikian sehingga titik u dan v dari
berada dalam kelas warna yang sama, missal , ,
0. Karena
,
,
untuk setiap
,
. Untuk
∈
untuk setiap
1, 1
sehingga c bukan pewarnaan lokasi. Jadi,
. Akibatnya,
,
. Akibatnya,
,
maka
. ▄
Akibat 2.4 (Chartrand dkk. 2002) Jika G adalah graf terhubung dengan suatu titik yang bertetangga mempunyai k daun, maka
1.
Bukti : Misalkan v adalah suatu titik yang bertetangga dengan k daun
,
,….,
di G. Berdasarkan Teorema 2.1 setiap pewarnaan lokasi dari G mempunyai warna yang berbeda untuk setiap pewarnaan lokasi dari G mempunyai warna yang berbeda untuk setiap
,
1,2, … , . Karena v bertetangga semua
mempunyai warna yang berbeda dengan daun
. Akibatnya
, maka harus
1. ▄
12
1
3
2
8 2
1 2
1
3
3
Gambar 2.5. Pewarnaan lokasi minimum pada graf G
Diberikan graf G seperti yang terlihat pada Gambar 2.4. Akan ditentukan terlebih yang
dahulu batas bawah bilangan kromatik lokasi pada graf G. Karena terdapat titik mempunyai 2 daun, maka berdasarkan Akibat 2.1,
3.
Selanjutnya, akan ditentukan batas atas bilangan kromatik lokasi dari graf G. Titik-titik pada {
,
dipartisi sebagai berikut : ,
={
}. Kode warnanya ialah = { 0,1,1 };
2,1,0 };
= { 2,0,1 } ;
};
berbeda, maka
pewarnaan
,
,
};
= { 0,1,2 };
={
, ,
};
= { 1,0,1 };
={
= {1,2,0 } ;
= { 1,0,2 };
=
= { 1,1,0
= { 0,2,1 }. Karena kode warna semua titik di tersebut
Berdasarkan persamaan dan diperoleh
merupakan
lokasi dengan
3..
3..
Teorema 2.5 (Chartrand dkk. 2002) Jika k adalah derajat maksimum di graf G maka
1.
13
Teorema 2.6 (Chartrand dkk. 2002) Bilangan kromatik lokasi graf lintasan
≥ 3)
adalah 3.
Bukti : Perhatikan bahwa
untuk
= 2 maka
,
2. Jelaskan bahwa
3. Berdasarkan teorema
maksimum. Karena pada terbukti
1 dan
3
1, dengan k derajat titik
1 + 2. Akibatnya
3. Jadi
3. ▄
1
2
3
1
2
1
2
1
V1
V2
V3
V4
V5
V6
V7
V8
Gambar 2.6. Pewarnaan lokasi minimum pada graf lintasan
,
3.
Teorema 2.7 (Chartrand dkk. 2002) Jika a dan b bilangan bulat dengan 1 b ≥ 2, maka
,
dan
= b + 1.
Bukti : Berdasarkan Akibat 2.4 , diperoleh batas bawah yaitu Selanjutnya, akan ditentukan batas atasnya, yaitu pewarnaan titik menggunakan
,
= b + 1.
) = b + 1. Misalkan c adalah
1 warna sebagaimana terlihat pada Gambar 2.5.
Perhatikan bahwa kode warna dari setiap titik pewarnaan lokasi. Jadi
,
,
b + 1. ▄
,
berbeda, Akibatnya c adalah
14
1 2
2 b + 1
a
3
1
u
V a + 1
b
Gambar 2.7. Pewarnaan lokasi minimum pada
, .
Chartrand dkk.(2003) telah mendapatkan bentuk graf pohon berorde memiliki bilangan kromatik lokasi dari 3 sampai n, kecuali
Teorema 2.8 (Chartrand dkk. 1998) Pada graf lingkaran jika n adalah bilangan ganjil dan
(
5 yang
1.
untuk n titik,
) = 4 maka n adalah bilangan genap.
(
)=3
