6
II.
LANDASAN TEORI
Pada bab ini akan diberikan beberapa konsep dasar teori graf dan bilangan kromatik lokasi sebagai landasan teori pada penelitian ini. 2.1 Konsep Dasar Graf Pada sub bab ini akan diberikan beberapa definisi dan teorema tentang graf yang diambil dari Deo (1989). Suatu graf G adalah pasangan himpunan terurut ( ( ), ( ) ) dengan menyatakan himpunan titik (vertex) tak kosong dan
( )
( ) menyatakan himpunan
sisi (edge) yakni pasangan tak terurut dari ( ). Pada Gambar 3, terlihat ( ) = { , , , , } dan ( ) = {
,
,
,
,
}.
Gambar 3. Contoh Graf dengan 5 titik dan 5 sisi
7
Graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek-objek sebagai bulatan atau titik, sedangkan hubungan antara objek dinyatakan dengan sisi. Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Sebagai contoh representasi dari graf adalah perjalanan bus untuk menemukan rute paling ekonomis dari sebuah terminal ke halte-halte yang harus dilewati tepat satu kali tanpa ada yang terlewati dua kali dan harus kembali ke terminal asal, merupakan upaya untuk mengefisienkan biaya dan waktu pada sistem transportasi. Sistem transportasi perjalanan bus dapat dimodelkan dalam graf dengan halte sebagai titik dan jalur yang menghubungkan halte-halte tersebut sebagai sisi.
Gambar 4. Contoh graf dengan 5 titik dan 8 sisi Loop adalah sisi yang memiliki titik awal dan titik akhir yang sama. Sisi paralel adalah sisi yang memiliki dua titik ujung yang sama. Pada Gambar 4, terdapat loop pada titik v2 yaitu e8, sedangkan e3, e6, e5 dan e7 disebut sisi paralel. Graf yang tidak mempunyai sisi ganda dan/atau loop disebut graf sederhana
8
(simple graph). Graf pada Gambar 4. bukan graf sederhana (simple graf) karena terdapat loop (e9) dan sisi ganda (e5 dan e7). Suatu graf G dikatakan graf lengkap jika untuk setiap pasangan titik terdapat sisi yang menghubungkannya.
Gambar 5. Contoh Graf Lengkap K4 Misalkan
adalah graf dengan himpunan titik ( ) dan sisi ( ), maka graf
dikatakan subgraf
dinotasikan dengan TG jika dan hanya jika ( ) himpunan
bagian dari ( ) dan ( ) himpunan bagian dari ( ). Graf sejati
jika dan hanya jika
subgraf dari
dan
dilihat pada gambar berikut :
≠
dikatakan subgraf
. Contoh subgraf dapat
A
e2
c e4
e1 B
e3
Graf T
Graf G
D
Gambar 6. T G Dua titik pada graf
dikatakan bertetangga (adjacent) bila keduanya terhubung
oleh suatu sisi. Suatu sisi dikatakan menempel (incident) dengan suatu titik u, jika titik u merupakan salah satu titik ujung dari sisi tersebut. Pada Gambar 4. dapat
9
dilihat bahwa sisi menempel pada sisi
menempel (incident) dengan titik dan
. Titik
bertetangga dengan titik
dan titik
bertetangga (adjacent) dengan titik
karena terdapat sisi-sisi yang menghubungkan titik
dan
, dan titik
dan
. Demikian pula dengan
bertetangga dengan titik
.
Derajat (degree) dari suatu titik v ∈ ( ), dinotasikan dengan ( ) dari graf
adalah banyaknya sisi yang menempel pada titik . Jika setiap titik pada graf mempunyai derajat yang sama, maka
disebut graf reguler. Daun (pendant
vertex) adalah titik yang berderajat satu. Pada Gambar 4. d ( ) = 2, ( ) = 3,
( ) = 5 dan
( ) = 5,
( ) = 3. Graf tersebut tidak memiliki daun
karena setiap titiknya memiliki derajat lebih dari satu.
Jalan (walk) adalah barisan berhingga dari titik dan sisi dimulai dan diakhiri dengan titik sedemikian sehingga setiap sisi menempel dengan titik sebelum dan sesudahnya. Contoh walk dari graf
pada gambar 7 adalah v1 e1 v2 e2 v3 e4 v4 e6 v5
e7 v6 e3.
Gambar 7. Contoh Graf dengan 6 titik dan 7 sisi Lintasan (path) adalah jalan yang memiliki atau melewati titik yang berbeda-beda. Lintasan yang memiliki titik awal dan akhir yang sama disebut lintasan tertutup
10
atau siklus. Graf G pada Gambar 7. v1v2v3v4v5v6
adalah salah satu lintasan
tertutup. Siklus yang banyak titiknya genap disebut sirkuit genap, sedangkan jika banyak titiknya ganjil, maka disebut siklus ganjil. Graf G dikatakan terhubung jika terdapat lintasan yang menghubungkan setiap dua titik yang berbeda
2.2. Kelas Graf Pohon Pohon (tree) adalah graf terhubung yang tidak memuat siklus. Suatu Graf adalah pohon jika dan hanya jika terdapat tepat satu lintasan untuk setiap pasangan titik di Graf
(Deo,1989).
Berikut ini akan diberikan beberapa kelas graf pohon yang berkaitan dengan penelitian ini. Misalkan
adalah graf terhubung,
disebut pohon jika dan hanya jika
tidak
memuat sirkuit. Gabungan dari pohon disebut hutan (forest) (Deo, 1989).
Gambar 8. T adalah contoh pohon dan H adalah contoh hutan Graf
,
adalah graf yang diperoleh dari
dihubungkan oleh suatu lintasan.
graf
,
dan setiap titik
nya
11
Gambar 9. Graf S4,k
Gambar 10. Graf 3S4,5
Graf bintang K1,n (star) adalah suatu graf terhubung yang mempunyai satu titik berderajat n yang disebut pusat dan titik lainya berderajat satu (Chartrand dkk., 1998). Graf bintang dengan k titik juga dapat dinotasikan dengan
.
12
Gambar 11. Graf bintang K1,6 Suatu graf pohon disebut graf bintang ganda (double star) jika graf pohon tersebut mempunyai tepat dua titik x dan y berderajat lebih dari satu. Jika x dan y berturut-turut berderajat a + 1 dan b + 1, dinotasikan dengan Sa,b (Chartrand dkk., 1998).
Gambar 12. Graf bintang ganda S3,2 Graf ulat (caterpillar graf) adalah graf pohon yang memiliki sifat apabila dihapus semua daunnya akan menghasilkan lintasan (Chartrand dkk., 1998).
Gambar 13. Contoh graf ulat Graf pohon pisang
,
adalah graf yang diperoleh dari n buah kegraf bintang
dengan cara menghubungkan sebuah daun dari setiap graf bintang
,
suatu titik
baru. Titik baru itu disebut titik root, dinotasikan dengan x (Asmiati dkk., 2011).
13
Gambar 14. Contoh Graf Pohon Pisang
2.3 Bilangan Kromatik Lokasi Bilangan kromatik lokasi diperkenalkan oleh Chartrand dkk. (2002). Bilangan kromatik lokasi didefinisikan sebagai berikut. Misalkan c suatu pewarnaan sejati di
dengan ( ) ≠ ( ) untuk
dan
yang bertetangga di
. Misalkan
adalah himpunan titik-titik yang diberi warna , yang selanjutnya disebut kelas warna, maka П = { , warna dari ( ( ,
), ( ,
} adalah himpunan yang terdiri dari kelas-kelas
,…..
( ). Kode warna, ), … . , ( ,
))
untuk 1≤ ≤ . Jika setiap titik di c disebut pewarnaan lokasi dari
П(
) dari
dengan
( ,
adalah k-pasang terurut
) = min
∈
mempunyai kode warna yang berbeda, maka . Banyaknya warna minimum yang digunakan
pada pewarnaan lokasi disebut bilangan kromatik lokasi dari dengan χ ( ).
( , )⃒
, dan dinotasikan
14
Berikut ini diberikan teorema dasar tentang bilangan kromatik lokasi yang telah dibuktikan oleh Chartrand dkk. (2002). Lingkungan dari
, dinotasikan dengan
N(u) adalah himpunan titik-titik yang bertetangga dengan .
Teorema 2.1. Misalkan c adalah pewarnaan lokasi pada graf adalah dua titik yang berbeda di
. Jika u dan v
sedemikian sehingga d(u,w) = d (v,w) untuk
semua w ϵ V(G) – {u,v}, maka c(u) ≠ c(v). Secara khusus, jika u dan v titik-titik yang tidak bertetangga di
sedemikian sehingga N(u) = N(v), maka c(u) ≠ c(v).
Bukti: Misalkan c adalah suatu pewarnaan lokasi pada graf terhubung misalkan П = { C1 , C2 , .... , Ck} adalah partisi dari titik-titik warna Ci. Untuk suatu titik u,v∊ V(G), andaikan
dan
kedalam kelas
( ) = ( ) sedemikian
sehingga titik u dan v berada dalam kelas warna yang sama, misal Ci dari П. Akibatnya, setiap
( ,
) =
( ,
) = 0.
Karena
( , ) =
∊ ( ) – { , } maka d(u,Cj) = d(v, ) untuk setiap j ≠ i,
( , )
untuk
1 ≤ j ≤ k . Akibatnya, cП (u) = cП (v) sehingga c bukan pewarnaan lokasi. Jadi, ( ) ≠ ( ).
■
Akibat 2.1. Jika
adalah graf terhubung dengan suatu titik yang bertetangga
dengan k daun, maka χ ( ) ≥ k+1. Bukti: Misalkan v adalah suatu titik yang bertetangga dengan k daun, yaitu x1, x2, .... ,xk di
. Berdasarkan Teorema 2.1, setiap pewarnaan lokasi dari
mempunyai warna yang berbeda untuk setiap xi, i = 1,2,..., k. Karena v bertetangga
15
dengan semua xi, maka v harus mempunyai warna yang berbeda dengan semua daun xi. Akibatnya, χL(G) ≥ k+1. Berikut ini diberikan graf graf
■
dan akan ditentukan bilangan kromatik lokasi dari
tersebut.
G Gambar 15. Pewarnaan lokasi minimum dari graf
Diberikan graf
seperti yang terlihat pada Gambar 15. Akan ditentukan terlebih
dahulu batas bawah bilangan kromatik lokasi dari graf
. Karena terdapat titik v3
yang mempunyai 3 daun, maka berdasarkan Akibat 2.1, χL( ) ≥ 4.
(2.1)
Misalkan c adalah pewarnaan titik menggunakan empat warna. Pada graf diberikan kelas warna sedemikian sehingga diperoleh П = { , = { ,
},
={ ,
,
},
={ ,
itu, didapatkan kode warna sebagai berikut : П(
) = (0,1,2,3) ;
(1,0,2,2);
(2,1,0,1);
П( П(
П(
) = (1,0,1,2);
) = (1,2,0,2); ) =(3,0,1,1);
П(
П(
П(
} dan
= { ,
) = (0,1,1,1);
) = (1,2,2,0);
) = (4,1,2,0);
П(
П(
)=
П(
,
,
} dengan
}. Oleh karena )=
) = (3,2,1,0)
16
Karena kode warna dari semua titik di
berbeda, maka c adalah pewarnaan
lokasi. Jadi, χL( ) ≤ 4
(2.2)
Berdasarkan (2.1) dan (2.2), maka П adalah pewarnaan lokasi dari
dan
χL( ) = 4.
Selanjutnya akan didiskusikan bilangan kromatik lokasi dari beberapa kelas graf pohon. Teorema 2.2. Bilangan kromatik lokasi graf lintasan Pn (n ≥ 3) adalah 3.
Bukti: Perhatikan bahwa χL (P1) = 1 dan χL (P2) = 2. Berdasarkan Akibat 2.1, diperoleh χL (Pn) ≥ 2. Misalkan c adalah 2-pewarnaan lokasi pada Pn, n≥ 3 akibatnya akan terdapat dua titik yang memiliki kode warna yang sama, kontradiksi. Maka χL (Pn) ≥ 3; n≥ 3.
Selanjutnya konstruksi batas atas pada Pn; n≥ 3 sebagai berikut. Misalkan c adalah 3-pewarnaan titik, c(v1)= 1; c(vi)= 2 untuk i genap; dan c(vi)= 3 untuk i ≥ 3 ganjil. Diperoleh kode warna genap;
П(
П(
) = (0,1,2) ;
П(
) = ( − 1,0,1) untuk i
) = ( − 1,1,0) untuk i ≥ 3 ganjil. Karena semua titik mempunyai
kode warna berbeda, maka c adalah pewarnaan lokasi. Akibatnya, χL (Pn) ≤ 3; n≥ 3. Jadi, χL (Pn) = 3; n≥ 3
■
17
1
2
3
1
2
1
v1
v2
v3
v4
v5
v6
un-1 un
Gambar 16. Pewarnaan lokasi minimum pada graf lintasan Pn
Teorema 2.3. Untuk bilangan bulat a dan b dengan 1≤ a ≤ b dan b ≥ 2 χL (Sa,b) = b+1 Bukti : Berdasarkan Akibat 2.1, diperoleh batas bawah yaitu χL (Sa,b) ≥ b+1. Selanjutnya, akan ditentukan batas atasnya, yaitu χL (Sa,b) ≤ b+1. Misalkan c adalah pewarnaan titik menggunakan (b+1) warna sebagaimana terlihat pada Gambar 17. Perhatikan bahwa kode warna dari setiap titik Sa,b berbeda, akibatnya c adalah pewarnaan lokasi. Jadi χL (Sa,b) ≤ b+1.
■
Gambar 17. Pewarnaan lokasi minimum pada Sa,b.
Chartrand dkk. (2003) telah mendapatkan bentuk graf pohon berorde n ≥ 5 yang memiliki bilangan kromatik lokasi dari 3 sampai n, kecuali n-1, sebagaimana teorema berikut ini.
18
Teorema 2.4. Terdapat pohon dengan berorde n ≥ 5 yang mempunyai bilangan kromatik k jika dan hanya jika k ∊ (3,4,..,n-2,n). Pewarnaan pada Teorema 2.4 dapat diberikan sebagai berikut:
1 u1 2 u2 k- 1 uk-1
k
1
2
1
2
v1
v2
v3
v4
v5
vn-k+1
Gambar 18. Pohon T berorde n dengan χL(T)= k
Teorema 2.5. Misalkan K1,n graf bintang berode n ≥ 1, maka χL (K1,n) = n+1. Bukti :
Gambar 19. Pewarnaan lokasi minimum graf bintang K1,n Karena terdapat daun sebanyak n,maka berdasarkan Akibat 2.1, χL( ) ≥ n+1. Misalkan c adalah pewarnaan pada graf K1,n, dengan c(v1)= 1; c(vi)= i; i ≥2. Kode warna titik
bernilai 0 untuk komponen warna ke-1 dan bernilai 1 untuk
19
komponen warna lainnya. Sedangkan kode warna titik
; ≥ 2, akan bernilai 1
untuk komponen warna ke-1, 0 untuk warna ke-i, dan 2 untuk lainnya. Karena kode warna dari semua titik adalah berbeda, maka c merupakan pewarnaan lokasi. Jadi χL( ) ≤ n+1.
■
