Implementasi masalah pewarnaan graph pada penjadwalan kuliah dengan algoritma Welch-Powell / Tatik Octiarsih Kartika Puji Rahayu
| Main Author: | Rahayu, Tatik Octiarsih Kartika Puji |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2010
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17019/ |
Daftar Isi:
- KatakuncipewarnaansimpulbilangankromatikalgoritmaWelch-PowellpenjadwalankuliahAdabeberapamasalahpewarnaandalamTeoriGraphtigadiantaranyaadalahpewarnaansimpulpewarnaansisidanpewarnaanwilayah.Teknikpewarnaanyangseringdigunakandalamkehidupansehari-hariadalahpewarnaansimpul.Salahsatukegunaanpewarnaansimpuldalamkehidupansehari-hariadalahmembantumenyelesaikanmasalahpenyusunanjadwalkuliah.PewarnaansimpuladalahmewarnaisemuasimpulpadagraphGsehinggasetiappasangsimpulyangterhubunglangsungmemilikiwarnayangberbeda.Banyaknyawarnaminimumyangdigunakanuntukmewarnaidisebutdenganbilangankhromatik.Terdapatbanyakalgoritmayangdapatdigunakanuntukmenyelesaikanmasalahpenjadwalan.SalahsatunyaadalahalgoritmaWelch-Powell.Langkahpertamaalgoritmainiadalahmenentukanderajatsetiapsimpulkemudianmengurutkanmulaidarisimpulyangderajatnyaterbesar.Langkahselanjutnyasimpulyangmemilikiderajatterbesardiberiwarnaterlebihdahulu.Kemudiandicarisimpulmanayangtidakterhubunglangsungdengansimpulyangtelahdiwarnadanberiwarnasimpultersebutdenganwarnayangsama.Algoritmainidapatdigunakanuntukmenyusunjadwalkuliahsehinggatidakadajadwalyangbertabrakan.Artinyatidakadaduamatakuliahyangdiambilolehseorangmahasiswadilaksanakanpadawaktuyangbersamaan.Sesuaidenganlangkah-langkahnyaalgoritmainihanyamemberikaninformasitentangbanyakwarnayangdigunakanbukanbilangankhromatiknya.Dengandemikiandapatditentukanbanyakwaktuuntukmelaksanakanperkuliahan.UntukmenyelesaikanmasalahpenjadwalankuliahdibuatprogramdenganmemanfaatkansoftwareDelphi7.SetelahdiamatiprosespengerjaandenganalgoritmaWelch-Powellsecaramanualataupunmenggunakanimplementasiprogrammemberikanhasilyangsama.