Hidayati, Purwanti (2010) Pewarnaan titik pada graph dengan algoritma backtracking dan aplikasinya / Purwanti Hidayati. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Kata kunci pewarnaan titik pewarnaan peta bilangan kromatik algoritma backtracking Dalam teori graph masalah pewarnaan graph terdiri dari tiga macam yaitu pewarnaan titik pewarnaan sisi dan pewarnaan wilayah. Teknik pewarnaan titik merupakan topik yang paling sering dibahas pada graph. Masalah utama pewarnaan titik adalah mewarnai semua titik sehingga tidak ada titik yang terhubung langsung memiliki warna yang sama. Contoh masalah yang dapat diselesaikan dengan pewarnaan titik salah satunya adalah pewarnaan peta. Sebenarnya pewarnaan peta ini merupakan bentuk lain dari pewarnaan titik karena pewarnaan peta merupakan pewarnaan wilayah dengan daerahnya dianggap sebagai titik dan wilayah yang berdekatan dihubungkan dengan sisi. Tujuan utama pewarnaan adalah mendapat bilangan jumlah warna minimum untuk mewarnai graph atau yang disebut bilangan kromatik. Algoritma yang digunakan pada pewarnaan biasanya menghasilkan satu solusi contohnya algoritma Welch-Powell. Terdapat algoritma yang dapat menghasilkan semua kemungkinan solusi yaitu algoritma backtracking. Algoritma backtracking adalah algoritma yang menyelesaikan persoalan pewarnaan dengan mengubah bentuk graph menjadi pohon dengan tiap titik pohon menyatakan status persoalan sedangkan cabang pada pohon diberi label yang merupakan kemungkinan warna untuk setiap titik pada graph. Kemudian pohon tersebut ditelusuri secara DFS (Depth First Search) sampai semua solusi dihasilkan. Pohon yang terbentuk ini disebut pohon ruang status. Kelebihan algoritma ini dibandingkan dengan menggunakan teorema empat warna yang berisi setiap graph planar dapat diwarnai dengan empat warna yaitu dapat diketahui warna yang diberikan pada tiap titik sehingga dapat digunakan untuk mewarnai peta. Sekilas algoritma backtracking terlihat rumit tetapi algoritma ini dapat menghasilkan semua kemungkinan solusi dari semua kemungkinan solusi itu dicari warna yang paling minimum. Untuk menyelesaikan masalah pewarnaan peta dibuat program yang menggunakan software Delphi 7. Berdasarkan perhitungan dengan algoritma backtracking secara manual maupun menggunakan aplikasi program diperoleh hasil yang sama.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 08 Oct 2010 04:29 |
| Last Modified: | 09 Sep 2010 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17012 |
Actions (login required)
 |
View Item |