JURNAL TEKNIK INFORMATIKA IMPLEMENTASI ALGORITMA GREEDY UNTUK MELAKUKAN GRAPH COLORING: STUDI KASUS PETA PROPINSI JAWA TIMUR

Penulis : Ardiansyah1), Fery Sofian Efendi2), Syaifullah2), Mateus Pinto2), Pujianto2), Hendro Steven Tempake2)

Kata kunci: edge, graph coloring, vertex.

Jurnal Penelitian | JURNAL TEKNIK INFORMATIKA IMPLEMENTASI ALGORITMA GREEDY UNTUK MELAKUKAN GRAPH COLORING: STUDI KASUS PETA PROPINSI JAWA TIMUR | Teori Graf mulai dikenal pada saat seorang matematikawan berkebangsaaan Swiss, bernama Leonhard Euler, berhasil mengungkapkan Misteri Jembatan Konigsberg pada tahun 1736. Di kota Konigsberg (sekarang bernama Kalilingrad, di Uni Soviet) mengalir sebuah sungai bernama sungai Pregel. Di tengah sungai tersebut terdapat dua buah pulau. Dari kedua pulau tersebut terdapat jembatan yang menghubungi ke tepian sungai dan diantara kedua pulau. Jumlah jembatan tersebut adalah 7 buah seperti ditunjukkan pada gambar 1: 

Konon kabarnya, penduduk kota Konigsberg sering berjalan-jalan ke tempat tersebut pada hari-hari libur. Kemudian muncul suatu keinginan untuk dapat menikmati daerah tersebut dengan melalui ketujuh jambatan tepat satu kali, yakni bermula dari satu tempat (A, B, C atau D) dan kembali ke tempat semula. Mereka berusaha untuk memperoleh rute yang sesuai dengan keinginan tersebut, dengan selalu mencoba menjalaninya. Setelah mencoba berkali-kali dan karena sudah cukup lama tidak diperoleh rutenya, akhirnya penduduk tersebut mengirim surat kepada Euler. Euler dapat memecahkan masalah tersebut, yakni bahwa perjalanan / rute yang diinginkan (yakni berawal dari suatu tempat, melalui ketujuh jembatan tepat satu kali, dan kembali ke tempat semula) tidak mungkin dicapai. 

Secara singkat, dalam tulisannya, Euler menyajikan keadaan jembatan Konigsberg tersebut seperti gambar 2:

Dalam masalah di atas, daratan (tepian A dan B, serta pulau C dan D) disajikan sebagai titik dan jembatan disajikan sebagai ruas edge. Euler mengemukakan teoremanya yang mengatakan bahwa perjalanan yang diinginkan di atas (yang kemudian dikenal sebagai perjalanan Euler) akan ada apabila graf terhubung dan banyaknya edge yang datang pada setiap titik (derajat vertex) adalah genap.

Silahkan Download Disini :

JURNAL TEKNIK INFORMATIKA IMPLEMENTASI ALGORITMA GREEDY UNTUK MELAKUKAN GRAPH COLORING: STUDI KASUS PETA PROPINSI JAWA TIMUR