Pewarnaan Metrik pada Graf Hasil Operasi Comb Graf Lintasan

Abstract

Topik yang dijadikan sebagai bahan kajian dalam penelitian ini adalah pewarnaan metrik. Pewarnaan graf adalah salah satu cara pelabelan dengan cara memberikan warna yang berbeda pada titik, sisi, atau wilayah yang bertetangga. Pewarnaan dibagi menjadi tiga macam, salah satunya yaitu pewarnaan titik. Pewarnaan titik merupakan pewarnaan dengan memberikan warna berbeda pada setiap titik yang bertetangga. Jumlah warna minimum yang digunakan untuk pewarnaan titik disebut bilangan kromatik, dan dinotasikan dengan (G). Pewarnaan metrik merupakan penggabungan dari dua konsep yaitu metrik dimension dan pewaraan titik. Warna minimum dari pewarnaan metrik disebut dengan bilangan kromatik metrik dan dinotasikan dengan µ(G). Pewarnaan metrik yaitu memberikan label pada setiap titik dengan label 1 hingga n dimana label tersebut harus seminimal mungkin, warna pada pewarnaan metrik diperoleh dengan representasi dari setiap label yang diperoleh. Operasi graf merupakan salah satu cara untuk memperoleh graf baru, operasi yang digunakan dalam penelitian ini yaitu operasi comb. Operasi comb merupakan operasi dua buah graf G dan H dimana graf G adalah punggung dan graf H adalah daun, sehingga dapat dinotasikan dengan (G Bo H), operasi comb (G Bo H) dapat diartikan dengan menduplikasikan graf H sebanyak satu titik pada graf G kemudian masing-masing titik pada graf G di hubungkan pada satu titik graf G hasil duplikat. Graf yang digunakan dalam penelitian ini yaitu graf hasil operasi comb graf lintasan Pn Bo G, dimana G ⇠= Pm, Cm, Fm, Sm, dan Km Dari hasil penelitian diperoleh 5 teorema, diantaranya sebagai berikut. Teorema 1 Bilangan kromatik metrik dari graf Pn Bo Pm, untuk n, m 2 adalah µ(Pn Bo Pm)=2. Teorema 2 Bilangan kromatik metrik dari graf Pn Bo Cm, untuk n 2, m 3 adalah µ(Pn Bo Cm) = ( 2, untuk m genap 3, untuk m ganjil Teorema 3 Bilangan kromatik metrik dari graf Pn Bo Fm, untuk n 2, m 3 adalah µ(Pn Bo Fm)=3. Teorema 4 Bilangan kromatik metrik dari graf Pn Bo Sm, untuk n 2, m 3 adalah µ(Pn Bo Sm)=2. Teorema 5 Bilangan kromatik metrik dari graf Pn Bo Km, untuk n 2, m 2 adalah µ(Pn Bo Km) = m