Page 109 - Trends in Science and Technology fo Sustainable Living
P. 109
70 Fakultas Sains dan Teknologi
Universitas Terbuka (2023)
tak langsung bahwa tidak ada dua sisi bertetangga yang dapat
diwarnai sama, sehingga dapat diasumsikan, tanpa mengurangi
perumuman, c′ (uu ) = 2 dan c′ (uu 3 ) = 3 (lihat Gambar 20(b)).
′
} { } . Jika c′
′
Jadi, { (c vv 2 ), (c vv 3 ) = 1,2 (vv 2 )1= dan c′ (vv 3 ) = 2,
maka c′ (uv ) = 3 dan c′ (uv )1= . Pada kasus ini, tidak
22
33
terdapat lintasan pelangi u - v di G. Di lain pihak, jika c′ (vv ) = 2
1 3 2
dan c′ (vv 3 )1= , maka c′ (uv ) {1,3}∈ dan c′ (uv ) = 2 . Jika
33
22
c′ (uv )1= , maka tidak terdapat lintasan pelangi u - v di G;
22 2 3
sementara jika c′ (uv ) = 3 , maka tidak terdapat lintasan pelangi
22
u - v di G. Hal ini kontradiksi dengan definisi terhubung pelangi.
2 1
Oleh karena itu, rc(G) = 4. Karena 4 = rc ()G ≤ src ()G dan graf G
pada Gambar 20(a) adalah pewarnaan-4 pelangi kuat juga, maka
src(G) = 4.
Dari pemaparan di atas, telah dibahas tentang bagaimana
menentukan rc(G) dan src(G). Oleh karena graf merupakan
representasi dari suatu jaringan komunikasi, jika jaringan komunikasi
yang diberikan berupa graf pada Gambar 20(a) maka berikut ini
representasi dari pewarnaan pelangi yang diperoleh. Diketahui
bahwa graf G pada Gambar 20(a) mempunyai bilangan terhubung
pelangi rc(G) = src(G) = 4. Hal ini berarti minimal banyaknya sandi
yang digunakan pada sistem jaringan komunikasi tersebut adalah
4. Oleh karena itu jika pengirim di u akan mengirimkan data ke
1
penerima di v maka pengirim harus memasang sandi pada data
3
sebanyak 4 layer. Selanjutnya, pengirim dapat mengirimkan data
melalui lintasan pelangi u - v yang aman. Salah satu pilihan
1 3
lintasan pelangi u - v yang aman adalah u − v − v − v . Meskipun
1 3 1 1 3
panjang lintasan tersebut adalah 3, namun karena sandi yang
dipasang sebanyak 4, maka data yang dikirim masih terjaga
keamanannya.
Selanjutnya, akan dijabarkan hasil-hasil penelitian tentang
bilangan terhubung pelangi dari beberapa kelas graf (umum) dan
hasil operasi graf umum sebagai berikut.