PROGRAM PEWARNAAN GRAF UNTUK PEMODELAN PENJADWALAN UJIAN SEMESTER DI JURUSAN MATEMATIKA UNNES

PROGRAM PEWARNAAN GRAF UNTUK PEMODELAN PENJADWALAN UJIAN SEMESTER DI JURUSAN MATEMATIKA UNNES

skripsi disajikan sebagai salah satu syarat untuk memperoleh gelar Sarjana Sain Program Studi Matematika

oleh Indra Bayu Muktyas 4150406043

JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI SEMARANG 2010

PERNYATAAN

Saya menyatakan bahwa yang tertulis dalam skripsi ini benar-benar hasil karya saya sendiri, bukan jiplakan dari karya tulis orang lain, baik sebagian atau seluruhnya. Pendapat atau temuan orang lain yang terdapat dalam skripsi ini, dikutip atau dirujuk berdasarkan kode etik ilmiah.

Semarang,

Agustus 2010

Yang membuat pernyataan,

Indra Bayu Muktyas NIM. 4150406043

ii

ABSTRAK Indra Bayu Muktyas. 2010. Program Pewarnaan Graf untuk Pemodelan Penjadwalan Ujian Semester di Jurusan Matematika Unnes. Skripsi. Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Semarang. Pembimbing I: Isnaini Rosyida, S.Si, M.Si. Pembimbing II: Endang Sugiharti, S.Si, M.Kom. Kata kunci: mahasiswa, mata kuliah, penjadwalan ujian semester, pewarnaan graf, visual basic application. Di jurusan Matematika Unnes, penjadwalan ujian semester dilakukan secara manual. Kemudian dilakukan perevisian jadwal yang terkadang memakan waktu sangat lama karena tumbuk jadwal satu dengan yang lain. Permasalahan ini dapat diselesaikan dengan sangat mudah dengan pewarnaan titik graf. Sebuah pewarnaan titik dari graf G=(V,E) adalah sebuah pemetaan F : V   di mana titik–titik yang bertetangga berwarna berbeda di N, yaitu jika sisi uv  E , maka F (u )  F (v) . Permasalahan yang diangkat dalam skripsi ini adalah bagaimana perancangan progam komputer untuk menyelesaikan pewarnaan graf, bagaimana visualisasi masalah penjadwalan ujian semester di Jurusan Matematika Unnes dalam graf, dan bagaimana hasil pewarnaan graf dalam menyelesaikan masalah penentuan jadwal ujian semester di Jurusan Matematika Unnes. Metode yang digunakan pada penulisan skripsi ini adalah studi pustaka, perumusan masalah mengenai program komputer dari algoritma Welch dan Powell dengan eksperimen, pemodelan ujian semester di Jurusan Matematika Unnes dalam bentuk graf, serta aplikasi program komputer tersebut dalam penjadwalan ujian semester di jurusan Matematika Unnes ke dalam bentuk graf. Selanjutnya disusun pemecahan masalah dalam bentuk pembahasan. Langkah-langkah yang dilakukan dalam membuat progam komputer untuk menyelesaikan pewarnaan graf adalah dengan membuat diagram alur algoritma Welch dan Powell kemudian mengubahnya ke dalam bahasa pemrograman VBA pada Microsoft Excel. Penjadwalan ujian semester di Jurusan Matematika Unnes dapat divisualisasikan dalam bentuk matriks ketetanggaan graf. Dari program komputer yang dibuat, diperoleh hasil 24 warna (periode waktu) berbeda untuk 84 mata kuliah pada semester genap tahun 2009/2010. Angka tersebut dapat dikelompokkan menjadi 8 hari karena tiap hari ada 3 warna (periode waktu). Hasil ini sangat membantu petugas bidang akademik. Penulis menyarankan agar program tersebut ditingkatkan lagi dalam hal kecepatan, ketepatan jadwal, dan kemudahan mengakses. Akan lebih baik lagi jika variabel-variabel lain seperti ruang kelas dan dosen dimasukkan pula ke dalam program tersebut.

iii

PENGESAHAN Skripsi yang berjudul Program Pewarnaan Graf untuk Pemodelan Ujian Semester di Jurusan Matematika Unnes disusun oleh Nama : Indra Bayu Muktyas NIM : 4150406043 telah dipertahankan di hadapan sidang Panitia Ujian Skripsi FMIPA Unnes pada tanggal 2 September 2010. Panitia: Ketua

Sekretaris

Dr. Kasmadi Imam S., M.S. NIP. 195111151979031001

Drs. Edy Soedjoko, M.Pd. NIP. 195604191987031001

Ketua Penguji

Drs. Amin Suyitno, M.Pd. NIP. 195206041976121001 Anggota Penguji/ Pembimbing Utama

Anggota Penguji/ Pembimbing Pendamping

Isnaini Rosyida, S.Si, M.Si NIP. 197302191998022001

Endang Sugiharti, S.Si, M.Kom NIP. 197401071999032001

iv

MOTTO DAN PERSEMBAHAN

MOTTO “Awali setiap sesuatu dengan Bismillaah” “Bisa karena biasa, maka biasakanlah untuk bisa” “Rasakan Allah selalu bersama kita, maka semua akan terasa begitu ringan” (Najma Tsaqib)

PERSEMBAHAN Skripsi ini penulis persembahkan kepada: Allah Subhanahu wa ta’ala.

v

KATA PENGANTAR

Segala puji syukur penulis panjatkan atas segala kenikmatan yang Allah berikan. Tiada yang bisa penulis lakukan tanpa rahmat-Nya. Semoga Allah selalu memberikan keridhoan di setiap jalan yang kita tempuh. Sholawat dan salam selalu tercurah kepada sang tauladan umat, Nabi Muhammad Saw, beserta keluarga dan sahabat yang setia dalam menegakkan agama Islam. Alhamdulillah, atas berkah dan rahmat yang Allah berikan, penulis dapat menyelesaikan skripsi ini. Dalam kesempatan ini penulis mengucapkan banyak terima kasih kepada: 1. Prof. Dr. H. Sudijono Sastroatmodjo, M.Si. Rektor Universitas Negeri Semarang (UNNES). 2. Dr. Kasmadi Imam S, M.S. Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) Universitas Negeri Semarang. 3. Drs. Edy Soejoko, M.Pd. Ketua Jurusan Matematika. 4. Isnaini Rosyida, S.Si, M.Si Pembimbing I yang telah memberikan petunjuk, arahan, dan bimbingan dalam penyusunan skripsi ini. 5. Endang Sugiharti, S.Si, M.Kom Pembimbing II yang telah memberikan bimbingan dan masukan dalam penyusunan skripsi ini. 6. Bapak dan Ibu Dosen Jurusan Matematika yang telah memberikan bekal dalam penyusunan skripsi ini.

vi

7. Yang paling utama, Bapak Edi haryono dan Ibu Endriyani, Orang tua penulis yang begitu besar pengorbanan jiwa dan raga beliau sehingga penulis dapat menjadi seperti saat ini, serta seluruh keluarga. 8. Teman-teman Matreg 06, PKL di BPS Kendal, KKN PBA Unnes Desa Sidomulyo Kec. Kesesi, SIGMA matematika, Paduan Suara Bina Vokalia FMIPA Unnes, Suara Pujangga, Ulin Nuha, Basmala, ANN Jateng, dan Beswan Djarum 2008. 9. Semua pihak yang telah membantu terselesaikannya skripsi ini, serta memberikan kenangan begitu mengesankan yang tidak dapat penulis sebutkan satu persatu. Semoga skripsi ini bermanfaat bagi pembaca demi kebaikan di masa yang akan datang.

Semarang,

Penulis

vii

Agustus 2010

DAFTAR ISI Halaman ABSTRAK .............................................................................................. iii HALAMAN PENGESAHAN ............................................................... iv MOTTO DAN PERSEMBAHAN .......................................................... v KATA PENGANTAR ............................................................................ vi DAFTAR ISI ......................................................................................... viii DAFTAR GAMBAR ............................................................................... x DAFTAR LAMPIRAN ........................................................................ xiii BAB 1 PENDAHULUAN 1.1 Latar Belakang .................................................................................... 1 1.2 Permasalahan....................................................................................... 2 1.3 Tujuan Penelitian ................................................................................ 3 1.4 Manfaat Penelitian .............................................................................. 3 1.5 Batasan Masalah.................................................................................. 4 1.6 Sistematika Skripsi .............................................................................. 4 BAB 2 LANDASAN TEORI 2.1 Definisi Graf........................................................................................ 6 2.2 Jenis-jenis Graf.................................................................................... 8 2.3 Penyajian Graf Dengan Matriks ........................................................ 10 2.4 Definisi Pewarnaan Titik pada Graf .................................................. 11 2.5 Pewarnaan Graf dengan Algoritma Welch dan Powell..................... 14 2.6 Aplikasi Algoritma Welch dan Powell dengan Microsoft Excel ..... 17

viii

BAB 3 METODE PENELITIAN 3.1 Identifikasi Masalah .......................................................................... 26 3.2 Perumusan Masalah .......................................................................... 26 3.3 Pemecahan Masalah .......................................................................... 27 3.4 Penarikan Simpulan .......................................................................... 27 BAB IV HASIL PENELITIAN DAN PEMBAHASAN 4.1 Diagram Alur Algoritma ................................................................... 28 4.2 Pembuatan Program .......................................................................... 30 4.3 Pengujian Program Pewarnaan Graf ................................................. 35 4.4 Pemodelan Penjadwalan Ujian Semester di Jurusan Matematika dengan Pewarnaan Graf ............................................................ 40 BAB V PENUTUP 5.1 Simpulan ........................................................................................... 50 5.2 Saran .................................................................................................. 51 DAFTAR PUSTAKA ............................................................................ 52 LAMPIRAN-LAMPIRAN

ix

DAFTAR GAMBAR

Halaman 1. Gambar 2.1. Graf G .................................................................................. 7 2. Gambar 2.2. Graf nol dengan tujuh titik .................................................. 8 3. Gambar 2.3. Graf teratur berderajat 2 ...................................................... 8 4. Gambar 2.4. Contoh – contoh graf lengkap ............................................. 9 5. Gambar 2.5. Graf K2,3 .............................................................................. 9 6. Gambar 2.6. H adalah graf bidang dari graf planar G ............................ 10 7. Gambar 2.7. Graf G dengan berbagai macam warna ............................. 12 8. Gambar 2.8. Graf Cn dengan 2 warna dan 3 warna ................................ 13 9. Gambar 2.9. Graf lengkap yang telah diwarnai ..................................... 13 10. Gambar 2.10. Graf K2,3 yang telah diwarnai .......................................... 14 11. Gambar 2.11. Graf G yang belum diwarnai ........................................... 14 12. Gambar 2.12. Graf G setelah diwarnai dengan algoritma Welch dan Powell dengan 4 warna ................................................ 15 13. Gambar 2.13. Graf G setelah diwarnai dengan algoritma Welch dan Powell dengan 3 warna ................................................ 15 14. Gambar 2.14. Graf H yang belum diwarnai ........................................... 16 15. Gambar 2.15. Graf H yang sudah diwarnai............................................ 17 16. Gambar 2.16. Lingkungan kerja Microsoft Excel 2003 ......................... 18 17. Gambar 2.17. Lingkungan kerja Microsoft Visual Basic Editor ............ 19 18. Gambar 2.18. Memunculkan tombol pada ruang kerja Ms. Excel 2007 20

x

19. Gambar 2.19. Tombol CommandButton1.............................................. 20 20. Gambar 2.20. Muncul kotak pesan ........................................................ 21 21. Gambar 2.21. Penulisan matriks ketetanggaan graf H pada lembar kerja Microsoft Excel. ............................................... 22 22. Gambar 2.22. Menuliskan derajat tiap titik ............................................ 23 23. Gambar 2.23. Matriks ketetanggaan yang sudah diurutkan berdasarkan derajat ........................................................................ 23 24. Gambar 2.24. Titik v6 dan v3 diwarnai dengan warna 1 ....................... 24 25. Gambar 2.25. titik v2 dan v4 diwarnai dengan warna 2 ........................ 24 26. Gambar 2.26. Graf H yang sudah terwarnai .......................................... 25 27. Gambar 2.27. Hasil pewarnaan graf H ................................................... 25 28. Gambar 4.1. Diagram alur algoritma Welch Powell .............................. 29 29. Gambar 4.2. Sheet tampilan awal tabel mata kuliah dan NIM mahasiswa ............................................................................. 30 30. Gambar 4.3. Tampilan form "Warna Graf Waaqi" ................................ 36 31. Gambar 4.4. Tabel matriks ketetanggaan graf G ................................... 36 32. Gambar 4.5. Kotak informasi matriks sudah simetri ............................. 37 33. Gambar 4.6. Kotak informasi baris dan kolom derajat sudah terisi ....... 37 34. Gambar 4.7. Kotak informasi Matrik sudah diurutkan berdasarkan derajat ........................................................................ 37 35. Gambar 4.8. Hasil pewarnaan graf pada sheet "Laporan1" ................... 37 36. Gambar 4.9. Tabel matriks ketetanggaan graf G dengan menukar v1 dengan v5 .................................................................................. 38

xi

37. Gambar 4.10. Tabel graf G yang sudah diwarnai .................................. 38 38. Gambar 4.11. Hasil Pewarnaan graf G pada sheet "Laporan2" ............. 39 39. Gambar 4.12. Tampilan awal file daftar makul.xls setelah macro di-enable ........................................................................................ 41 40. Gambar 4.13. Tampilan sheet jadwal makul dan nim yang sudah diisi . 41 41. Gambar 4.14. Proses transformasi tabel mata kuliah ke bentuk matriks ketetanggaan, selanjutnya ditulis sebagai graf M ............. 42 42. Gambar 4.15. Hasil akhir pewarnaan graf M ......................................... 43

xii

DAFTAR LAMPIRAN

Lampiran

Halaman

1. Kode Program ........................................................................................ 53

xiii

BAB 1 PENDAHULUAN

1.1 Latar Belakang Dalam dunia pendidikan, ujian merupakan sesuatu yang sangat penting. Dengan adanya ujian, akan diketahui sejauh mana tingkat pemahaman terhadap bidang ilmu yang dikaji. Untuk tingkat SD, SMP, atau SMA, penentuan jadwal ujian tidaklah terlalu sulit, karena masing–masing siswa mendapatkan mata pelajaran yang sama. Lain halnya di universitas. Setiap mahasiswa berhak mengambil mata kuliah yang mereka inginkan, asalkan sudah mengambil mata kuliah prasyaratnya. Hal ini sangat memungkinkan bagi mahasiswa/mahasiswi mengambil beberapa mata kuliah yang bisa bertabrakan jadwal ujiannya. Petugas kantor akademik harus menentukan jadwal ujian yang tepat dan menghindari semua jadwal ujian yang bertabrakan. Bisa saja ia membuat jadwal dengan setiap mata kuliah memiliki waktu ujian yang berlainan pula, akan tetapi akan membutuhkan masa ujian yang sangat lama. Hal ini akan merugikan banyak pihak, baik dari dosen, mahasiswa, maupun seluruh karyawan universitas tersebut. Untuk itu, petugas tersebut tentu ingin membuat masa ujian sesingkat mungkin tanpa adanya tumbukan jadwal. Di jurusan Matematika Unnes, penjadwalan ujian semester dilakukan secara manual. Petugas bidang akademik langsung memberikan jadwal ujian. Mahasiswa dengan jadwal tumbukan diperkenankan untuk menghubungi petugas bidang

1

akademik. Selanjutnya petugas tersebut mengubah jadwal menjadi jadwal revisi 1 dan diumumkan kembali melalui selebaran atau web jurusan matematika. Jika masih ada laporan tumbukan dari mahasiswa, maka diadakan revisi ke 2, revisi ke 3 dan seterusnya sampai final jadwal di mana sudah tidak ada jadwal ujian yang tumbukan. Hal ini dilakukan dalam selang waktu yang relatif lama. Akan tetapi masalah ini dapat diselesaikan dengan mudah jika menggunakan pewarnaan graf. Salah satu kelebihan pewarnaan graf adalah jadwal yang ada sudah pasti tidak saling bertumbukan. Selain itu waktu yang diperlukan untuk menyusun jadwal juga jauh lebih singkat jika dibandingkan dengan cara biasa. Oleh karena itu penulis mengangkat judul Program Pewarnaan Graf untuk Pemodelan Penjadwalan Ujian Semester di Jurusan Matematika Unnes.

1.2 Permasalahan Berdasarkan uraian di atas maka diambil permasalahan: 1. Bagaimana perancangan progam komputer untuk menyelesaikan pewarnaan graf? 2. Bagaimana visualisasi masalah penjadwalan ujian semester di Jurusan Matematika Unnes dalam graf? 3. Bagaimana hasil pewarnaan graf dalam menyelesaikan masalah penentuan jadwal ujian semester di jurusan Matematika Unnes?

2

1.3 Tujuan Penelitian Tujuan penelitian ini adalah sebagai berikut. 1. Mengetahui perancangan progam komputer untuk menyelesaikan pewarnaan graf. 2. Mengetahui visualisasi masalah penjadwalan ujian semester di Jurusan Matematika Unnes dalam graf. 3. Mengetahui hasil pewarnaan graf dalam menyelesaikan masalah penentuan jadwal ujian semester di jurusan Matematika Unnes.

1.4 Manfaat Penelitian Adapun manfaat yang dapat diambil dari penelitian ini antara lain: 1. Bagi Penulis Membantu penulis dalam mengaplikasikan teori-teori tentang graf baik yang telah didapatkan di perkuliahan maupun ilmu baru yang penulis dapatkan di luar perkuliahan. 2. Bagi Jurusan Matematika Aplikasi program pewarnaan graf yang dihasilkan dapat membantu petugas bidang akademik Jurusan Matematika serta menghemat waktu dalam menyusun jadwal ujian pada tiap semester. 3. Bagi Universitas Negeri Semarang (UNNES) Sebagai bahan bacaan dan acuan bagi mahasiswa lain serta bahan referensi bagi pihak perpustakaan tentang program pewarnaan graf dan aplikasinya dalam penjadwalan ujian.

3

1.5 Batasan Masalah Dalam skripsi ini, penulis tidak memperhatikan apakah dalam satu hari ada mahasiswa dengan mata ujian lebih dari dua.

1.6 Sistematika Skripsi Skripsi ini terdiri atas beberapa bagian yang masing-masing diuraikan sebagai berikut. (1)

Bagian awal skripsi, terdiri dari: halaman judul, surat pernyataan, abstrak, halaman pengesahan, motto dan persembahan, kata pengantar, daftar isi, daftar gambar, dan daftar lampiran.

(2)

Bagian isi merupakan bagian pokok dalam skripsi yang terdiri dari lima bab sebagai berikut. Bab 1 : Pendahuluan berisi tentang latar belakang, rumusan masalah, tujuan penulisan, manfaat penulisan, batasan masalah dan sistematika penulisan. Bab 2 : Landasan teori berisi tentang teori-teori yang mendukung dan berkaitan dengan permasalahan skripsi. Bagian ini terdiri dari Pengertian graf, pewarnaan graf, dan matriks ketetanggaan Bab 3 : Metode penelitian berisi tentang proses atau langkah penelitian. Bab ini meliputi identifikasi masalah, perumusan masalah, pemecahan masalah dan penarikan simpulan Bab 4 : Hasil dan pembahasan berisi tentang hasil penelitian dan pembahasan mengenai program pewarnaan graf dengan bantuan

4

Microsoft Excel serta penggunaannya dalam menentukan jadwal ujian semester di jurusan Matematika. Bab 5 : Penutup berisi tentang simpulan dari pembahasan dan saran-saran yang berkaitan dengan simpulan. (3)

Bagian akhir, merupakan bagian yang terdiri dari daftar pustaka yang bertujuan untuk memberikan informasi tentang semua buku sumber dan literatur lainnya yang digunakan dalam penulisan skripsi ini serta lampiran-lampiran.

5

BAB 2 LANDASAN TEORI

2.1 Definisi Graf Sebuah graf G=(V,E) adalah suatu sistem yang terdiri atas suatu himpunan objek V={v1, v2, v3, v4, v5, ... , vn} yang disebut himpunan titik dan sebuah koleksi E={e1, e2, e3, e4, e5, e6, ... en} yang merupakan koleksi sisi sedemikian hingga tiap sisi ek dikaitkan dengan suatu pasangan tak terurut (vi, vj) (Sutarno 2003:59). Titik vi, vj yang berkaitan dengan ek disebut titik-titik ujung sisi ek. Jika sebuah titik vi merupakan titik ujung dari suatu sisi ek, maka vi dan ek disebut saling berinsidensi atau titik vi terkait/menempel/insiden dengan sisi ek. Dua sisi yang tidak paralel disebut bertetangga/ajasen bila kedua sisi tersebut menempel dengan titik yang sama. Dua buah titik disebut bertetangga jika kedua titik tersebut merupakan titiktitik ujung dari sisi yang sama (Sutarno 2003:60). Loop/gelang adalah sisi yang dua titik ujungnya sama atau sisi yang terkait hanya pada satu titik. Sedangkan sisi ganda adalah dua sisi atau lebih yang terkait dengan pasangan titik yang sama. Cara menyajikan graf yang paling umum adalah dengan diagram. Titik dinyatakan dengan noktah dan sisi dinyatakan dengan kurva sederhana yang menghubungkan tiap dua titik.

6

G disebut graf sederhana, jika G tidak memuat loop dan sisi ganda. Banyak sisi yang terkait dengan titik v disebut derajat dari v, dinotasikan d(v) (Hasbullah 2008: 5-6). Sebuah jalan di graf G adalah sebuah barisan berhingga tak kosong W= v0 e1 v1 e2 v2 e3 v3 e4 v4 ... ek vk yang suku – sukunya bergantian titik dan sisi sedemikian hingga vi-1 dan vi adalah titik – titik akhir sisi ei untuk 1 < i < k. Jika semua sisi e1, e2, e3, e4, ... ek dalam jalan W berbeda, maka W disebut jejak. Jejak dengan semua titik v1, v2, v3, ... vk dalam jalan W berbeda disebut lintasan. Jalan W disebut tertutup jika titik awal dan titik akhir dari W sama. Jejak tertutup disebut sirkuit. Sirkuit dengan titik awal dan titik internalnya berlainan disebut siklus. Siklus dengan n titik dinotasikan dengan Cn (Sutarno 2003:65). Contoh: v1

v2 e2

e1

e3 e4

v6

e8

v3

e7

e9

e5 v5

e6

v4

Gambar 2.1. Graf G

G=(V,E) V={v1, v2, v3, v4, v5, v6} E={e1, e2, e3, e4, e5, e6, e7, e8, e9} Jalan: v1 v5 v6 v5 Jalan tertutup: v1 v5 v6 v5 v1 Jejak: v5 v6 v1 v5 v4 Sirkuit: v5 v6 v1 v5 v4 v3 v2 v1 v5 Siklus: v1 v5 v6 v1 Lintasan: v1 v5 v6

Pada Gambar 2.1 dapat dilihat titik v1 bertetangga dengan v2, v1 juga bertetangga dengan v5. v1 terkait dengan e8. Sisi e4 adalah loop. Sisi e7 dan e8 merupakan sisi ganda karena kedua sisi tersebut terkait dengan titik v1 dan v5. Derajat titik v5 pada Gambar 2.1 adalah 4, atau ditulis d(v5)=4.

7

2.2 Jenis – jenis graf 1. Graf Nol atau Graf Kosong Graf nol adalah graf yang tidak memiliki sisi. graf nol dengan n titik dinotasikan dengan Nn. Suatu graf boleh tidak mempunyai sisi, akan tetapi harus memuat paling sedikit satu titik. Contoh: v3

v4

v7 v6

v5

v1

v2

Gambar 2.2. Graf nol dengan tujuh titik 2. Graf Teratur Sebuah graf disebut graf teratur jika semua titiknya berderajat sama. Contoh:

Gambar 2.3. Graf teratur berderajat 2 3. Graf Lengkap G disebut graf lengkap jika setiap pasangan titik vi dan vj di G terdapat sisi yang menghubungkannya. Graf lengkap dengan n titik dinotasikan dengan Kn. Graf lengkap juga merupakan graf teratur.

8

Contoh:

K2

K3

K4 Gambar 2.4. Contoh – contoh graf lengkap

K6

4. Graf Bipartit Sebuah graf G disebut graf bipartit jika himpunan titik graf G, yaitu V(G) dapat dipartisi menjadi dua himpunan bagian X dan Y sedemikian hingga setiap sisi dari G menghubungkan sebuah titik di X dan sebuah titik di Y. Dinotasikan (X,Y) bipartit dari G. Sebagai contoh, gambar 2.3 adalah graf bipartit. Apabila G sederhana dan bipartit dengan partisi (X,Y) sedemikian hingga setiap titik di X dihubungkan dengan setiap titik di Y, maka G disebut graf bipartit lengkap, dinotasikan dengan Km,n. Contoh:

Gambar 2.5. Graf K2,3

9

5. Graf Planar Sebuah graf G disebut planar jika G dapat digambar pada bidang datar sedemikian hingga sisi – sisinya tidak ada yang saling "berpotongan" selain pada titik – titik akhir sisi – sisi tersebut. Graf planar yang digambar pada bidang sedemikian hingga tidak ada sisi – sisi yang saling berpotongan selain pada titik – titik akhir sisi – sisi tersebut disebut graf bidang (Sutarno 2003:111). Contoh: a

d

b

G

a

b

d

c

c

H Gambar 2.6. H adalah graf bidang dari graf planar G

2.3 Penyajian Graf Dengan Matriks Sebarang graf G berkorespondensi dengan suatu matriks berukuran n  n yang disebut matriks ketetanggaan dari G. Matriks ketetanggaan A(G)=[ aij ], di mana aij adalah banyak sisi yang terkait dengan pasangan titik vi dan v j . Matriks ketetanggaan graf G pada Gambar 2.1 adalah

10

0  1 0 A(G)   0 2  1 

1 0 1 0 0 0

0 1 1 1 0 0

0 0 1 0 1 0

2 0 0 1 0 1

1  0 0 . 0 1  0 

Angka-angka pada baris pertama yaitu 0, 1, 0, 0, 2, dan 1 secara berurutan menyatakan banyak sisi yang terkait antara pasangan titik-titik v1 dengan v1, v1 dengan v2, v1 dengan v3, v1 dengan v4, v1 dengan v5, dan v1 dengan v6.

2.4 Definisi Pewarnaan Titik pada Graf Pewarnaan titik pada graf adalah pemberian warna-warna pada titik-titik suatu graf sehingga tidak ada dua buah titik yang bertetangga pada graf tersebut berwarna sama (Malkawi 2008:1). Sebuah pewarnaan titik dari graf G=(V,E) adalah sebuah pemetaan F : V   di mana titik–titik yang bertetangga berwarna berbeda di N, yaitu jika uv  E , maka F (u )  F (v) (Klotz 2002:1). Sebuah graf G dapat diwarnai dengan warna yang berbeda pada tiap titiknya, akan tetapi dalam aplikasinya, pewarnaan graf dengan warna sesedikit mungkin sangat diperlukan. Jumlah minimum yang dibutuhkan oleh sebuah graf G sehingga seluruh titiknya diwarnai tanpa ada sepasang titik yang bertetangga berwarna sama disebut bilangan kromatik dari graf G, dinotasikan χ(G). Sebuah graf G disebut k – kromatik jika χ(G)=k.

11

Contoh:

B A

C

B

G

C G

A

D

D

E F Graf G dengan 7 warna

E F Graf G dengan 5 warna B

C G

A

D

E F Graf G dengan 4 warna Gambar 2.7. Graf G dengan berbagai macam warna Dari gambar 2.7. dapat dilihat graf G dapat diwarnai dengan 7 warna, 5 warna, dan 4 warna, namun tidak bisa diwarnai dengan jumlah warna kurang dari 4. Jadi bilangan kromatik graf G adalah 4, ditulis χ(G)=4. Suatu siklus dengan titik berjumlah genap mempunyai bilangan kromatik 2, sedangkan untuk siklus dengan titik berjumlah ganjil mempunyai bilangan kromatik 3 (Sutarno 2003:122-123).

12

Contoh: a

a

f

b

e

e

c

d

b

c

Graf C5 dengan 3 warna d Graf C6 dengan 2 warna Gambar 2.8. Graf Cn dengan 2 warna dan 3 warna Graf lengkap dengan n titik (Kn) mempunyai bilangan kromatik n karena setiap titik pada graf tersebut bertetangga dengan titik lain, sehingga tidak mungkin graf Kn dapat diwarnai dengan sejumlah warna yang kurang dari n. Contoh:

K2

K3

K4 Gambar 2.9. Graf lengkap yang telah diwarnai Sebuah graf bipartisi (X,Y) mempunyai bilangan kromatik 2. Titik – titik pada himpunan X tidak saling bertetangga, begitu juga pada himpnan Y. Oleh karena itu, titik – titik pada himpunan X dapat diwarnai dengan warna pertama dan titik – titik pada himpunan Y diwarnai dengan warna ke dua.

13

Contoh:

Gambar 2.10. Graf K2,3 yang telah diwarnai

2.5 Pewarnaan Graf dengan Algoritma Welch dan Powell Salah satu cara untuk mewarnai graf adalah dengan Algoritma Welch dan Powell. Kelebihan dari algoritma ini adalah algoritma ini cukup praktis dalam mewarnai graf. Kekurangannya adalah algoritma ini tidak selalu memberikan jumlah warna minimum, hanya cocok digunakan untuk graf dengan orde yang kecil. Oleh karena itu algoritma Welch-Powell hanya dapat menentukan batas atas warna (As’ad 2008). Hal ini terjadi karena pewarnaan yang diperoleh dari algoritma ini tidak tunggal. Khususnya untuk titik dengan jumlah derajat yang sama. Sebagai contoh:

Gambar 2.11. Graf G yang belum diwarnai

14

Gambar 2.12. Graf G setelah diwarnai dengan algoritma Welch dan Powell dengan 4 warna

Gambar 2.13. Graf G setelah diwarnai dengan algoritma Welch dan Powell dengan 3 warna Langkah–langkah dalam algoritma Welch dan Powell adalah sebagai berikut. 1.

Urutkan semua titik berdasarkan derajatnya, dari derajat besar ke derajat kecil.

2.

Ambil warna pertama (misalnya merah), warnai titik pertama yang sudah diurutkan. Kemudian warnai titik berikutnya yang tidak bertetangga dengan titik pertama tadi dengan warna yang masih sama (merah).

15

3.

Kemudian lanjutkan dengan warna ke dua, dan seterusnya sampai semua titik telah diberi warna. (Wijaya L. 2009: 4).

Contoh: Warnai graf H berikut ini dengan algoritma Welch dan Powell!

B

C G

A

D F

E

Gambar 2.14. Graf H yang belum diwarnai Langkah-langkahnya adalah sebagai berikut. 1.

Urutkan titik berdasarkan derajatnya dari besar ke kecil. Titik berderajat terbesar adalah F yaitu 5, kemudian titik-titik berderajat 4 adalah B, D, dan G, selanjutnya titik A berderajat 3, dan titik berderajat 2 adalah

E dan C. Sehingga urutannya adalah

F,B,D,G,A,C,E. Urutan titik B, D, dan G dapat dibolak-balik, begitu juga titik E dan C. 2.

Ambil satu warna (misalnya merah) untuk titik F. Kemudian warnai titik yang tidak bertetangga dengan F dengan warna yang sama (merah). Diperoleh titik yang tidak bertetangga dengan F adalah C. Jadi titik C berwarna merah. Urutan titik-titik yang berlum terwarnai menjadi B,D,G,A,E.

16

3.

Ambil warna ke dua (misalnya biru) untuk titik B. Titik yang tidak bertetangga dengan B adalah D dan E. Warnai titik D dengan warna biru. Karena titik D sudah berwarna biru dan E bertentangga dengan D, maka titik E tidak bisa diwarnai dengan biru. Sekarang urutan titiktitik yang belum terwarnai menjadi G,A,E

4.

Ambil warna ke tiga (misalnya kuning) untuk titik G. Dengan cara yang sama, warnai pula titik E dengan kuning. Sehingga sisanya adalah titik A diwarnai dengan warna berbeda (misalnya hitam). Jadi graf H dapat diwarnai dengan 4 warna. Artinya χ(H) = 4 atau H adalah 4 – kromatik. Hasilnya adalah sebagai berikut. B

C G

A

D F

E

Gambar 2.15. Graf H yang sudah diwarnai

2.6 Aplikasi Algoritma Welch dan Powell dengan Microsoft Excel Suatu graf dapat diwarnai secara manual untuk jumlah titik yang relatif sedikit. Akan tetapi sangat kesulitan jika jumlah titiknya banyak. Maka dari itu, penulis menggunakan bantuan komputer untuk mewarnai sebuah graf. Aplikasi yang digunakan adalah Visual Basic Application for Microsoft Excel sebagai media menerapkan algoritma Welch dan Powell. Untuk lebih jelasnya, akan disajikan pada bab Metode penelitian. Dalam sub bab ini penulis hanya

17

memberikan gambaran lingkungan kerja Microsoft Excel dan macro Visual Basic Application untuk algoritma Welch dan Powell.

3

1 4 2

Gambar 2.16. Lingkungan kerja Microsoft Excel 2003 Keterangan: 1. menu bar 2. menu command 3. toolbar 4. button Untuk memunculkan lingkungan kerja Visual Basic Editor cukuplah mudah. Cara yang digunakan pada Microsoft Excel 2003 yaitu dengan menekan Tools, Macro, Visual Basic Editor atau dengan menekan shortcut Alt+F11. Sedangkan pada Microsoft Excel 2007 dengan menekan tombol menu pada pojok kiri atas,

18

kemudian klik tombol Excel Options. Setelah tombol Popular terpilih, beri centang pada bagian Show Developer tab in the Ribbon, klik OK. Muncul tab Developer pada menu Ribbon. Klik tombol Visual Basic pada menu Ribbon Developer tersebut, atau dengan shortcut Alt+F11.

Gambar 2.17. Lingkungan kerja Microsoft Visual Basic Editor Sama seperti Visual Basic pada umumnya, lingkungan kerja Microsoft Visual Basic Editor digunakan untuk menulis kode program. Yang membedakan yaitu lingkungan kerja Microsoft Excel digunakan sebagai Formnya, atau bisa juga menambahkan form sendiri saat bekerja di lingkungan Microsoft Excel. Untuk memunculkan control toolbox, seperti button, label, text, dsb. pada Microsoft Excel 2003 caranya dengan mengeklik View, Toolbars, Control Toolbox. Sedangkan pada Microsoft Excel 2007 langsung klik insert control pada menu ribbon Developer.

19

Sebagai contoh akan dibuat program sederhana di lingkungan kerja Microsoft Excel 2007. Buat sebuah tombol CommandButton1 dengan mengeklik insert, kemudian pilih tombol pada ActiveX Control seperti gambar berikut ini.

Gambar 2.18. Memunculkan tombol pada ruang kerja Ms. Excel 2007 Setelah tombol dibuat, klik dua kali tombol CommandButton1 tersebut

Gambar 2.19. Tombol CommandButton1 Ketikkan kode program berikut ini. Private Sub CommandButton1_Click() Msgbox ”Alhamdulillaah, Berhasil!!” End Sub

20

Kembali ke jendela Microsft Excel dengan menekan tombol

atau

.

Kemudian untuk menjalankannya dengan menonaktifkan tombol design mode . Klik tombol CommandButton1. Hasilnya adalah sebagai berikut.

Gambar 2.20. Muncul kotak pesan

Berikut ini adalah algoritma Welch dan Powell yang sudah diubah dalam bentuk bahasa pemrograman. 1.

Ubah graf menjadi bentuk matriks ketetanggaan.

2.

Tulis derajat tiap titik.

3.

Urutkan titik berdasarkan derajat.

4.

Untuk i=1 sampai banyak titik, lakukan langkah 5 sampai 9.

5.

Warnai i untuk titik berderajat terbesar yang belum diwarnai.

21

6.

Daftar semua sel pada baris titik berwarna i yang tidak sama dengan 1 atau kosong (artinya titik tidak bertetangga).

7.

Untuk j=1 sampai banyak titik pada poin 6 lakukan langkah 8.

8.

Warnai titik j dengan warna i dengan syarat titik tersebut tidak bertetangga dengan titik yang sudah diwarnai dan titik tersebut belum diwarnai (sel j≠1 dan sel baris warna = "").

9.

Lakukan hal yang sama sampai semua titik terwarnai.

Berikut ini adalah contoh alur pewarnaan graf H gambar 2.11 dengan program komputer. 1. Buat matriks ketetanggaan dari graf H pada lembar kerja Microsoft Excel. Matriks ketetanggaan dari graf H adalah sebagai berikut.

Gambar 2.21. Penulisan matriks ketetanggaan graf H pada lembar kerja Microsoft Excel

22

2. Cari derajat tiap titik.

Gambar 2.22. Menuliskan derajat tiap titik 3. Urutkan titik-titik berderajat terbesar ke terkecil.

Gambar 2.23. Matriks ketetanggaan yang sudah diurutkan berdasarkan derajat 4. Warnai titik v6 dengan warna1. 5. Pada kolom v6, cari sel kosongnya, diperoleh titik v3. Warnai v3 dengan warna 1.

23

Gambar 2.24. Titik v6 dan v3 diwarnai dengan warna 1 6. Selanjutnya warnai titik v2 dengan warna 2 7. Cari sel kosong pada kolom v2, diperoleh v2, v4, dan v5. warnai v4 dengan warna 2.

Gambar 2.25. titik v2 dan v4 diwarnai dengan warna 2

24

8. Dari titik v2, v4, dan v5, cari titik yang bersama-sama kosong dengan sel yang sudah terwarnai. Karena sel (v5,v4)=1 tidak kosong, maka v5 tidak diwarnai dengan warna 2. 9. Warnai titik v7 dengan warna 3. Kemudian cari sel kosong pada kolom v7, diperoleh v7, v3, dan v5. Karena v3 sudah diwarnai dengan warna 1 dan v5 belum diwarnai, maka hanya v5 yang diwarnai dengan warna 3. 10. Terakhir, tinggal v1 yang belum terwarnai. Warnai titik v1 dengan warna 4.

Gambar 2.26. Graf H yang sudah terwarnai Diperoleh hasil pewarnaan pada sheet baru sebagai berikut.

Gambar 2.27. Hasil pewarnaan graf H

25

BAB 3 METODE PENELITIAN

3.1 Identifikasi Masalah Identifikasi masalah dimulai dengan studi pustaka. Studi pustaka yang dilakukan adalah penelaahan sumber pustaka yang relevan mengenai pewarnaan graf, khususnya algoritma Welch dan Powell. Setelah sumber pustaka terkumpul dilanjutkan dengan penelaahan isi sumber pustaka tersebut. Hasil penelaahan tersebut kemudian digunakan untuk perumusan masalah.

3.2 Perumusan Masalah Setelah menelaah sumber pustaka, langkah selanjutnya adalah merumuskan masalah, yaitu bagaimana program komputer dari algoritma tersebut, bagaimana memodelkan ujian semester di jurusan Matematika Unnes dalam bentuk graf, serta bagaimana aplikasi program komputer tersebut dalam penjadwalan ujian semester di jurusan Matematika Unnes ke dalam bentuk graf.

26

3.3 Pemecahan Masalah Metode yang dilakukan dalam penelitian ini adalah studi pustaka dan eksperimen. Hal yang dilakukan untuk memecahkan masalah di atas adalah sebagai berikut. 1.

Membuat diagram alur dari algoritma Welch dan Powell.

2.

Kemudian diagram alur tersebut diubah ke dalam bahasa pemrograman komputer.

3.

Tahap selanjutnya yaitu memodelkan penjadwalan ujian semester dengan graf.

4.

Kemudian

graf

tersebut

ditulis

dalam

bentuk

matriks

ketetanggaan. 5.

Dengan program komputer yang telah dibuat, masalah tersebut dapat diselesaikan.

3.4 Penarikan Simpulan Hasil dari pembahasan ini dituangkan dalam bentuk simpulan akhir yang menyimpulkan secara umum pemecahan masalah tersebut. Simpulan ini dijadikan sebagai hasil kajian akhir dan merupakan hasil akhir dari proses penulisan skripsi.

27

BAB 4 HASIL DAN PEMBAHASAN

3.5 Diagram Alur Algoritma Berikut ini adalah diagram alur algoritma Welch dan Powell.

mulai

Untuk i=1 sampai jumlah titik Urutkan titik berdasarkan derajat dari terbesar ke terkecil

Untuk j=1 sampai jumlah titik Apakah j=jumlah titik?

ya

tidak

Apakah titik j sudah diwarnai?

tidak Warnai titik berderajat terbesar dengan warna j; Dapat(0)=titik j

28

1

ya keluar

l=1 Untuk k=1 sampai jumlah titik Apakah sel (j,k)≠1 dan titik k belum diwarnai?

tidak

ya dapat(l)=titik k l=l+1

tidak

Apakah k=jumlah titik? ya

Untuk m=1 sampai l Apakah sel(dapat(m),k)≠1?

tidak

Sama=false Keluar sub

ya tidak Sama=true

ya Apakah m=l?

Jika sama=true maka Warnai titik (dapat(m)) dengan warna j

Gambar 4.1. Diagram alur algoritma Welch Powell

29

1

3.6 Pembuatan Program Pertama yang dilakukan adalah membuat tabel mata kuliah dan NIM mahasiswa yang mengambilnya. Berikut ini adalah tampilan program.

Gambar 4.2. Sheet tampilan awal tabel mata kuliah dan NIM mahasiswa Tabel ini selanjutnya ditransformasikan ke dalam bentuk matriks ketetanggaan graf melalui kode sebagai berikut. Dim i, j, k, l, MaksBaris, MaksBaris2, MaksKolom As Single 'mengosongkan sheet 'waaqi warna graf' 'fungsi "Kosong" berada di module Kosong 'menghitung banyak kolom For j = 1 To 1000 If Cells(1, j) = "" Then MaksKolom = j - 1 y = MsgBox("Ada " & MaksKolom & " mata kuliah." _ & Chr(13) & "Lanjut?", vbInformation + vbYesNo) If y = vbNo Then Cells(1, MaksKolom).Select End If Exit For End If Next

30

For l = 1 To MaksKolom 'menghitung banyak For i = 2 To 255 If Cells(i, l) MaksBaris2 Exit For End If Next

- 1 baris2 = "" Then = i - 1

For k = l + 1 To MaksKolom 'menghitung banyak baris makul2 For i = 2 To 255 If Cells(i, k) = "" Then MaksBaris = i - 1 Exit For End If Next For i = 1 To MaksBaris2 For j = 1 To MaksBaris If Cells(i, l) = Cells(j, k) Then ShWarnaGraf.Cells(l + 1, k + 1) = 1 ShWarnaGraf.Cells(k + 1, l + 1) = 1 GoTo a End If Next j Next i a: Next k 'menjalankan progress loading bar LblJalan.Width = (l + 1) / MaksKolom * (LblBelakang.Width) LblPersen.Caption = Format(l / MaksKolom, "0%") LblTeks.Caption = "transformasi kolom " & l & ", matakuliah " & Cells(1, l) DoEvents Next l ShWarnaGraf.Activate With FrmMenu .TxtTitik = MaksKolom .CmdOK.SetFocus End With

Lama proses transformasi tergantung dengan banyak titik. Semakin banyak titik (mata kuliah), maka waktu yang berlangsung semakin lama. Kemudian derajat tiap titik dituliskan melalui kode sebagai berikut. 'menuliskan baris derajat BarisDerajat = Titik + 2 Cells(BarisDerajat, 1) = "Drjt"

31

Cells(1, BarisDerajat) = "Drjt" i = 1 Do While i <= Titik Jml = 0 j = 1 Do While j <= Titik Jml = Cells(j + 1, i + 1) + Jml j = j + 1 Loop Cells(BarisDerajat, i + 1) = Jml Cells(i + 1, BarisDerajat) = Jml i = i + 1 Loop

Matriks tersebut diurutkan dengan kode macro sebagai berikut. 'mengurutkan matriks berdasarkan derajat Range(Cells(1, 1), Cells(BarisDerajat, BarisDerajat)).Sort _ Key1:=Cells(BarisDerajat, 1), order1:=xlDescending, header:=xlGuess _ , ordercustom:=1, MatchCase:=False, Orientation:=xlLeftToRight, _ dataoption1:=xlSortNormal Range(Cells(1, 1), Cells(BarisDerajat, BarisDerajat)).Sort _ Key1:=Cells(1, BarisDerajat), order1:=xlDescending, header:=xlGuess _ , ordercustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, _ dataoption1:=xlSortNormal

Setelah titik diurutkan berdasarkan derajat, langkah selanjutnya adalah mewarnai graf tersebut. Inilah inti dari program pewarnaan graf yang penulis buat. Berikut ini adalah kode program yang digunakan. 'menuliskan baris warna BarisWarna = Titik + 3 Cells(BarisWarna, 1) = "Wrn" Cells(BarisWarna, 1).BorderAround _ Weight:=xlThin Range(Cells(BarisWarna, 1), Cells(BarisWarna, Titik + 1)).BorderAround _ Weight:=xlMedium Warna = 1 h = 1 Do While h <= Titik If Cells(BarisWarna, h + 1) = "" Then Maks = 0 i = 1

32

Do While i <= Titik If Cells(BarisWarna, i + 1) = "" Then If Cells(BarisDerajat, i + 1) > Maks Then Maks = Cells(BarisDerajat, i + 1) KolMaks = i End If End If i = i + 1 Loop Cells(BarisWarna, KolMaks + 1) = "w" & Warna Dapat(0) = KolMaks j = 1 k = 1 Do While j <= Titik If (Cells(KolMaks + 1, j + 1) <> 1) And (Cells(BarisWarna, j + 1) = "") Then Dapat(k) = j 'Cells(10 + k, 16) = "dapat(" & k & ")=" & Dapat(k) l = 0 Do While l <= k If Cells(Dapat(l) + 1, j + 1) <> 1 Then Sama = True Else Sama = False Exit Do End If l = l + 1 Loop If Sama = True Then Cells(BarisWarna, j + 1) = "w" & Warna Else Cells(BarisWarna, j + 1) = "" End If k = k + 1 End If j = j + 1 Loop Warna = Warna + 1 End If h = h + 1 Loop Cells(BarisWarna, 1).Select

33

Selanjutnya hasil akhir pengerjaan program disajikan pada sheet baru dengan nama sheet "Laporan1", "Laporan2", "Laporan3" dst. Menggunakan kode program sebagai berikut. Warna = Warna - 1 Sheets.Add With ActiveSheet .Name = "Laporan" & Sheets.Count - 3 .Cells(1, 1) = "Alhamdulillaah berhasil!!" .Cells(2, 1) = "Daftar warna dan titiknya" For i = 1 To Warna .Cells(3, i) = "w" & i .Cells(3, i).Interior.ColorIndex = 15 .Cells(3, i).Font.Bold = True Next MaksBaris = 4 For i = 1 To Warna k = 4 For j = 1 To Titik If ShWarnaGraf.Cells(BarisWarna, j + 1) = "w" & i Then Cells(k, i) = ShWarnaGraf.Cells(1, j + 1) k = k + 1 End If If MaksBaris < k Then MaksBaris = k - 1 Next Next With Range(Cells(3, 1), Cells(MaksBaris, Warna)) .BorderAround Weight:=xlMedium .Borders(xlInsideVertical).Weight = xlThin End With .Cells(MaksBaris + 2, 1) = "Tabel transformasi titik dan mata kuliah:" DataBaris = MaksBaris + 3 .Cells(DataBaris, 1) = "titik" .Cells(DataBaris, 2) = "mata kuliah" .Cells(DataBaris, 2).ColumnWidth = 17 For i = 1 To 2 With .Cells(MaksBaris + 3, i) .Interior.ColorIndex = 15 .Font.Bold = True End With Next For i = 1 To Titik .Cells(DataBaris + i, 1) = "v" & i .Cells(DataBaris + i, 2) = ShJadwal.Cells(1, i) Next With Range(Cells(DataBaris, 1), Cells(Titik + DataBaris, 2)) .BorderAround Weight:=xlMedium .Borders(xlInsideVertical).Weight = xlThin

34

End With .Cells(DataBaris - 1, 6) = "Pengelompokan jadwal ujian:" For i = 1 To Warna .Cells(DataBaris, 5 + i) = .Cells(3, i) With .Cells(DataBaris, 5 + i) .Interior.ColorIndex = 15 .Font.Bold = True End With For j = 1 To MaksBaris For k = 1 To Titik If .Cells(j + 3, i) = .Cells(DataBaris + k, 1) Then _ .Cells(DataBaris + j, 5 + i) = .Cells(DataBaris + k, 2) Next Next Next With Range(Cells(DataBaris, 6), Cells(MaksBaris + DataBaris, Warna + 5)) .BorderAround Weight:=xlMedium .Borders(xlInsideVertical).Weight = xlThin .Columns.AutoFit End With End With

3.7 Pengujian Program Pewarnaan Graf Berikut ini akan disajikan pewarnaan graf G gambar 2.11. menggunakan program yang telah dibuat.

Gambar 2.11. Graf G yang belum diwarnai

35

Langkah pertama adalah mengubah graf G ke dalam bentuk matriks ketetanggaan pada sheet "waaqi warna graf". Masukkan banyak titik (yaitu 8) pada form "warna Graf Waaqi", posisi form secara default berada di pojok kiri atas, kemudian tekan OK.

Gambar 4.3. Tampilan form "Warna Graf Waaqi" Muncul tabel kosong. Isikan tabel tersebut dengan angka 1 untuk dua titik yang bertetangga dan biarkan tetap kosong untuk titik-titik yang tidak bertetangga. Matriks ketetanggaan graf G disajikan pada tabel berikut.

Gambar 4.4. Tabel matriks ketetanggaan graf G Kemudian dilanjutkan dengan mengeklik tombol warna. Muncul kotak informasi.

36

Gambar 4.5. Kotak informasi matriks sudah simetri Klik OK atau tekan Enter. Akan muncul beberapa kotak informasi secara berurutan, tekan yes.

Gambar 4.6. Kotak informasi baris dan kolom derajat sudah terisi

Gambar 4.7. Kotak informasi Matrik sudah diurutkan berdasarkan derajat Diperoleh hasil pada sheet "Laporan1" sebagai berikut.

Gambar 4.8. Hasil pewarnaan graf pada sheet "Laporan1"

37

Jumlah warna yang dibutuhkan sebanyak 4 warna. Hasil ini akan berbeda jika titik v1 ditukar dengan titik v5, seperti pada gambar berikut.

Gambar 4.9. Tabel matriks ketetanggaan graf G dengan menukar v1 dengan v5 Setelah dilakukan proses yang sama, diperoleh hasil pewarnaan sebagai berikut.

Gambar 4.10. Tabel graf G yang sudah diwarnai

38

Gambar 4.11. Hasil Pewarnaan graf G pada sheet "Laporan2" Gambar 4.8. dan gambar 4.11. adalah hasil pewarnaan pada graf yang sama yaitu graf G, akan tetapi hasil yang diperoleh berbeda. Tentu saja yang akan dipilih oleh pengguna program adalah dengan warna yang paling sedikit, yaitu 3 warna seperti pada gambar 4.11. Hasil ini juga membuktikan bahwa pewarnaan graf dengan algoritma Welch dan Powell tidak tunggal dan hanya memberikan batas atas warna, yaitu 4. Artinya dengan algoritma ini tidak akan diperoleh warna dengan jumlah lebih dari 4. Bahkan pada percobaan ke dua dengan menukar v1 dan v5 diperoleh 3 warna saja. Semula muncul ide dari penulis untuk menambahkan permutasi dalam program ini, yaitu dengan mendaftar semua kemungkinan urutan titik-titik yang bertetangga dengan suatu titik yang sama, khususnya jika derajat titik-titik tersebut sama. Kemudian setiap urutan tersebut diberi tanda pewarnaan. Dari pewarnaan-pewarnaan yang ada, selanjutnya dipilih pewarnaan dengan jumlah warna terkecil. Penambahan algoritma ini akan efektif apabila digunakan pada graf dengan order kecil karena banyak permutasi dari n titik adalah n!. Memang benar dengan cara ini pasti akan diperoleh jumlah warna yang paling minimal, akan tetapi jika jumlah titik-titik yang akan diwarnai semakin banyak, maka waktu yang dibutuhkan pun semakin banyak. Bayangkan jika ada 50 titik yang

39

sama-sama

bertetangga

dengan

suatu

titik

maka

akan

ada

sebanyak

3,04140932017134E+64 kemungkinan urutan titik. Untuk itu penulis hanya menggunakan algoritma Welch dan Powell yang ada tanpa menyertakan permutasi tersebut. Banyak keunggulan dari program pewarnaan graf tersebut dibandingkan dengan penjadwalan ujian semester yang dilakukan secara manual, diantaranya yaitu : 1.

Dapat dipastikan bahwa tidak akan terjadi tumbuk jadwal antara mata kuliah satu dengan mata kuliah lain.

2.

Penghematan waktu penyusunan jadwal. Dengan program komputer ini, pengguna/petugas bidang akademik tidak memerlukan waktu berhari-hari untuk melakukan revisi-revisi jadwal.

3.8 Pemodelan

Penjadwalan

Ujian

Semester

di

Jurusan

Matematika dengan Pewarnaan Graf Pertama yang dilakukan adalah mengunduh file mata kuliah beserta daftar mahasiswa yang mengambil mata kuliah tersebut dari SIKADU. Pengunduhan file ini dapat dilakukan oleh dosen ataupun mahasiswa, begitu juga petugas bidang akademik. Setelah semua file mata kuliah diunduh, langkah selanjutnya adalah melakukan copy-paste nama mata kuliah dan NIM mahasiswa yang mengambilnya ke dalam sheet jadwal makul dan NIM. Untuk mempermudah pengerjaan,

40

penulis menggunakan file “daftar makul.xls” yang sudah berisi macro. File ini berada dalam satu folder dengan file pewarnaan graf “waaqi3.xls”.

Gambar 4.12. Tampilan awal file daftar makul.xls setelah macro di-enable

Gambar 4.13. Tampilan sheet jadwal makul dan nim yang sudah diisi

41

Kemudian tekan tombol “Klik untuk lanjut” pada form Jadwal waaqi. Posisi form secara default berada di pojok kiri atas layar. Tunggu beberapa saat. Waktu menunggu menyesuaikan dengan banyak mata kuliah dan banyak mahasiswa karena komputer mengecek satu persatu pada mata kuliah apakah mahasiswa di satu mata kuliah juga berada di kolom mata kuliah lain. Hasil yang diperoleh untuk semester genap tahun akademik 2009/2010 menunjukkan waktu yang dibutuhkan untuk mentransformasikan tabel ke dalam matriks ketetanggaan selama ± 2 menit. Waktu ini juga bergantung pada kecepatan komputer yang digunakan.

Gambar 4.14. Proses transformasi tabel mata kuliah ke bentuk matriks ketetanggaan, selanjutnya ditulis sebagai graf M

42

Kemudian tekan tombol OK dilanjutkan tombol Warna pada form “Warna Graf Waaqi”. Ikuti setiap alur pada message box yang muncul. Diperoleh hasil akhir pada sheet Laporan sebagai berikut.

Gambar 4.15. Hasil akhir pewarnaan graf M Dari Gambar 4.15. diperoleh 24 warna berbeda. Diasumsikan dalam satu hari terdapat 3 mata kuliah. Jadi disimpulkan ada 8 hari yang dibutukan untuk melaksanakan ujian semester. Jika hari Jumat hanya melaksanakan 2 mata kuliah saja, maka waktu ujian semester dapat berlangsung selama 9 hari. Hasil tersebut dapat digunakan sebagai pertimbangan untuk menentukan jadwal ujian semester. Bisa jadi seorang dosen mengharuskan ujian semester dilaksanakan pada awalawal hari karena suatu hal, atau mungkin dosen tertentu menghendaki untuk melaksanakan pada hari-hari akhir dari minggu ujian. Hal-hal tersebut sangat mempengaruhi dalam pengelompokan waktu ujian. Berikut ini adalah hasil

43

pengelompokan mata kuliah yang digunakan untuk menentukan jadwal ujian semester.

Pengelompokan jadwal ujian: w1 P.M.statistika M.matek P.M.geotrans S.rancang perc. P.M.sa2 P.M.ar2

w6 M.statistika P.M.metnum S.prokom1 M.arw

w2 P.M.kimia P.M.database-2 M.komstat

w7 M.alel2 P.M.tekur1 M.RO1

w3 M.kalkulus2 P.M.kalkulus2 M.geotrans

w8 M.prokom1 P.M.geoan M.anfung S.aduh

w9 P.M.prokom2-23 M.ekonometrika P.M.geononeuclid

w11 w12 P.M.kalklanj2 P.M.peng.statmat M.pdb M.pks S.jarkom P.M.daspros2

w13 P.M.prolin M.sist dnmk M.georuang

w16 P.M.tekur3 P.M.tekur2 M.teori antrian S.kalkulus2

w18 P.M.daslitpend M.modlin M.psa2 P.M.biologi S.statmultvrt

w17 P.M.ankom P.M.prokom2-6 M.stat non par M.dpm S.peng.statmat1

w4 M.peng. Prob P.M.alel1 M.peng.statmat2

44

w5 P.M.georu M.peng. Areal P.M.prokom2-14

w10 P.M.psa1 M.tpb S.database2 P.M.workshop3

w14 P.M.database-3 P.M.database-1 M.matdis M.anreg

w19 P.M.workshop2 M.topologi M.kimia S.met.peramaln

w15 P.M.matek M.mtdsurvspl S.statistika

w20 P.M.prokom2-5 M.RO2 P.M.statpen S.ekonometrika

w21 M.kalkpeubhbyk M.nasb S.riset pasar

w22 M.aduh S.teori antrian M.pdp

w23 w24 S.b.inggris S.statinferen S.aplstat2 S.neraca nasnl

Contoh jadwal ujian semester berdasarkan hasil di atas adalah sebagai berikut. senin w1 P.M.statistika M.matek P.M.geotrans S.rancang perc. P.M.sa2 P.M.ar2

w2 P.M.kimia P.M.database-2 M.komstat

w3 M.kalkulus2 P.M.kalkulus2 M.geotrans

selasa w4 M.peng. Prob P.M.alel1 M.peng.statmat2

w5 P.M.georu M.peng. Areal P.M.prokom2-14

w6 M.statistika P.M.metnum S.prokom1 M.arw

rabu w7 M.alel2 P.M.tekur1 M.RO1

w8 M.prokom1 P.M.geoan M.anfung S.aduh

w9 P.M.prokom2-23 M.ekonometrika P.M.geononeuclid

45

kamis w10 P.M.psa1 M.tpb S.database2 P.M.workshop3

w22 M.aduh S.teori antrian M.pdp

w11 w12 P.M.kalklanj2 P.M.peng.statmat M.pdb M.pks S.jarkom P.M.daspros2

jumat w23 w24 S.b.inggris S.statinferen S.aplstat2 S.neraca nasnl

senin w13 P.M.prolin M.sist dnmk M.georuang

w14 P.M.database-3 P.M.database-1 M.matdis M.anreg

w15 P.M.matek M.mtdsurvspl S.statistika

selasa w16 P.M.tekur3 P.M.tekur2 M.teori antrian S.kalkulus2

w17 w18 P.M.ankom P.M.daslitpend P.M.prokom2-6 M.modlin M.stat non par M.psa2 M.dpm P.M.biologi S.peng.statmat1 S.statmultvrt

rabu

46

w19

w20 P.M.prokom2P.M.workshop2 5 M.topologi M.RO2 M.kimia P.M.statpen S.met.peramaln S.ekonometrika

w21 M.kalkpeubhbyk M.nasb S.riset pasar

Sedangkan jadwal ujian semester yang telah dibuat oleh petugas bidang akademik adalah sebagai berikut.

1 bindo pm.matek s.aplkstat2 m.matek

1 m.matdis m.tpb pm.daspros2 m.modlin s.database1 pm.database

1 pm.georu m.georu m.dpm s.prokom1

1 pm.pengstatmat psikologi belajar m.peng.statmat2 s.peng.statmat1

senin 2 bk m.kalkpeubhbyk s.database2

selasa 2 filsafat ilmu pm.tekur1 s.rancang percob pm.prokom2

rabu 2 pm.geononeuclid peng ilmu pendidikn m.prokom1

kamis 2 pkn m.pdp pm.prokom2

3 pm.biologi umum pm.ar2 s.metode prmln s.statinferen m.ro1

3 pm.statistika m.peng.an.real m.ekonometrika m.statistika

3 pm.kimia m.kimia m.sisdinamik s.neraca nasional

3 pm.geotrans pm.kalkulus2 m.kalkulus2 s.kalkulus2 m.geotrans pm.prokom2

47

1 m.peng.sa2 plh pm.sa2 m.ro2

1 pend.pancasila pm.prolin m.topologi m.peng.probab s.jarkom

1 m.anfung pm.alel1 s.binggris

1 pm.geoan m.komstat

1 pm.ankom

jumat 2 m.alel2 pm.tekur3 m.nasb m.arw pm.prokom2 senin 2 m.metd survy smpl s.riset pasar pm.dpm

selasa 2 m.aduh s.aduh pm.tekur2

rabu 2 pm.workshop2 s.teori antrian m.teori antrian

3 m.pdb pm.peng.sa1 s.statmultivariat

3 m.statnonpar pm.kalklanj2 pm.workshop3 s.ekonometrika

3 pm.metnum m.anreg terapan

3 m.peng.kualits stat pm.database

kamis 2 pm.stat penelitian

3

Jadwal ujian yang disusun oleh petugas bidang akademik memerlukan waktu 9 hari. Selain itu, proses penyusunan jadwal hingga diperoleh jadwal final membutuhkan waktu yang cukup lama karena adanya revisi-revisi jadwal. Revisi tersebut dilakukan setelah ada mahasiswa yang melaporkan tumbuk jadwal antara mata kuliah satu dan mata kuliah lainnya. Hal ini menunjukkan kelebihan

48

program pewarnaan graf dalam menjadwalkan ujian semester dibandingkan dengan penyusunan jadwal ujian semester yang dilakukan secara manual.

49

BAB 5 PENUTUP

3.9 Simpulan Berdasarkan pembahasan di atas dapat disimpulkan sebagai berikut. i.

Langkah-langkah yang dilakukan dalam membuat program komputer untuk menyelesaikan pewarnaan graf adalah sebagai berikut. 1.

Membuat diagram alur algoritma Welch dan Powell

2.

Mengubahnya ke dalam bahasa pemrograman VBA pada Microsoft Excel.

ii.

Penjadwalan ujian semester di Jurusan Matematika Unnes dapat divisualisasikan dalam bentuk matriks ketetanggaan graf. Mata kuliah divisualisasikan sebagai titik dan setiap titik tersebut terhubung oleh satu sisi jika ada mahasiswa yang sama yang mengambil mata kuliahmata kuliah tersebut.

iii.

Dari program komputer yang dibuat, diperoleh hasil 24 warna (periode waktu) berbeda untuk 84 mata kuliah pada semester genap tahun 2009/2010. Angka tersebut dapat dikelompokkan menjadi 8 hari karena tiap hari ada 3 warna (periode waktu).

50

3.10 Saran Dari hasil yang diperoleh, penulis memberikan saran kepada pembaca, khususnya petugas bidang akademik untuk menggunakan program pewarnaan graf yang penulis susun. Program komputer tersebut sangat membantu dalam menentukan jadwal ujian semester. Sedangkan faktor-faktor lain seperti banyak ruang kelas, kapasitas ruang kelas, dan keinginan dosen tertentu dapat menjadi pertimbangan lain dalam menyusun jadwal ujian semester tersebut. Hendaknya program pewarnaan graf tersebut dapat ditingkatkan lagi dalam hal kecepatan, ketepatan jadwal, dan kemudahan mengakses. Akan lebih baik lagi jika variabel-variabel lain seperti ruang kelas dan dosen dimasukkan pula ke dalam program tersebut.

51

DAFTAR PUSTAKA

Budiman, Hengki. 2009. Penerapan Graph Colouring untuk Merencanakan Jadwal. http://webmail.informatika.org/~rinaldi/Matdis/2006-2007/Makalah /Makalah0607-98.pdf (1 Februari 2010 21:30:58) Hasbullah, Ismail. 2008. Algoritma untuk Mengkonstruksi Pewarnaan Sisi-f pada Graf. Bandung: Institut Teknologi Bandung. Klotz, Walter. 2002. Graph Coloring Algorithms. Malkawi, Mohammad dkk. 2008. A New Exam Scheduling Algorithm Using Graph Coloring. http://www.ccis2k.org/iajit/PDF/vol.5,no.1/11-68.pdf . The International Arab Journal of Information Technology, Vol. 5, No. 1, January 2008. (21 Februari 2010 22:13:34) Sutarno, Heri, dkk. 2003. Common Textbook Matematika Diskrit. Jica: Universitas Pendidikan Indonesia. Wijaya L., Adventus. 2009. Penerapan Pewarnaan Graf dalam Penjadwalan. http://webmail.informatika.org/~rinaldi/Matdis/2009-2010/Makalah0910/ MakalahStrukdis0910-109.pdf. (1 Februari 2010).

52

Lampiran Kode program untuk workbook adalah sebagai berikut. Private Sub Workbook_NewSheet(ByVal Sh As Object) Sh.Move After:=Sheets(Sheets.Count) End Sub Private Sub Workbook_Open() ShPetunjuk.Activate End Sub

Kode program untuk sheet jadwal adalah sebagai berikut. Private Sub Worksheet_Activate() Cells.ColumnWidth = 17 FrmProses.Show End Sub Private Sub Worksheet_Deactivate() FrmProses.Hide End Sub

Kode program untuk sheet "waaqi warna graf" adalah sebagai berikut. Private Sub Worksheet_Activate() FrmMenu.Show End Sub Private Sub Worksheet_Deactivate() FrmMenu.Hide End Sub Private Sub Worksheet_SelectionChange(ByVal Target As Range) Dim i, j, a, b As Byte i = Target.Column j = Target.Row If i <= Titik + 1 And j <= Titik + 1 Then If i > 1 And j > 1 Then For a = i - 1 To i + 1 For b = j - 1 To j + 1 Cells(a, b) = Cells(b, a) Next b Next a End If End If End Sub

53

Kode program untuk Form FrmMenu (Warna Graf Waaqi) adalah sebagai berikut. Private Sub CmdAwal_Click() Kosong TxtTitik.SetFocus SendKeys "{home}+{end}" End Sub Private Sub CmdOK_Click() Dim i, j As Byte 'memeriksa apakah nilai banyak titik benar Titik = Val(TxtTitik) If Titik = 0 Then TxtTitik.SetFocus SendKeys "{home}+{end}" Exit Sub End If 'menuliskan v1, v2, ... ,vn With ShWarnaGraf i = 1 Do While i <= Titik .Cells(1, i + 1) = "v" & i .Cells(i + 1, 1) = "v" & i i = i + 1 If .Cells(Titik + 3, i) <> "" Then MsgBox "Baris warna sudah terisi!" & Chr(13) & _ "Silakan ulangi lagi", vbCritical CmdAwal_Click Exit Sub End If Loop 'memberi border Range(Cells(1, 1), Cells(1 + Titik, 1)).BorderAround _ Weight:=xlThin Range(Cells(1, 1), Cells(1, Titik + 1)).BorderAround _ Weight:=xlThin Range(Cells(1, 1), Cells(1 + Titik, Titik + 1)).BorderAround _ Weight:=xlMedium End With CmdWarna.SetFocus Cells(2, 3).Activate End Sub Private Sub CmdWarna_Click() Dim Sim, Sama As Boolean Dim BarisDerajat, Jml, BarisWarna, Maks, KolMaks, Dapat(1000), _ Warna, MaksBaris, DataBaris As Single Dim i, j, k, l As Byte

54

'memeriksa apakah nilai banyak titik benar Titik = Val(TxtTitik) If Titik = 0 Then TxtTitik.SetFocus SendKeys "{home}+{end}" Exit Sub End If 'mengecek apakah baris warna sudah ada i = 1 Do While i <= Titik If ShWarnaGraf.Cells(Titik + 3, i) <> "" Then MsgBox "Baris warna sudah terisi!" & Chr(13) & _ "Silakan ulangi lagi", vbCritical CmdAwal_Click Exit Sub End If i = i + 1 Loop 'mengecek apakah matriks sudah simetri i = 1 Do While i <= Titik j = 1 Do While j <= Titik If Cells(i + 1, j + 1) <> Cells(j + 1, i + 1) Then Sim = False MsgBox "Data belum simetri!", vbExclamation, Informasi" Cells(i + 1, j + 1).Select Exit Sub Else Sim = True End If j = j + 1 Loop i = i + 1 Loop If Sim = True Then MsgBox "Matriks sudah simetri.", vbInformation, Informasi" End If 'menuliskan baris derajat BarisDerajat = Titik + 2 Cells(BarisDerajat, 1) = "Drjt" Cells(1, BarisDerajat) = "Drjt" Cells(BarisDerajat, 1).BorderAround _ Weight:=xlThin Range(Cells(BarisDerajat, 1), Cells(BarisDerajat, 1)).BorderAround _ Weight:=xlMedium Cells(1, BarisDerajat).BorderAround _ Weight:=xlThin Range(Cells(1, BarisDerajat), Cells(Titik BarisDerajat)).BorderAround _

55

"waaqi

"waaqi

Titik

+

+

1,

Weight:=xlMedium i = 1 Do While i <= Titik Jml = 0 j = 1 Do While j <= Titik Jml = Cells(j + 1, i + 1) + Jml j = j + 1 Loop Cells(BarisDerajat, i + 1) = Jml Cells(i + 1, BarisDerajat) = Jml i = i + 1 Loop y = MsgBox("baris dan kolom derajat sudah terisi." & Chr(13) & _ "Lanjut?", vbInformation + vbYesNo) If y = vbNo Then Exit Sub 'mengurutkan matriks berdasarkan derajat Range(Cells(1, 1), Cells(BarisDerajat, BarisDerajat)).Sort _ Key1:=Cells(BarisDerajat, 1), order1:=xlDescending, header:=xlGuess _ , ordercustom:=1, MatchCase:=False, Orientation:=xlLeftToRight, _ dataoption1:=xlSortNormal Range(Cells(1, 1), Cells(BarisDerajat, BarisDerajat)).Sort _ Key1:=Cells(1, BarisDerajat), order1:=xlDescending, header:=xlGuess _ , ordercustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, _ dataoption1:=xlSortNormal y = MsgBox("matriks sudah diurutkan berdasarkan derajat." & Chr(13) & _ "Lanjut?", vbInformation + vbYesNo) If y = vbNo Then Exit Sub 'menuliskan baris warna BarisWarna = Titik + 3 Cells(BarisWarna, 1) = "Wrn" Cells(BarisWarna, 1).BorderAround _ Weight:=xlThin Range(Cells(BarisWarna, 1), Cells(BarisWarna, 1)).BorderAround _ Weight:=xlMedium Warna = 1 h = 1 Do While h <= Titik If Cells(BarisWarna, h + 1) = "" Then Maks = 0 i = 1 Do While i <= Titik If Cells(BarisWarna, i + 1) = "" Then If Cells(BarisDerajat, i + 1) > Maks Then Maks = Cells(BarisDerajat, i + 1)

56

Titik

+

KolMaks = i End If End If i = i + 1 Loop

Cells(BarisWarna, KolMaks + 1) = "w" & Warna Dapat(0) = KolMaks j = 1 k = 1 Do While j <= Titik If (Cells(KolMaks + 1, j + 1) <> 1) And (Cells(BarisWarna, j + 1) = "") Then Dapat(k) = j l = 0 Do While l <= k If Cells(Dapat(l) + 1, j + 1) <> 1 Then Sama = True Else Sama = False Exit Do End If l = l + 1 Loop If Sama = True Then Cells(BarisWarna, j + 1) = "w" & Warna Else Cells(BarisWarna, j + 1) = "" End If k = k + 1 'Else 'Cells(10 + k, 16) = "adalah " & Cells(KolMaks + 1, j + 1) _ & "." 'y = MsgBox("perhatikan!" & Chr(13) & _ "sel(" & KolMaks + 1 & "," & j + 1 & ")=1 atau kolom" _ & j + 1 & " sudah diwarnai." & Chr(13) & _ "Lanjut?", vbYesNo) 'If y = vbNo Then Exit Sub End If j = j + 1 Loop Warna = Warna + 1 End If h = h + 1

57

Loop Cells(BarisWarna, 1).Select Warna = Warna - 1 Sheets.Add With ActiveSheet .Name = "Laporan" & Sheets.Count - 3 .Cells(1, 1) = "Alhamdulillaah berhasil!! ada " & Warna & " warna" .Cells(2, 1) = "Daftar warna dan titiknya" For i = 1 To Warna .Cells(3, i) = "w" & i .Cells(3, i).Interior.ColorIndex = 15 .Cells(3, i).Font.Bold = True Next MaksBaris = 4 For i = 1 To Warna k = 4 For j = 1 To Titik If ShWarnaGraf.Cells(BarisWarna, j + 1) = "w" & i Then Cells(k, i) = ShWarnaGraf.Cells(1, j + 1) k = k + 1 End If If MaksBaris < k Then MaksBaris = k - 1 Next Next With Range(Cells(3, 1), Cells(MaksBaris, Warna)) .BorderAround Weight:=xlMedium .Borders(xlInsideVertical).Weight = xlThin End With .Cells(MaksBaris + 2, 1) = "Tabel transformasi titik dan mata kuliah:" DataBaris = MaksBaris + 3 .Cells(DataBaris, 1) = "titik" .Cells(DataBaris, 2) = "mata kuliah" .Cells(DataBaris, 2).ColumnWidth = 17 For i = 1 To 2 With .Cells(MaksBaris + 3, i) .Interior.ColorIndex = 15 .Font.Bold = True End With Next For i = 1 To Titik .Cells(DataBaris + i, 1) = "v" & i .Cells(DataBaris + i, 2) = ShJadwal.Cells(1, i) Next With Range(Cells(DataBaris, 1), Cells(Titik + DataBaris, 2)) .BorderAround Weight:=xlMedium .Borders(xlInsideVertical).Weight = xlThin End With .Cells(DataBaris - 1, 6) = "Pengelompokan jadwal ujian:"

58

For i = 1 To Warna .Cells(DataBaris, 5 + i) = With .Cells(DataBaris, 5 + .Interior.ColorIndex = .Font.Bold = True End With For j = 1 To MaksBaris For k = 1 To Titik If .Cells(j + 3, Then _ .Cells(DataBaris + k, 2) Next Next Next

.Cells(3, i) i) 15

i) = .Cells(DataBaris + k, 1) j, 5 + i) = .Cells(DataBaris +

With Range(Cells(DataBaris, 6), Cells(MaksBaris + DataBaris 3, Warna + 5)) .BorderAround Weight:=xlMedium .Borders(xlInsideVertical).Weight = xlThin .Columns.AutoFit End With End With End Sub

Kode program untuk form FrmProses (Jadwal Waaqi) adalah sebagai berikut. Private Sub CmdLanjut_Click() Dim i, j, k, l, MaksBaris, MaksBaris2, MaksKolom As Single 'mengosongkan sheet 'waaqi warna graf' 'fungsi "Kosong" berada di module Kosong 'menghitung banyak kolom For j = 1 To 1000 If Cells(1, j) = "" Then MaksKolom = j - 1 y = MsgBox("Ada " & MaksKolom & " mata kuliah." _ & Chr(13) & "Lanjut?", vbInformation + vbYesNo) If y = vbNo Then Cells(1, MaksKolom).Select End If Exit For End If Next For l = 1 To MaksKolom 'menghitung banyak For i = 2 To 255 If Cells(i, l) MaksBaris2 Exit For

- 1 baris2 = "" Then = i - 1

59

End If Next For k = l + 1 To MaksKolom 'menghitung banyak baris makul2 For i = 2 To 255 If Cells(i, k) = "" Then MaksBaris = i - 1 Exit For End If Next For i = 1 To MaksBaris2 For j = 1 To MaksBaris If Cells(i, l) = Cells(j, k) Then ShWarnaGraf.Cells(l + 1, k + 1) = 1 ShWarnaGraf.Cells(k + 1, l + 1) = 1 GoTo a End If Next j Next i a: Next k LblJalan.Width = (l + 1) / MaksKolom * (LblBelakang.Width) LblPersen.Caption = Format(l / MaksKolom, "0%") LblTeks.Caption = "transformasi kolom " & l & ", matakuliah " & Cells(1, l) DoEvents Next l ShWarnaGraf.Activate With FrmMenu .TxtTitik = MaksKolom .CmdOK.SetFocus End With End Sub Private Sub UserForm_Activate() LblJalan.Width = 0 LblPersen.Caption = "" LblTeks.Caption = "" End Sub

60

Kode program untuk module ModulWaaqi adalah sebagai berikut. Public Titik As Byte Function Kosong() With ShWarnaGraf .Cells = "" With .Cells .Borders.LineStyle = xlLineStyleNone .EntireColumn.ColumnWidth = 4 .EntireRow.RowHeight = 20 End With End With End Function

61