Ardhian, Nia Prastuti (2010) Penyelesaian masalah pewarnaan simpul pada graph dengan algoritma gabungan dan implementasinya / Nia Prastuti Ardhian. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
ABSTRAK Ardhian Nia Prastuti. 2010. Penyelesaian Masalah Pewarnaan Simpul pada Graph dengan Algoritma Gabungan dan Implementasinya. Skripsi Jurusan Matematika FMIPA Universitas Negeri Malang. Pembimbing (I) Dra. Sapti Wahyuningsih M.Si (II) Darmawan Satyananda S.T M.T Kata kunci pewarnaan simpul bilangan kromatik algoritma gabungan penjadwalan ujian Dalam Teori Graph masalah pewarnaan graph terdiri dari tiga macam yaitu pewarnaan simpul pewarnaan sisi dan pewarnaan wilayah. Teknik pewarnaan simpul merupakan salah satu subyek yang menarik dalam bidang graph. Pewarnaan simpul adalah mewarnai semua simpul di sehingga setiap pasang simpul yang terhubung langsung diberi warna yang berbeda. Jumlah warna minimum yang diperlukan disebut bilangan kromatik Terdapat beberapa algoritma heuristik yang digunakan untuk menemukan bilangan kromatik suatu graph. Di antaranya adalah Algoritma First Fit (FF) Largest Degree Ordering (LDO) Saturated Degree Ordering (SDO) dan Incident Degree Ordering (IDO). Teknik ini memusatkan bagaimana cara pengambilan simpul yang akan diwarnai berikutnya secara hati-hati. Aplikasi dari teknik pewarnaan simpul telah banyak diterapkan di berbagai bidang yang memiliki karakteristik yang analog dengan masalah pewarnaan simpul. Salah satunya adalah penentuan jadwal ujian. Diperlukan suatu metode yang lebih baik dari algoritma heuristik untuk menemukan bilangan kromatik suatu graph. Salah satunya adalah Algoritma Gabungan. Langkah pertama pada Algoritma Gabungan adalah membangun spanning tree. Pada akhir langkah ini spanning tree dapat diwarnai dengan dua warna. Langkah berikutnya adalah memeriksa sisi-sisi yang bermasalah yaitu sisi yang tidak termasuk ke dalam spanning tree. Bila warna kedua simpul sama maka warna salah satu simpul harus diubah. Untuk mengubah warna simpul digunakan algoritma modifikasi dari Algoritma Largest Degree Ordering (LDO) dan Saturated Degree Ordering (SDO). Kelebihan menggunakan Algoritma Gabungan bila dibandingkan dengan menggunakan polinom kromatik adalah selain mengetahui bilangan kromatik juga dapat diketahui warna yang diberikan pada setiap simpul sehingga kita dapat menyusun jadwal ujian sehingga tidak ada jadwal yang bertabrakan yaitu tidak ada mahasiswa yang harus menempuh dua ujian dalam waktu yang bersamaan. Sekilas terlihat bahwa algoritma gabungan ini menjadi lebih rumit tetapi berdasarkan penelitian yang pernah dilakukan algoritma-algoritma yang digabung akan memiliki efisiensi yang lebih tinggi dibandingkan dengan masing-masing algoritma heuristik yang berdiri sendiri. Untuk menyelesaikan masalah penjadwalan ujian dibuat program yang menggunakan software Delphi 7. Berdasarkan perhitungan dengan menggunakan Algoritma Gabungan yang dilakukan secara manual maupun menggunakan implementasi 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: | Users 2 not found. |
| Date Deposited: | 30 Jun 2010 04:29 |
| Last Modified: | 09 Sep 2010 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/16903 |
Actions (login required)
 |
View Item |