| Popis: |
Pewarnaan graf dapat dilakukan dengan 3 cara yaitu pewarnaan sisi (edge), titik/simpul (vertex), dan wilayah (region). Pada tulisan ini yang digunakan adalah pewarnaan titik/simpul pada graf sederhana. Pewarnaan titik adalah bagaimana mewarnai titik pada suatu graf sedemikian sehingga dua titik yang bertetangga memiliki warna yang berbeda. Tujuan utama pewarnaan titik pada graf adalah mendapatkan banyaknya warna minimum dari suatu graf yang biasa disebut bilangan khromatik. Terdapat beberapa cara dalam melakukan pewarnaan titik suatu graf, diantaranya dengan menggunakan algoritma Welch-Powell, algoritma jaringan saraf tiruan, dan algoritma baris. Pada penelitian ini dilakukan pewarnaan titik dengan menggunakan algoritma baris dan implementasinya berupa program menggunakan MATLAB. Kompleksitas program algoritma baris yang dihasilkan terbagi dua yaitu kompleksitas waktu asimptotik untuk kasus terbaik dan kompleksitas waktu asimptotik untuk kasus terburuk. |
