PEWARNAAN TITIK DAN SISI PADA GRAF BINTANG SIERPINSKI MENGGUNAKAN ALGORITMA WELCH POWELL

Arif Fabikhan, NIM.: 15610048 (2020) PEWARNAAN TITIK DAN SISI PADA GRAF BINTANG SIERPINSKI MENGGUNAKAN ALGORITMA WELCH POWELL. Skripsi thesis, UIN SUNAN KALIJAGA YOGYAKARTA.

Preview	Text (PEWARNAAN TITIK DAN SISI PADA GRAF BINTANG SIERPINSKI MENGGUNAKAN ALGORITMA WELCH POWELL) 15610048_BAB-I_BAB-IV_DAFTAR PUSTAKA.pdf - Published Version Download (2MB) | Preview
	Text (PEWARNAAN TITIK DAN SISI PADA GRAF BINTANG SIERPINSKI MENGGUNAKAN ALGORITMA WELCH POWELL) 15610048_BAB-II_BAB-III.pdf - Published Version Restricted to Registered users only Download (4MB)

Abstract

Pewarnaan dalam teori graf berarti pemberian warna ke semua titik atau sisi suatu graf G sehingga tidak ada titik atau sisi yang bertetangga dengan warna yang sama. Algorimta Bilangan kromatik adalah jumlah warna minimum yang digunakan untuk pewarnaan graf, dimana bilangan kromatik titik graf G dilambangkan dengan ()G dan bilangan kromatik sisi graf G dilambangkan dengan '( )G . Salah satu algoritma pada pewarnaan graf adalah algoritma Welch Powell yang melakukan pewarnaan dengan mendahulukan titik atau sisi berdasarkan derajat maksimumnya. Penelitian ini membahas pewarnaan titik dan sisi pada graf bintang Sierpinski SS yang dikonstruksi berdasarkan segitiga Sierpinski. Segitiga Sierpinski merupakan fraktal yang serupa dengan dirinya yang dibangun dari n sebuah segitiga sama sisi yang dibagi secara rekursif menjadi 4 buah segitiga yang kongruen dengan skala setengah dari segitiga sebelumnya. Berdasarkan hasil pembahsan, diperoleh bahwa bilangan kromatik pada pewarnaan titik graf SS adalah 2 untuk 2n  , sedangkan bilangan kromatik pada pewarnaan sisi graf n SS adalah n 3.2 n 2 untuk 2n  atau sama dengan derajat maksimum titiknya.

Share this knowledge with your friends :

Actions (login required)

View Item