Rahayu, Tatik Octiarsih Kartika Puji (2010) Implementasi masalah pewarnaan graph pada penjadwalan kuliah dengan algoritma Welch-Powell / Tatik Octiarsih Kartika Puji Rahayu. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Kata kunci pewarnaan simpul bilangan kromatik algoritma Welch-Powell penjadwalan kuliah Ada beberapa masalah pewarnaan dalam Teori Graph tiga diantaranya adalah pewarnaan simpul pewarnaan sisi dan pewarnaan wilayah. Teknik pewarnaan yang sering digunakan dalam kehidupan sehari-hari adalah pewarnaan simpul. Salah satu kegunaan pewarnaan simpul dalam kehidupan sehari-hari adalah membantu menyelesaikan masalah penyusunan jadwal kuliah. Pewarnaan simpul adalah mewarnai semua simpul pada graph G sehingga setiap pasang simpul yang terhubung langsung memiliki warna yang berbeda. Banyaknya warna minimum yang digunakan untuk mewarnai disebut dengan bilangan khromatik. Terdapat banyak algoritma yang dapat digunakan untuk menyelesaikan masalah penjadwalan. Salah satunya adalah algoritma Welch-Powell. Langkah pertama algoritma ini adalah menentukan derajat setiap simpul kemudian mengurutkan mulai dari simpul yang derajatnya terbesar. Langkah selanjutnya simpul yang memiliki derajat terbesar diberi warna terlebih dahulu. Kemudian dicari simpul mana yang tidak terhubung langsung dengan simpul yang telah diwarna dan beri warna simpul tersebut dengan warna yang sama. Algoritma ini dapat digunakan untuk menyusun jadwal kuliah sehingga tidak ada jadwal yang bertabrakan. Artinya tidak ada dua matakuliah yang diambil oleh seorang mahasiswa dilaksanakan pada waktu yang bersamaan. Sesuai dengan langkah-langkahnya algoritma ini hanya memberikan informasi tentang banyak warna yang digunakan bukan bilangan khromatiknya. Dengan demikian dapat ditentukan banyak waktu untuk melaksanakan perkuliahan. Untuk menyelesaikan masalah penjadwalan kuliah dibuat program dengan memanfaatkan software Delphi 7. Setelah diamati proses pengerjaan dengan algoritma Welch-Powell secara manual ataupun menggunakan implementasi program memberikan 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: | 19 Oct 2010 04:29 |
| Last Modified: | 09 Sep 2010 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17019 |
Actions (login required)
 |
View Item |