Pewarnaan Metrik pada Keluarga Graf Pohon sebagai E-Monograf

Abstract

Penelitian ini mengambil topik pewarnaan titik pada graf. Pewarnaan titik merupakan pemberian warna pada titik sedemikian hingga tidak ada titik bertetangga yang mempunyai warna sama. Jenis pewarnaan titik yang digunakan adalah pewarnaan metrik. Pewarnaan metrik merupakan penggabungan konsep antara pewarnaan graf dengan sub topik dimensi metrik dalam graf. Dalam pewarnaan metrik, setiap titik pada graf boleh diwarnai dengan warna yang sama selama titik yang bertetangga mempunyai kode metrik yang berbeda. Banyak warna minimum yang diperoleh dari pewarnaan metrik disebut bilangan kromatik metrik. Tujuan dari pewarnaan metrik adalah untuk menemukan bilangan kromatik metrik. Graf yang digunakan adalah keluarga graf pohon, termasuk graf E, graf sapu, graf serangga seribu kaki, graf sapu ganda, dan graf H. Keluarga graf ini dipilih karena karakteristik unik dari pohon itu sendiri, yaitu graf terhubung dan tak berarah yang tidak memiliki siklus serta belum ada penelitian sebelumnya yang dilakukan pada graf ini. Pembuktian dimulai dengan menentukan batas bawah, kemudian menentukan batas atas menggunakan fungsi pewarnaan dan kode metrik. Memastikan apakah fungsi pewarnaan metrik telah menghasilkan kode metrik yang berbeda untuk setiap dua simpul yang berdekatan.