BAB III

PEMBAHASAN

Graf roda adalah graf sikel yang memiliki satu titik pusat yang semua titiknya terhubung pada

titik pusat. Sehingga untuk menemukan spaning subgraf dari graf roda, kami menetapkan titik

pusat tersebut menjadi titik awal, lalu bergerak menuju satu titik pada sikel dan bergerak

mengitari sikel, seperti yang ditunjukkan pada gambar dibawah ini :

Graf Roda Spaning Subgraf dari Graf Roda

Pembentukan spaning subgraf dalam hal ini digunakan untuk mempermudah dalam alur pewarnaan

titik. Tetapi tetap berpedoman pada graf roda dalam pewarnaan titknya.

Dalam aturan pewarnaan titik tidak memperbolehkan warna yang sama pada titik yang adjecency.

Sehingga untuk graf dengan banyaknya titik 9, titik awal (v1) diberi warna hijau, lalu dilanjutkan

untuk titik v2 sampai v9 diberi warna merah muda dan warna kuning secara bergantian, maka untuk

titik v9 mempunyai warna kuning. Dapat dilihat bahwa titik-titik pada graf roda dengan banyaknya

titik 9 yang adjecency tidak mempunyai warna yang sama, dengan warna sebanyak 3.

Lain halnya jika titik pada graf sebanyak 8, titik awal (v1) diberi warna hijau, lalu dilanjutkan untuk

titik v2 sampai v8 diberi warna merah muda dan warna kuning secara bergantian, maka untuk titik v8

mempunyai warna merah muda. Karena v8 dan v1 merupakan titik yang adjency. Maka v8 tidak

boleh berwarna kuning, maka v8 diberi warna coklat. Sehingga dilihat bahwa titik-titik pada graf roda

dengan banyaknya titik 8 yang adjecency tidak mempunyai warna yang sama, dengan warna sebanyak

4.

Dari contoh-contoh diatas dapat diperumum jika banyaknya titik pada graf roda sebanyak

genap maka warna yang dibutuhnkan sebanyak 4. Tetapi jika banyaknya titik pada graf roda

sebanyak genap maka warna yang dibutuhnkan sebanyak 3.

Untuk menerapkannya dalam matlab, maka dibutuhkan matriks untuk menggambarkan graf

tersebut. Pada matriks berikut, elemen bernilai 1 apabila 2 titik tersebut adjecen, dan bernilai

0 apabila 2 titik tersebut tdk adjecen. Berikut ini bentuk matriks adjacency dari graf roda

dengan banyaknya titik 9 dan sebanyak n.

V = V =

Dapat dilihat pada matrik V, elemen bernilai 0 pada diagonal utamanya, karena mereka tidak

adjency pada drinya sendiri. Dan bernilai 1 pada V(2,n), V(n,2) dan V(i, 1-i) untuk i ∈ n dan

pada baris dan kolom 1 kecuali pada V(1,1) dan 0 untuk yang lainnya.

Untuk pewarnaan titik, pada titik awal selalu berwarna 11, sedangkan untuk titik genap

berwarna 22, untuk titik ganjil berwarna 33. Apabila titik terakhir berwarna sama dengan titik

nomor 2, ma titik terakhir berwarna 44.

Maka dapat dituliskan dalam bentuk m-file sebagai berikut :

Maka outputnya adalah :