Bilangan Kromatik Equitable Pada Graf Bintang, Graf Lolipop, Dan Graf Persahabatan

Praja, Yuda (2023) Bilangan Kromatik Equitable Pada Graf Bintang, Graf Lolipop, Dan Graf Persahabatan. Skripsi thesis, Universitas Tanjungpura.

	Text (Cover-Bab I) Cover-Bab1_H1011191030.pdf - Published Version Download (615kB)
	Text (H1011191030_YUDA PRAJA) H1011191030_YUDA PRAJA.pdf - Accepted Version Restricted to Repository staff only Download (962kB)

Abstract

Diberikan sebarang graf G yang terhubung dan tak berarah. Pewarnaan simpul pada graf G adalah pemetaan dari himpunan simpul pada graf G ke himpunan warna sedemikian sehingga untuk setiap dua simpul yang bertetangga mempunyai warna yang berbeda. Salah satu pengembangan dari konsep pewarnaan simpul adalah pewarnaan equitable. Pewarnaan equitable dari graf G adalah pewarnaan simpul graf G yang memenuhi syarat bahwa untuk setiap kelas warna yang diinduksi memiliki kardinalitas yang merata dengan beda 0 atau 1. Minimum banyaknya warna yang digunakan untuk pewarnaan equitable pada graf G disebut bilangan kromatik equitable G, yang dinotasikan dengan χe(G). Penggunaan graf pada penelitian ini dibatasi oleh graf yang memiliki simpul pusat, yaitu satu simpul yang bertetangga dengan setiap simpul lainnya, seperti graf bintang (Sn), graf lolipop (Ln), graf persahabatan (fn). Penelitian ini bertujuan untuk merumuskan bilangan kromatik equitable pada graf bintang (Sn), graf lolipop (Ln), graf persahabatan (fn). Langkah pertama yang dilakukan dalam penelitian ini adalah menerapkan pewarnaan simpul pada Sn, Ln, dan fn. Setelah itu, diperoleh kelas warna pada himpunan simpul dan ditentukan kardinalitasnya. Tahap selanjutnya adalah menganalisis bahwa pewarnaan simpul yang diterapkan memenuhi definisi pewarnaan equitable. Kemudian, membuktikan bahwa banyaknya warna yang digunakan adalah minimum. Sehingga diperoleh bilangan kromatik untuk masing-masing graf dan dibuktikan kebenarannya. Berdasarkan penelitian ini, diperoleh bilangan kromatik equitable Sn adalah ⌈n/2⌉ + 1, bilangan kromatik equitable Ln adalah n, dan bilangan kromatik equitable fn adalah 3, untuk n = 1 dan n + 1, untuk n ≥ 2.

Actions (login required)

View Item