PENDAHULUAN
Teori graph adalah topik yang berguna untuk aplikasi yang luas. Setiap Bidang ilmu dapat dikaitkan dengan graph.Algoritma yang digunakan dalam menentukan warna pada penjadwalan ujian, yaitu algoritma Welch- Powell.
Keuntungan dari algoritma Welch- Powell adalah efisien. Metode yang dipakai adalah dengan dengan pewarnaan langsung pada sebuah graph dengan warna yang sesedikit mungkin.
TEORITIS
2.1 TEORI DASAR
Teori Graph merupakan cabang ilmu matematika diskrit yang banyak penerapannya dalam berbagai bidang ilmu. Teori Graph juga dapat diaplikasikan untuk menyelesaikan persoalan-persoalan. Dalam kehidupan sehari-hari, graph digunakan untuk menggambarkan berbagai macam struktur yang ada.
Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti.
2.2 LATAR BELAKANG
Masalah jembatan Kőnigsberg (Kőnigsberg Bridge Problem) bisa menjadi contoh yang paling dekat dalam teori graph, dahulu merupakan masalah yang cukup rumit hingga pada akhirnya dipecahkan oleh Leonhard Euler, Matematikawan dari Swiss (1707-1783) tahun 1736.
Sungai Pregel membagi kota menjadi empat daratan dengan mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai, seperti tampak pada gambar 1 berikut ini :
<gambar 1>
Solusi Euler merepresentasikan masalah ini ke dalam sebuah graph dengan ke empat daratan sebagai empat vertex (node) dan ke tujuh jembatan sebagai empat sisi (edge).
<gambar 2>
2.3 JENIS-JENIS GRAPH
1. Graph sederhana (Simplegraph)
Graph yang tidak mengandung edge maupun edge ganda. Gambar 3 di bawah ini adalah contoh graph sederhana.
<Gambar 3>
2. Raph tak sederhana (Unsimple-graph)
Graph yang mengandung edge ganda atau edge. Gambar 2.10 di bawah ini adalah contoh graph tidak sederhana
<Gambar 4>
2.3 ALGORITMA WELCH-POWELL
Algoritma Welch-Powell dapat digunakan untuk mewarnai sebuah graph G secara efisien.
Algoritma Welch-Powell hanya cocok digunakan untuk graph dengan orde yang kecil. Oleh karena itu algoritma Welch-Powell hanya dapat menentukan batas atas warna. Langkah-langkahnya adalah sebagai berikut :
a. Langkah 1 (melabel titik dengan derajatnya). Label titik V1, V2, ..., Vn sedemikian hingga derajat (V1) > derajat (V2) > ... > derajat (Vn).
b. Langkah 2 (warnai titik belum berwarna pertama dari titik-titik belum berwarna yang berdekatan dengan titik itu).
Berikan warna yang belum digunakan pada titik belum berwarna yang pertama pada daftar titik itu. Lakukan hal itu pada semua titik dalam daftar secara terurut, berikan warna baru ini pada setiap titik yang tidak berdekatan dengan setiap titik lain yang telah diwarnai ini.
c. Langkah 3 (graphnya telah diwarnai?). Jika beberapa titiknya belum berwarna, maka kembalilah ke langkah 2.
d. Langkah 4 (selesai). Pewarnaan graph telah dilakukan.
Graph yang tidak mengandung edge maupun edge ganda. Gambar 3 di bawah ini adalah contoh graph sederhana.
<Gambar 3>
2. Raph tak sederhana (Unsimple-graph)
Graph yang mengandung edge ganda atau edge. Gambar 2.10 di bawah ini adalah contoh graph tidak sederhana
<Gambar 4>
2.3 ALGORITMA WELCH-POWELL
Algoritma Welch-Powell dapat digunakan untuk mewarnai sebuah graph G secara efisien.
Algoritma Welch-Powell hanya cocok digunakan untuk graph dengan orde yang kecil. Oleh karena itu algoritma Welch-Powell hanya dapat menentukan batas atas warna. Langkah-langkahnya adalah sebagai berikut :
a. Langkah 1 (melabel titik dengan derajatnya). Label titik V1, V2, ..., Vn sedemikian hingga derajat (V1) > derajat (V2) > ... > derajat (Vn).
b. Langkah 2 (warnai titik belum berwarna pertama dari titik-titik belum berwarna yang berdekatan dengan titik itu).
Berikan warna yang belum digunakan pada titik belum berwarna yang pertama pada daftar titik itu. Lakukan hal itu pada semua titik dalam daftar secara terurut, berikan warna baru ini pada setiap titik yang tidak berdekatan dengan setiap titik lain yang telah diwarnai ini.
c. Langkah 3 (graphnya telah diwarnai?). Jika beberapa titiknya belum berwarna, maka kembalilah ke langkah 2.
d. Langkah 4 (selesai). Pewarnaan graph telah dilakukan.
0 Komentar