PENERAPAN PEWARNAAN GRAF PADA PENYUSUNAN PETA ZONASI SMA NEGERI DI KABUPATEN KARANGANYAR BERDASARKAN DATA PPDB TAHUN PELAJARAN 2022/2023 MENGGUNAKAN ALGORITMA WELCH-POWELL

Nugraha, Muhammad Rizky Ardi
Chrisnawati, Henny Ekana

Proximal: Jurnal Penelitian Matematika dan Pendidikan Matematika
Vol. 8 No. 1 (2025): Integrasi Matematika, Teknologi, dan Budaya dalam Pendidikan dan Aplikasi Terap

Abstrak. Penerimaan Peserta Didik Baru (PPDB) jalur zonasi merupakan salah satu strategi penting dalam pemerataan pendidikan di tingkat Sekolah Menengah Atas (SMA) di Indonesia. Kebijakan zonasi sekolah diyakini oleh pemerintah pusat dapat mewujudkan tantangan pemerataan kualitas pendidikan antar sekolah dan berkeadilan. Kabupaten Karanganyar menerapkan sistem ini untuk memastikan distribusi siswa berdasarkan kedekatan geografis antara tempat tinggal siswa dan sekolah. Namun, tantangan utama dalam pelaksanaan sistem zonasi adalah menentukan zona penerimaan yang optimal atau kekurangan kuota di sekolah-sekolah yang ada. Penelitian ini bertujuan untuk memodelkan dan menyelesaikan masalah zonasi pada peta PPDB SMA Negeri di Kabupaten Karanganyar menggunakan teori graf, khususnya pewarnaan graf. Algoritma Welch-Powell digunakan sebagai metode utama dalam pewarnaan graf ini. Hasil penelitian menunjukkan bahwa penerapan algoritma Welch-Powell mampu memetakan zonasi dengan warna minimum, sehingga dapat menjadi pertimbangan pemerintah daerah Kabupaten Karanganyar untuk meningkatkan pemerataan akses pendidikan di Kabupaten Karanganyar, terutama sebagai pertimbangan pembangunan Unit Sekolah Baru (USB) di wilayah-wilayah yang belum terdapat SMA Negeri.