## BILANGAN TERHUBUNG PELANGI PADA AMALGAMASI GRAF BERLIAN
Cindy Aisa Putri Noor 1 *, Karina Ansyelia Mamonto 2 , Widya Eka Pranata 3
1,2,3 Jurusan Matematika, Universitas Negeri Gorontalo, Bone Bolango 96119, Indonesia
*Penulis Korespondensi. Email: cindy.aisa2010@gmail.com

## Abstrak
Misalkan 𝐺 = (𝑉, 𝐸) adalah graf terhubung tak trivial. Graf 𝐺 dikatakan terhubung pelangi jika untuk setiap dua  titik 𝑥 dan 𝑦 terdapat  lintasan  pelagi  dari 𝑥 dan 𝑦 .  Bilangan  terhubung  pelangi  didefinisikan  sebagai minimum 𝑘 dari  pewarnaan −𝑘 pelangi  sehingga  menghasilkan  sebuah  lintasan  pelangi  dengan  dua  sisi bertetangga  memiliki  warna  yang  berbeda  dan  dinotasikan  sebagai 𝑟𝑐(𝐺) .  Misalkan  t  adalah  bilangan  asli dengan 𝑡 ≥ 2 dan misalkan {𝐺 𝑖 |𝑖 ∈ [1, 𝑡]} adalah graf terhubung tak trivial  dengan setiap 𝐺 𝑖 mempunyai titik tetap 𝑣 0𝑖 , maka amalgamasi untuk graf 𝐺 dinotasikan dengan 𝐴𝑚𝑎𝑙(𝐺 𝑖 , 𝑣 0𝑖 , 𝑡) . Amalgamasi merupakan salah satu  operasi  matematika  yang  terbentuk  dengan  merekatkan  semua  graf 𝐺 𝑖 pada  titik 𝑣 0𝑖 dengan  titik 𝑣 0𝑖 merupakan titik terminal. Dalam penelitian ini operan yang digunakan pada operasi amalgamasi adalah graf berlian dengan notasi 𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡) dengan 𝑡 ≥ 2 .
Kata Kunci: Bilangan Terhubung; Pelangi; Amalgamasi; Graf Berlian

## 1. Pendahuluan
Teori  graf  merupakan  cabang  ilmu  matematika  yang  mempelajari  tentang  sifat-sifat  graf.  Graf merupakan himpunan tak trivial dari pasangan himpunan (V,E) , dengan V merupakan himpunan tidak kosong dari  titik  ( vertex )  dan E merupakan  himpunan  sisi  ( edge )  yang  menghubungkan  sepasang  titik  dimana E mungkin saja kosong. Pasangan himpunan tersebut dinotasikan dengan G = (V,E) [1].
Seiring berjalannya waktu, teori graf mengalami perkembangan pesat dengan lahirnya cabang-cabang ilmu baru seperti pelabelan graf, penjodohan, bilangan terhubung pelangi, hingga amalgamasi. Amalgamasi merupakan  sebuah  operasi  graf  dengan  pasangan  titik  graf (G,u) dan (H,v) yang  diperoleh  dengan menggabungkan titik u dan v menjadi satu titik [2].
Salah  satu  cabang  ilmu  baru  dari  teori  graf  adalah  bilangan  terhubung  pelangi  yang  pertama  kali diperkenalkan  oleh  Chatrand  [3].  Bilangan  terhubung  pelangi  merupakan  minimum 𝑘 dari  pewarnaan −𝑘 pelangi  sehingga  menghasilkan  sebuah  lintasan  pelangi  dengan  dua  sisi  bertetangga  memiliki  warna  yang berbeda. Jika graf 𝐺 memiliki diameter yang berupa jarak terdekat antara 𝑣 1 dan 𝑣 2 yang dinotasikan dengan 𝑑𝑖𝑎𝑚(𝐺) dan juga memiliki sisi sebanyak 𝑚 , maka :
𝑑𝑖𝑎𝑚(𝐺) ≤ 𝑟𝑐(𝐺)   ≤ 𝑠𝑟𝑐(𝐺) ≤ 𝑚 (1)
Dari penjelasan diatas maka muncullah gagasan untuk melakukan penelitian bilangan terhubung pelangi dengan  menggunakan  operasi  amalgamasi.  Adapun  operan  yang  digunakan  dalam  operasi  amalgamasi  ini adalah graf berlian dengan titik yang diambil adalah titik v pada graf berlian. Graf berlian merupakan graf dengan 2𝑛 titik yang diperoleh dari graf tangga segitiga dengan 2𝑛 − 1 titik dan ditambahkan satu titik dan beberapa sisi tertentu dengan notasi 𝐵𝑟 𝑛 [4].

## 2. Metode Penelitian
Penelitian  ini  menggunakan  metode  penelitian  studi  literatur  (library  research).  Pada  penelitian  ini dilakukan  kajian  terhadap buku,  textbook,  jurnal,  dan  artikel-artikel  ilmiah  mengenai  amalgamasi  dan  graf berlian. Adapun langkah-langkah yang dilakukan adalah
1. Mempelajari literatur,
2. Menggambar bentuk amalgamasi graf berlian,
3. Menentukan pola pewarnaan amalgamasi graf berlian, dan
4. Membuktikan teorema.

## 3. Pembahasan
Graf berlian dinotasikan dengan 𝐵𝑟 𝑛 dengan definisi sisi dan titik sebagai berikut :
𝑉(𝐵𝑟 𝑛 ) = {𝑣} ∪ {𝑣 𝑖 |𝑖 ∈ {1,2, … , 𝑛}} ∪ {𝑢 𝑖 |𝑖 ∈ {1,2, … 𝑛 − 1}}
𝐸(𝐵𝑟 𝑛 ) = {𝑣𝑣 𝑖 |𝑖 ∈ {1,2, … , 𝑛}} ∪ {𝑣 𝑖 𝑣 𝑖+1 |𝑖 ∈ {1,2, … , 𝑛 − 1}} ∪ {𝑢 𝑖 𝑢 𝑖+1 |𝑖 ∈ {1,2, … , 𝑛 − 2}} ∪ {𝑢 𝑖 𝑣 𝑖 |𝑖 ∈ {1,2, … , 𝑛 − 1}} ∪ {𝑢 𝑖 𝑣 𝑖−1 |𝑖 ∈ {1,2, … , 𝑛 − 1}}
Gambar graf berlian 𝐵𝑟 4 dapat dilihat pada Gambar 1.
Gambar 1. Graf Berlian 𝐵𝑟 4
Amalgamasi graf berlian (𝐵𝑟 𝑛 ) sebanyak 𝑡 dengan 𝑣 adalah titik terminal dinotasikan dengan 𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡) dengan 4 ≤ 𝑛 ≤ 6 . 𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡) memiliki diameter 4 dan didefinisikan sebagai berikut :
𝑉(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) = { 𝑢 𝑖,𝑗 , 𝑖 ∈ [1, 𝑡] 𝑗 ∈ [1, 𝑛 − 1]
𝑣 𝑖,𝑗 , 𝑖 ∈ {1, 𝑡] 𝑗 ∈ [1, 𝑛]
𝑣
𝐸(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) =
{ 𝑢 𝑖,𝑗 𝑢 𝑖,𝑗+1 ; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 2] 𝑣 𝑖,𝑗 𝑣 𝑖,𝑗+1 ; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 1] 𝑢 𝑖,𝑗 𝑣 𝑖,𝑗 ; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 1]
𝑢 𝑖,𝑗 𝑣 𝑖,𝑗+1 ; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 1]
𝑣 𝑖,𝑗 𝑣; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛]
Teorema 1
Misalkan 𝐺 ≅ 𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡) dengan bilangan bulat 4 ≤ 𝑛 ≤ 6 dan 𝑡 ≥ 2 , maka bilangan terhubung pelangi pada 𝐺 adalah :
𝑟𝑐 (𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) = 2𝑡 .
Bukti
Untuk 𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡) dengan  bilangan  bulat 4 ≤ 𝑛 ≤ 6 dan 𝑡 ≥ 2 memiliki  diameter  4  dan  bilangan terhubung pelangi 2t. Karena 𝑟𝑐(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) = 2 dan 𝑡 ≥ 2 maka 𝑟𝑐(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) ≥ 4 , sehingga
𝑑𝑖𝑎𝑚(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) ≤ 𝑟𝑐(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) .  Definisikan  pewarnaan 𝑐: 𝐸(𝐺) → {1,2,3, . . } sebagai berikut:
𝑐(𝑢 𝑖,𝑗 𝑢 𝑖,𝑗+1 ) = 𝑗, untuk 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 2]
𝑐(𝑣 𝑖,𝑗 𝑣 𝑖,𝑗+1 ) = (𝑗 + 1)𝑚𝑜𝑑 2 + 2𝑖 − 3, untuk 𝑖 ∈ [2, 𝑡], 𝑗 ∈ [1, 𝑛 − 1]
𝑐(𝑣 1,𝑗 𝑣 1,𝑗+1 ) = 2𝑡 − (𝑗 𝑚𝑜𝑑 2), untuk 𝑗 ∈ [1, 𝑛 − 1]
𝑐(𝑣𝑣 𝑖,𝑗 ) = 2𝑖 − 1 + ⌊ 𝑗 4 ⌋, untuk 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛]
𝑐(𝑢 𝑖,𝑗 𝑣 𝑖,𝑗 ) =   { 2𝑖, 𝑢𝑛𝑡𝑢𝑘 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1,3]
2𝑖 − 1, 𝑢𝑛𝑡𝑢𝑘 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [4,5]
𝑐(𝑢 𝑖,𝑗 𝑣 𝑖,𝑗+1 ) = 2𝑖 + 1, untuk 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛], 2𝑡 + 1 = 1
Pewarnaan  pelangi  untuk  amalgamasi  graf  berlian 𝐴𝑚𝑎𝑙(𝐵𝑟 4 , 𝑣, 2), 𝐴𝑚𝑎𝑙(𝐵𝑟 5 , 𝑣, 3), dan 𝐴𝑚𝑎𝑙(𝐵𝑟 6 , 𝑣, 4) berturut-turut dapat dilihat pada gambar 3.2, gambar 3.2, dan gambar 3.4. Untuk menunjukan bahwa terdapat lintasan  dari  titik 𝑥 ke  titik 𝑦 di 𝑉(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) dengan 𝑑𝑖𝑎𝑚(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) = 4 ,  maka  diperoleh lintasan pelangi :
Kasus 1. Untuk 𝑛 = 4
Subkasus 1.1. Lintasan berjarak 2
Misalkan 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑣 𝑖,𝑗+2 dengan 𝑖 ∈ [1, 𝑡] ,  dan 𝑗 ∈ [1,2] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑢 𝑖,𝑗 , 𝑢 𝑖,𝑗+1 , 𝑣 𝑖,𝑗+2 .
Kasus 2. Untuk 4 ≤ 𝑛  ≤ 6
Subkasus 2.1. Lintasan berjarak 2
1. Misalkan 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑣 dengan 𝑖 ∈ [1, 𝑡] dan 𝑗 ∈ [1, 𝑛 − 1]. Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗 , 𝑣 . 2. Misalkan 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑢 𝑖,𝑗+2 dengan 𝑖 ∈ [1, 𝑡] dan 𝑗 ∈ [1, 𝑛 − 3]. Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑢 𝑖,𝑗 , 𝑢 𝑖,𝑗+1 , 𝑢 𝑖,𝑗+2 . 3. Misalkan 𝑥 = 𝑣 𝑖,𝑗 dan 𝑦 = 𝑣 𝑖,𝑗+2 dengan 𝑖 ∈ [1, 𝑡] dan 𝑗 ∈ [1, 𝑛 − 2]. Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑣 𝑖,𝑗 , 𝑣 𝑖,𝑗+1 , 𝑣 𝑖,𝑗+2 .
4. Misalkan 𝑥 = 𝑣 𝑖,𝑗 dan 𝑦 = 𝑣 𝑖,𝑙 dengan 𝑖 ∈ [1, 𝑡] , 𝑗 ∈ [1, 𝑛 − 3] dan 𝑙 ∈ [4, 𝑛] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑖,𝑙 . 5. Misalkan 𝑥 = 𝑣 𝑖,𝑗 dan 𝑦 = 𝑣 𝑘,𝑙 dengan 𝑖 ∈ [1, 𝑡 − 1] , 𝑗, 𝑙 ∈ [1, 𝑛] dan 𝑘 ∈ [𝑖 + 1, 𝑡] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑘,𝑙 .
6. Misalkan 𝑥 = 𝑣 𝑖,𝑗 dan 𝑦 = 𝑢 𝑖,𝑗+1 dengan 𝑖 ∈ [1, 𝑡] ,  dan 𝑗 ∈ [1, 𝑛 − 2] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑣 𝑖,𝑗 , 𝑣 𝑖,𝑗+1 , 𝑢 𝑖,𝑗+1 .
Subkasus 2.2. Lintasan berjarak 3
1. Misalkan 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑣 𝑖,𝑙 dengan 𝑖 ∈ [1, 𝑡] , 𝑗 ∈ [1, 𝑛 − 3] , dan 𝑙 ∈ [4, 𝑛] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗+1 , 𝑣, 𝑣 𝑖,𝑙 . 2. Misalkan 𝑥 = 𝑣 𝑖,𝑗 dan 𝑦 = 𝑢 𝑖,𝑙 dengan 𝑖 ∈ [1, 𝑡] , 𝑗 ∈ [1, 𝑛 − 3] , dan 𝑙 ∈ [3, 𝑛 − 1] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑖,𝑙+1 , 𝑢 𝑖,𝑙 . 3. Misalkan 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑣 𝑘,𝑙 dengan 𝑖 ∈ [1, 𝑡 − 1] , 𝑗 ∈ [1, 𝑛 − 1] , 𝑘 ∈ [𝑖 + 1, 𝑡] , dan 𝑙 ∈ [1, 𝑛] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑘,𝑙 . 4. Misalkan 𝑥 = 𝑣 𝑖,𝑗 dan 𝑦 = 𝑢 𝑘,𝑙 dengan 𝑖 ∈ [1, 𝑡 − 1] , 𝑗 ∈ [1, 𝑛] , 𝑘 ∈ [𝑖 + 1, 𝑡] , dan 𝑙 ∈ [1, 𝑛 − 1] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑘,𝑙 , 𝑢 𝑘,𝑙 .
Subkasus 2.3. Lintasan berjarak 4
Misalkan 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑢 𝑘,𝑙 dengan 𝑖 ∈ [1, 𝑡 − 1] , 𝑗, 𝑙 ∈ [1, 𝑛 − 1] ,  dan 𝑘 ∈ [𝑖 + 1, 𝑡] .  Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑘,𝑙 , 𝑢 𝑘,𝑙 .
Kasus 3. Untuk 𝑛 = 5 dan 𝑛 = 6
Subkasus 3.1. Lintasan berjarak 2
Subkasus 3.1. Lintasan berjarak 2
Misalkan 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑣 𝑖,𝑗+2 dengan 𝑖 ∈ [1, 𝑡] ,  dan 𝑗 ∈ [1, 𝑛 − 2] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗+1 , 𝑣 𝑖,𝑗+2 .
Subkasus 3.1. Lintasan berjarak 3
Misalkan 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑢 𝑖,𝑗+3 dengan 𝑖 ∈ [1, 𝑡] dan 𝑗 ∈ [1, 𝑛 − 4] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑢 𝑖,𝑗 , 𝑢 𝑖,𝑗+1 , 𝑢 𝑖,𝑗+2 , 𝑢 𝑖,𝑗+3 .
Kasus 4. Untuk 𝑛 = 6
Subkasus 4.1. Lintasan berjarak 4
Misalkan 𝑥 = 𝑢 𝑖,1 dan 𝑦 = 𝑢 𝑖,5 dengan 𝑖 ∈ [1, 𝑡] . Terdapat lintasan pelangi 𝑥 ke 𝑦 yaitu 𝑢 𝑖,1 , 𝑢 𝑖,2 , 𝑢 𝑖,3 , 𝑢 𝑖,4 , 𝑢 𝑖,5 .
Gambar 2. Pewarnaan Pelangi 𝐴𝑚𝑎𝑙(𝐵𝑟 4 , 𝑣, 2)
Gambar 3. Pewarnaan Pelangi 𝐴𝑚𝑎𝑙(𝐵𝑟 5 , 𝑣, 3)
Gambar 4. Pewarnaan Pelangi 𝐴𝑚𝑎𝑙(𝐵𝑟 6 , 𝑣, 4)

## 4. Kesimpulan
Dari pembahasan diatas maka diperoleh bilangan terhubung pelangi pada amalgamasi graf berlian adalah : 𝑟𝑐 (𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) = 2𝑡 .
Penelitian selanjutnya dapat dilanjutkan untuk 𝑛 ≥ 6 .

## Referensi
[1] R. Munir, Matematika Disktrit , 3rd ed. Bandung: Informatika Bandung, 2010.
[2] J.  L.  Gross,  “Genus distribution  of  graph  amalgamations:  Self -pasting  at  root- vertices,” Australas.  J. Comb. , vol. 49, pp. 19 – 38, 2011.
[3] G. Chartrand, D. Erwin, P. Zhang, and M. Bohemica, “Mathematica Bohemica Terms of use:,” vol. 127, no. 1, 2008.
[4] M. A. Shulhany and A. N. M. Salman, “Bilangan Terhubung Pelangi Graf Berlian,” 2015.