PERBANDINGAN METODE PEWARNAAN GRAF

Zulfaida, Ajeng (2025) PERBANDINGAN METODE PEWARNAAN GRAF. Other thesis, UNIVERSITAS NURUL JADID.

	Text COVER.pdf Download (1MB)
	Text BAB I.pdf Restricted to Registered users only Download (943kB)
	Text BAB II.pdf Restricted to Registered users only Download (1MB)
	Text BAB III.pdf Restricted to Registered users only Download (1MB)
	Text BAB IV.pdf Restricted to Registered users only Download (1MB)
	Text BAB V.pdf Restricted to Registered users only Download (971kB)
	Text DAPUS.pdf Download (2MB)

Abstract

Zulfaida, Ajeng. 2025. Perbandingan Metode Pewarnaan Graf. Skripsi, Program Studi Pendidikan Matematika, Fakultas Sosial dan Humaniora, Universitas Nurul Jadid Paiton Probolinggo. Pembimbing: Olief Ilmandira Ratu Farisi, S.Pd., M.Si.

Kata Kunci: Pewarnaan Graf, Algoritma Greedy, Algoritma Welch Powell, Algoritma Sequential, Bilangan Kromatik.

Pewarnaan graf merupakan salah satu cabang dari Teori Graf yang memiliki banyak penerapan dalam kehidupan sehari hari seperti penjadwalan, pengaturan lampu lalu lintas, dan pewarnaan peta. Tujuan dari pewarnaan graf adalah untuk memberikan warna pada objek graf sehingga tidak ada objek graf yang saling bertetangga memiliki warna yang sama. Telah banyak algoritma pewarnaan graf yang telah dikembangkan diantaranya algoritma Greedy, algoritma Welch Powell, algoritma Sequential, dan lainnya. Penelitian ini bertujuan untuk membandingkan beberapa algoritma pewarnaan graf guna menemukan algoritma yang paling efisien dari segi waktu komputasi dan jumlah minimum warna yang digunakan (chromatic number). Metode yang digunakan dalam penelitian ini adalah metode komparatif (study comparison) dengan parameter berupa bilangan kromatik dan waktu komputasi yang dihasilkan oleh setiap algoritma. Adapun algoritma yang dibandingkan dalam penelitian ini adalah algoritma Greedy, algoritma Welch Powell, dan algoritma Sequential. Data graf yang digunakan dalam penelitian ini diperoleh dari berbagai sumber, seperti literatur, penelitian terdahulu dan situs Kaggle.com. Data yang diperoleh direpresentasikan dalam bentuk matriks ketetanggaan guna memudahkan proses analisis serta implementasi algoritma. Ketiga algoritma tersebut akan diimplementasikan menggunakan bahasa pemrograman Python untuk memperoleh hasil berupa bilangan kromatik dan waktu komputasi yang diperlukan dari masing-masing algoritma. Validasi dalam penelitian ini dilakukan dengan cara membandingkan hasil implementasi yang telah dilakukan baik secara manual maupun secara pemrograman guna memastikan keakuratan dari hasil penelitian.

Hasil penelitian menunjukkan bahwa algoritma Greedy unggul baik dari segi waktu komputasi maupun bilangan kromatiknya, bahkan saat diterapkan pada graf yang memiliki ukuran serta order yang besar. Algoritma Welch Powell juga unggul dalam hal bilangan kromatik yang dihasilkan, namun memiliki waktu komputasi yang lebih tinggi dikarenakan pengecekan simpul yang tidak bertetangga. Sementara itu, algoritma Sequential unggul dalam waktu komputasi namun cenderung lebih banyak menghasilkan bilangan kromatik dibandingkan dua algoritma lainnya. Dengan demikian, dapat disimpulkan bahwa algoritma Greedy merupakan algoritma yang paling optimal baik dari segi waktu komputasi dan bilangan kromatik yang dihasilkan, terlepas dari ukuran serta order graf, baik kecil maupun yang besar.

Item Type:	Thesis (Other)
Subjects:	L Education > LB Theory and practice of education > LB1603 Secondary Education. High schools
Divisions:	Fakultas Sosial dan Humaniora > S1 Pendidikan Matematika
Depositing User:	Users 23 not found.
Date Deposited:	10 Jan 2026 07:53
Last Modified:	10 Jan 2026 07:53
URI:	https://repository.unuja.ac.id/id/eprint/991

Actions (login required)

View Item