SIMULASI ALGORITMA DEPTH FIRST SEARCH (DFS) PADA PEWARNAAN EDGE GRAPH

22064174, Edi Hermanson Simarmata (2013) SIMULASI ALGORITMA DEPTH FIRST SEARCH (DFS) PADA PEWARNAAN EDGE GRAPH. Bachelor thesis, Universitas Kristen Duta Wacana.

	Text (Skripsi Informatika) 22064174_Bab1_Bab5_Daftarpustaka.pdf Download (1MB)
	Text (Skripsi Informatika) 22064174_Bab2-sd-Bab4_Lampiran.pdf Restricted to Registered users only Download (2MB) | Request a copy

Abstract

Teori graph merupakan topik yang banyak mendapatkan perhatian saat ini, karena model-model yang ada pada teori graph berguna untuk aplikasi yang luas. Teori-teori mengenai graph ini telah banyak dikembangkan dengan berbagai algoritma yang memiliki kelebihan dan kelemahan masing-masing dalam menyelesaikannya. Teori pewarnaan graph merupakan salah satu objek yang menarik dan terkenal dalam bidang ilmu graph. Pewarnaan sisi graf adalah pemberian warna secara tepat pada garis sedemikian rupa sehingga setiap garis yang bertumpuan pada titik yang sama diberi warna yang berbeda. Jumlah warna minimal yang dapat digunakan untuk mewarnai sisi-sisi dalam suatu graph G disebut indeks khromatik G dinotasikan χ’(G). Jika G adalah graph sederhana yang berderajat maksimum titiknya adalah m, maka indeks kromatiknya adalah m ≤ χ’(G) ≤ m+1 (As’ad, 2008). Hasil pada penelitian ini berupa sebuah sistem untuk mengimplementasikan algoritma depth first search untuk mewarnai graph dan mencari jumlah warna minimum yang diperlukan untuk mewarnai graph yang disebut bilangan kromatik dari G. Dari percobaan-percobaan dengan menggunakan graph komplit dan graph sembarang dengan menggunakan algoritma Depht First Search, hasil yang diperoleh adalah algoritma Depth First Searh tidak menjamin hasil pewarnaan yang diperoleh sudah optimal, karena dari 58 percobaan terdapat 10 kali pewarnaan tidak optimal.

Actions (login required)

View Item