Program Excel Pewarnaan graf dg algoritma Welch dan Powell

Pewarnaan graf

Bismillaah..
Sebuah graf memiliki titik dan sisi.
Ada 2 macam pewarnaan dalam graf, pewarnaan titik dan pewarnaan sisi.
Yang akan dibahas dalam aplikasi ini adalah pewarnaan titik.
Pewarnaan titik adalah cara mewarnai graf sedemikian hingga untuk setiap 2 titik yang bertetangga berwarna berbeda.
Dua titik dikatakan bertetangga jika ada sebuah sisi yang menghubungkan keduanya.

Aplikasi ini dapat mewarnai graf dengan optimal, walaupun mungkin dalam kasus tertentu belum mencapai jumlah warna yang paling minimum.
Algoritma yang dipakai adalah algoritma Welch dan Powell, dengan memanfaatkan matriks ketetanggaan graf.
Sebagai contoh, matriks ketetanggaan dari graf di atas adalah sebagai berikut.

A B C D E F G A 0 1 0 0 0 1 1 B 1 0 1 1 0 1 0 C 0 1 0 0 0 0 1 G= D 0 1 0 0 1 0 0 E 0 0 0 1 0 1 1 F 1 1 0 0 1 0 0 G 1 0 1 0 1 0 0

atau dalam excel bisa ditulis seperti berikut ini.

Contoh penggunaan 'waaqi' pewarnaan graf

1, Diketahui jumlah titik pada graf G adalah 7.
Kita masukkan banyak titik (contoh: 7) ke dalam text box yang ada di form, kemudian klik ok.

2, muncul tabel matriks ketetanggaan. v1, v2, sampai v7 mewakili nama tiap titik
v1 (vertex 1) → A
v2 (vertex 2) → B
v3 (vertex 3) → C
v4 (vertex 4) → D
v5 (vertex 5) → E
v6 (vertex 6) → F
v7 (vertex 7) → G

Keterangan:
-isikan dengan 1 untuk dua titik yang bertetangga
-biarkan kosong untuk dua titik yang tidak bertetangga

secara default, jika kita mengisi sel (v1,v3), maka sel (v3,v1) juga akan terisi secara otomatis

3, tekan tombol 'Warna'. Akan muncul beberapa pesan disertai dengan perubahan pada tabel matriks ketetanggaan.
Perubahan-perubahan yang terjadi adalah sesuai dengan algoritma pewarnaan graf 'welch dan powell'. berikut ini adalah screenshotnya.

 4, hasil pewarnaan graf ada di sheet baru, yaitu di sheet 'Laporan ..'

 5, kita dapat mewarnai graf berdasarkan hasil yang sudah diperoleh.
warna 1 : v2 (titik B) dan v5 (titik E)
warna 2 : v1 (titik A), v3 (titik C), dan v4 (titik D)
warna 3 : v6 (titik F) dan v7 (titik G)

kalau masih belum bisa menjalankan macro vba, maka ikuti langkah berikut ini:

Cara mengaktifkan macro

1, klik Options… pada bar Security Warning

2, pilih enable this content, ok

Cara untuk selalu mengaktifkan macro di excel:
1, klik Excel Option pada Office button di sebelah kiri atas layar

 2, Pilih Trust Center, kemudian pilih Trust Center Setting

 

3, Pilih Enable all macros, ok, ok

 

silakan unduh filenya di sini (setelah dibuka halaman ini, klik kanan waaqi pewarnaan graf, unduh)
https://docs.google.com/file/d/0B139JQzD_9i_ZTRmYjdlZjUtYjM5NS00NGIyLTg1NmUtYzk1NGNhOGVmNTk1/edit
untuk ms.excel 2003, jika belum bisa dijalankan silakan klik tools, macro, security trus dipilih yang medium atau low.
keluar dulu.
trus kembali buka file excel nya.
semoga bermanfaat..
;)