Membangun Spanning Tree Dan Menyelesaikan Sisi-Sisi Bermasalah Dalam Pewarnaan Graf

Amral, Amral (2008) Membangun Spanning Tree Dan Menyelesaikan Sisi-Sisi Bermasalah Dalam Pewarnaan Graf. Masters thesis, Program Pasca Sarjana Universitas Andalas.

Preview

PDF (Membangun Spanning Tree Dan Menyelesaikan Sisi-Sisi Bermasalah Dalam Pewarnaan Graf) - Supplemental Material Available under License Creative Commons Public Domain Dedication. Download (397Kb) | Preview

Abstract

Masalah utama dalam pewarnaan graf adalah bagaimana supaya semua titik-titik yang bertetangga pada graf memiliki warna yang berbeda dan jumlah warna yang digunakan seminimum mungkin. Beberapa cara pewarnaan graf sudah disusun dalam algoritma, antara lain Largest Degree Ordering (LDO), Saturation Degree Ordering (SDO), Incident Degree Ordering (IDO). Ada juga algoritma pewarnaan graf khusus untuk subgraf dan bigraf dan dalam bentuk fungsi persamaan bilangan kromatik. Akan tetapi pewarnaan dengan cara tersebut belum memberikan hasil yang terbaik. Oleh sebab itu perlu ada cara lain dalam pewarnaan graf. Berdasarkan hal di atas maka dilakukan penelitian ini. Tujuan penelitian : 1) Membangun Spanning Tree dan sebuah graf yang diberikan. 2) Menyelesaikan sisi-sisi bermasalah yang diperoleh saat membangun Spanning Tree, sehingga diperoleh graf dengan warna minimum. Penelitian ini dilakukan di jurusan Matematika Universitas Andalas, dari bulan Januari sampai Mei 2008. Proses penelitian dilakukan dalam tiga tahap, yaitu; 1) Membaca referensi di pustaka. 2) Mengakses informasi/sumber lain di internet. 3) Membahas dan menyelesaikan penelitian.

Actions (login required)

View Item