BILANGAN KROMATIK–TOTAL GRAF HASIL OPERASI SHACKLE

Abstract

Teori graf memiliki cukup banyak pembahasan yang dikaji, salah satunya adalah pewarnaan titik dan sisi yang disebut bilangan kromatik total. Pewarnaan sejati dari graf yaitu memberikan warna ke titik atau sisi atau keduanya (total) sedemikianhinggaelemen(titikatausisiataukeduanya)terdekatdiwarnaidengan warna yang berbeda. Sebuah pewarnaan-total pada graf G adalah pemberianwarna titik V(G) dan sisi E(G) pada G sedemikian hingga setiap 2 titik yang berhubungan langsung dan setiap sisi yang terkait pada titik yang sama mendapatkan warna yang berbeda. Bilangan kromatik-total sebuah graf G, dinotasikan𝜒𝑇(𝐺), yaitu minimum warna yang dibutuhkan untuk pewarnaan-total pada G. Graf yang dikaji adalah graf lintasan (𝑃𝑛) dan graf sikel (𝐶𝑛) yang dioperasikandenganoperasi𝑆ℎ𝑎𝑐𝑘𝑙𝑒sehinggamembentukkelas 𝑆ℎ𝑎𝑐𝑘(𝑃𝑛,𝑥𝑖,𝑚) dan 𝑆ℎ𝑎𝑐𝑘(𝐶𝑛,𝑥𝑖,𝑚). Metode yang digunakan dalam penelitian ini adalah penelitian eksploratif, dimana penelitian ini merupakan bagian dari penelitian murni (basic research) yang bertujuan untuk mengembangkan dan menemukan teori baru. Instrumen penelitian berupa jurnal, artikel penelitian serta buku yang terkait serta menggunakan tools Sketchpad 5.06 yang digunakan untuk menggambargrafoperasi𝑆ℎ𝑎𝑐𝑘𝑙𝑒.Hasilpenelitiandiperolehbilangankromatik 𝜒(𝑆ℎ𝑎𝑐𝑘(𝑃𝑛,𝑥𝑖,𝑚))=4𝑑𝑎𝑛𝜒(𝑆ℎ𝑎𝑐𝑘(𝐶𝑛,𝑥𝑖,𝑚))= 2,jika𝑛genapdan3jika 𝑛 ganjil, dan kromatik total untuk 𝜒𝑇(𝑆ℎ𝑎𝑐𝑘(𝑃𝑛,𝑥𝑖,𝑚))=4 dan 𝜒𝑇(𝑆ℎ𝑎𝑐𝑘(𝐶𝑛,𝑥𝑖,𝑚))= 6untuk𝑛genapdan5untuk𝑛ganjil.