Pembandingan Kompleksitas Algoritma pada Penyelesaian Permasalahan Graph Isomorphism

Abstract

Graf adalah sebuah model yang direpresentasikan sebagai kumpulan titik atau simpul dan beberapa garis yang menghubungkan antar titik atau yang disebut sebagai edge. Graf bisa digunakan sebagai model berbagai macam relasi dalam berbagai macam bidang seperti fisika, biologi, dan teknologi informasi. Salah satu masalah yang muncul di graf adalah masalah isomorphism.

Graf A dan graf B bisa dikatakan isomorphic jika semua simpul di graf A bisa dipetakan ke simpul di graf B secara bijeksi. Untuk bisa mengetahui apakah kedua graf bersifat isomorphic ada beberapa pilihan algoritma yang bisa digunakan seperti VF2, Schmidt & Druffel fast backtracking dan lain lain.

Pada tugas akhir ini, akan diselesaian permasalahan dengan judul “ISOMORPH” pada situs penilaian daring SPOJ. Pada permasalahan tersebut akan terdapat beberapa graf yang harus dicari pasangan isomorphic nya. Permasalahan tersebut akan diselesaikan dengan menggunakan 2 macam algoritma yaitu algoritma VF2 dan algoritma Schmidt & Druffel fast Backtracking.