## Pembandingan Kompleksitas Algoritma Pada Penyelesaian Permasalahan Graph Isomorphism
Ryan Nathan Soetandyo, Arya Yudhi Wijaya dan Rully Soelaiman Jurusan Teknik Informatika, Fakultas Masing-masing, Institut Teknologi Sepuluh Nopember (ITS)
Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia
e-mail :  rully@if.its.ac.id
Abstrak —Permasalahan  graf  isomrophism  adalah permasalahan  untuk  menentukan  apakah  2  buah  graf bersifat  isomorphic.  Kedua  graf  bisa  dikatakan isomorphic  jika  simpul  pada  graf  1  bijeksi  terhadap simpul  pada  graf  2.  Permasalahan  “ISOMORPH”  yang terdapat  pada  situs  penilaian  daring  SPOJ  akan digunakan  sebagai  masalah  yang  merepresentasikan permasalahan  graf  isomorphism.  2  macam  algoritma akan  digunakan  untuk  menyelesaikan  permasalahan tersebut. 2 algoritma tersebut adalah algoritma VF2 dan algoritma Schmidt & Druffel. Hasil uji coba menunjukkan bahwa permasalahan “ISOMORPH” bisa diselesaikan dengan waktu penyelesaian tercepat sebesar 0.0 detik dengan menggunakan memori sebesar 2.7 MB.
Kata  Kunci — Graf,  Isomorphism,  Schmidt  & Drufel , VF2

## I. PENDAHULUAN
raf  adalah  sebuah  model  yang  direpresentasikan sebagai kumpulan titik atau simpul dan beberapa grais  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 𝑓𝑎𝑠𝑡 𝑏𝑎𝑐𝑘𝑡𝑟𝑎𝑐𝑘𝑖𝑛𝑔 , dan lain lain.
Pada tugas akhir ini, akan diselesaikan permasalahan  dengan  judul  “ISOMORPH”  pada  situ penilaian  daring  SPOJ.  Pada  permasalahan  tersebut akan terdapat beberap graf yang harus dicari pasangan isomorphic-nya. Permasalahn tersebut akan diselesaikan dengan menggunakan 2 macam algoritma yaitu algoritma VF2 dan algoritma Schmidt & Druffel 𝑓𝑎𝑠𝑡 𝑏𝑎𝑐𝑘𝑡𝑟𝑎𝑐𝑘𝑖𝑛𝑔 .

## II. TINJUAN PUSTAKA

## Algoritma VF2
Algorirtma  VF2  adalah  salah  satu  algoritma  yang bisa  digunakan  untuk  menyelesaikan  permasalahan isomorphism. Algoritma ini bisa digunakan untuk graf 𝑑𝑖𝑟𝑒𝑐𝑡𝑒𝑑 dan graf undirected .
Proses  pencocokan  antara  2  graf 𝐺1  =   ( 𝑉1 , 𝐸1) dengan 𝐺2 = (𝑉2, 𝐸2) tersediir  dari  penentuan 𝑀 pemetaan  simpul 𝐺1 yang  berasosiasi  dengan  simpul 𝐺2 . 𝑀 di ekspresikan sebagai set dari susunan pasangan (n,m)  (dengan  n ∈  𝑉 1 𝑑𝑎𝑛 𝑚 ∈  𝑉 2),  dimana  setiap pasangan  tersebut  merepresentasikan  pemetaan  antara simpul 𝑛 dari 𝑉1 dengan 𝑚 dari 𝑉2 . State  Space  Representation (selanjutnya  disebut SSR)  bisa  digunakan  untuk  mendeskripsikan  proses pembandingan  graf,  jika  setiap  kedaan 𝑠 dari  proses pembandingan merepresentasikan sebagian dari solusi akhir.Sebuah  bagian  dari  solusi  pemetaan (𝑠) adalah subset dari 𝑀 .
Pada prinsipnya, solusi dari masalah pembandingan adalah dengan mencoba semua kemungkinan pemetaan.  Untuk  kemungkinan  pemetaan  di  setiap 𝑠 dari 𝑠 0  menuju  solusi  akhir  terdapat  3  kriteria  yang digunakan  untuk  mendeteksi  adanya  kemungkinan kondisi  pada  saat  ini  tidak  menghasilkan  pemetaan solusi. 3 kriteria tersebut adalah 0- look-ahead rules , 1 - look-ahead  rules dan 2 - look-ahead  rules, yang  akan dijelaskan pada Tabel 1.
1-look-ahead rules dan 2-look-ahead rules digunakan  untuk  mengurangi  jumlah  kemungkinan pemetaan. Kedua rule tersebut menggunakan kumpulan  simpul  yang  bisa  mengunjungi  simpul- simpul  di 𝑀₁(𝑠) dan 𝑀₂(𝑠) yang  dilambangkan dengan Tin1 (𝑠) dan Tin2 (𝑠) ,  serta  menggunakan kumpulan simpulan yang bisa dikunjungi oleh simpul- simpul  di 𝑀₁(𝑠) dan 𝑀₂(𝑠) yang  dilambangkan dengan Tout1 (𝑠) dan Tout2 (𝑠) ,  dan 𝑇₁ 𝑠 = Tin1 𝑠 ∪ Tout1 (𝑠) , 𝑇₂  𝑠  = Tin2 𝑠  ∪ Tout2 (𝑠) .  Gambar  1 mengilustrasikan 𝑇(𝑠) dan (𝑠) .
G
T ABEL 1. L OOK A HEAD R ULES Look Ahead Rule Kondisi
0 R_pred Jika  dan  hanya  jika  setiap
predecessor simpul 𝑛 ′ dari 𝑛 di pemetaan sementara berkorespondensi dengan predecessor simpul 𝑚 ′  dari 𝑚 dan sebaliknya.
R_succ
Jika  dan  hanya  jika  setiap successor  simpul 𝑛 ′  dari 𝑛 di pemetaan sementara berkorespondensi dengan successor simpul 𝑚 ′  dari 𝑚 dan sebaliknya.
1
R_termin
Jika  dan  hanya  jika  jumlah predecessors dan successors
dari  n  yang  merupakan  bagian dari  Tin1( 𝑠 )  sama  dengan
jumlah predecessors dan
successors dari m yang merupakan bagian dari Tin2( 𝑠 )
R_termout
Jika  dan  hanya  jika  jumlah predecessors dan successors dari  n  yang  merupakan  bagian dari Tout1 ( 𝑠 )  sama  dengan jumlah predecessors dan successors dari m yang merupakan bagian dari
Tout2 ( 𝑠 ) 2 R_new
Jika  dan  hanya  jika  jumlah predecessors dan successors dari 𝑛 yang  bukan  merupakan bagian  dari 𝑀₁ ( 𝑠 )  maupun 𝑇₁ ( 𝑠 )  sama  dengan  jumlah predecessors dan successors dari 𝑚 yang bukan  merupakan bagian  dari 𝑀₂ ( 𝑠 )  maupun 𝑇₂ ( 𝑠 )

## Schmidt & Druffel Fast Backtracking Algorithm
Douglas  &  Schmidt fast  backtracking  algorithm menggunakan distance  matrix untuk  menyelesaikan masalah  graf isomorphism . Distance  matrix adalah karakteristik  dari  sebuah  graf  yang  memberikan informasi tentang hubungan antar simpul di dalam graf tersebut. Distance  matrix 𝐷 adalah 𝑁𝑥𝑁 matrix dengan  setiap  element 𝑑 ij  merepresentasikan  panjang dari  jarak  terdekat  antara  simpul 𝑉 i dan 𝑉 j .  Jika 𝑖 = 𝑗 maka 𝑑 ij  =  0,  jika  tidak  ada path antara  2  simpul 𝑉 i dan 𝑉 j , panjangnya didefinisikan tak hingga.
Definisikan  matriks row  characteristic sebagai XR dengan  ukuran  ( 𝑁 −1),  setiap  elemen xr im adalah jumlah simpul yang memiliki jarak m dari simpul 𝑉 i . Definisikan XC sebagai matriks column characteristic dengan  ukuran  ( 𝑁 −1),  setiap  elemen xcim adalah jumlah  simpul  yang  bisa  memiliki  jarak  terpendek 𝑚 dari  simpul 𝑖 .  Matriks characteristic 𝑋 dibentuk dengan menggabungkan 𝑋𝑅 dan 𝑋𝐶 .Tabel 2(a), Tabel 2(b),  Tabel  2(c),  Tabel  2(d)  secara  berturut-turut menunjukkan  matriks distance , 𝑋𝑅 , 𝑋𝐶 dan 𝑋 dari graf  pada  Gambar  2.  Tabel  2(e),  Tabel  2(f),  Tabel 2(g),  Tabel  2(h)  secara  berturut-turut  menunjukkan
matriks distance , 𝑋𝑅 , 𝑋𝐶 dan 𝑋 dari graf pada Gambar 3.
Gambar  2  dan  Gambar  3  adalah  graf undirected yang  akan  digunakan  sebagai  ilustrasi  langkah- langkah  algoritma Schmidt  dan  Druffel  Fast Backtracking .  Karena  graf  bersifat undirected maka row  characteristic  matrix akan  sama  nilainya  dengan column characteristic matrix , hal ini bisa dilihat pada Tabel 2(b) dengan Tabel 2(c), serta Tabel 2(d) dengan Tabel 2(e).
Gambar 2. Ilustrasi Graf 1
T ABEL 2. ( A ) D ISTANCE M ATRIX G RAF 1, ( B ) R OW C HARACTERISTIC M ATRIX G RAF 1, ( C ) C OLUMN C HARACTERISTIC M ATRIX G RAF 1, ( D ) C HARACTERISTIC M ATRIX G RAF 1,( E ) D ISTANCE M ATRIX G RAF 2, ( F ) R OW C HARACTERISTIC M ATRIX G RAF 2, ( G ) C OLUMN C HARACTERISTIC M ATRIX G RAF 2, ( H ) C HARACTERISTIC
M ATRIX G RAF 2.
(a)
A  B  C  D  E  F A  0 1  2  1 1  2 B  1 0  1  2 2  1 C  2 1  0  3 3  2 D  1 2  3  0 2  3 E  1 2  3  2 0  1 F  2 1  2  3 1  0
(b) 1 2 3 4 5 A 3 2 0 0 0 B 3 2 0 0 0 C 1 2 2 0 0 D 1 2 2 0 0 E 2 2 1 0 0 F 2 2 1 0 0 (c) 1 2 3 4 5 A 3 2 0 0 0 B 3 2 0 0 0 C 1 2 2 0 0 D 1 2 2 0 0 E 2 2 1 0 0 F 2 2 1 0 0 (d) 1 2 3 4 5 A  3 3 2 2 0 0 0 0
0 0 B  3 3 2 2 0 0 0 0 0 0 C  1 1 2 2 2 2 0 0 0 0 D  1 1 2 2 2 2 0 0 0 0 E 2 2 2 2 1 1 0 0 0 0 F 2 2 2 2 1 1 0 0 0 0

## (e)
A  B  C  D  E  F A  0 1  2  3 1  2 B  1 0  1  2 2  1 C  2 1  0  3 3  2 D  3 2  3  0 2  1 E  1 2  3  2 0  1 F  2 1  2  1 1  0
(f) 1 2 3 4 5 A 2 2 1 0 0 B 3 2 0 0 0 C 1 2 2 0 0 D 1 2 2 0 0 E 2 2 1 0 0 F 3 2 0 0 0
(g) 1 2 3 4 5 A  2 2 1 0 0 B  3 2 0 0 0 C  1 2 2 0 0 D  1 2 2 0 0
(h) 1 2 3 4 5 A  2 2 2 2 1 1 0 0 0 0 B  3 3 2 2 0 0 0 0 0 0
E 2 2 1 0 0 F 3 2 0 0 0 C  1 1 2 2 2 2 0 0 0 0 D  1 1 2 2 2 2 0 0 0 0 E  2 2 2 2 1 1 0 0 0 0 F  3 3 2 2 0 0 0 0 0 0
Gambar 3. Ilustrasi Graf 2.

## III. UJI COBA DAN ANALISIS

## Uji Coba Kebenaran Algoritma VF2
Uji  kebenaran  dilakukan  dengan  membandingkan hasil keluaran dari program dengan permasalahan dan mengirimkan kode sumber program dari implementasi algoritma VF2 yang telah dibuat, pada persoalan yang bersangkutan yaitu SPOJ “ISOMORPH”.

## Gambar 4. Hasil Uji Coba Algoritma VF2  pada situs SPOJ
Kode  sumber  program  mendapatkan  umpan  balik Accepted dari situs SPOJ. Hal ini berarti keluaran kode sumber  telah  sesuai  dengan  persoalan  yang  terdapat pada  situs  SPOJ.  Waktu  tercepat  dari  pengumpulan kode  sumber  program  adalah  0,23  detik  dengan memori  maksimal  yang  dibutuhkan  program  sebesar 2,8MB.
Dilakukan  pengujian  sebanyak  20  kali  dalam  situs SPOJ  untuk  menemukan  rata-rata  waktu  program, serta  memori  yang  dibutuhkan.  Dari  pengujian sebanyak  20  kali,  waktu  yang  dibutuhkan  program minimum  0,23  detik,  maksimum  0,24  detik  dan  rata- rata  0,239  detik.  Memori  yang  dibutuhkan  program minimum  sebesar  2,7MB  dan  maksimum  sebesar 2,8MB.
Gambar 5. Grafik Hasil Uji Coba Algoritma VF2 pada situs SPOJ
Uji Coba Kebenar a n Algoritma Schmidt &

## Druffel
Uji  kebenaran  dilakukan  dengan  membandingkan hasil keluaran dari program dengan permasalahan dan mengirimkan kode sumber program dari implementasi algoritma Schmidt & Druffel  yang telah dibuat, pada persoalan yang bersangkutan yaitu SPOJ “ISOMORPH”.
Gambar 6. Hasil Uji Coba Algoritma Schmidt & Druffel pada situs SPOJ
Kode  sumber  program  mendapatkan  umpan  balik Accepted dari situs SPOJ. Hal ini berarti keluaran kode sumber  telah  sesuai  dengan  persoalan  yang  terdapat pada  situs  SPOJ.  Waktu  tercepat  dari  pengumpulan kode  sumber  program  adalah  0,00  detik  dengan memori  maksimal  yang  dibutuhkan  program  sebesar 2,8MB.
Dilakukan  pengujian  sebanyak  20  kali  dalam  situs SPOJ  untuk  menemukan  rata-rata  waktu  program, serta  memori  yang  dibutuhkan.  Dari  pengujian sebanyak  20  kali,  waktu  yang  dibutuhkan  program konstan 0,00 detik. Memori yang dibutuhkan program minimum  sebesar  2,7MB  dan  maksimum  sebesar 2,8MB.
Gambar 7. Grafik Hasil Uji Coba Algoritma Schmidt & Druffel pada situs SPOJ

## Analisa Hasil Uji Coba
Hasil  uji  coba  menunjukkan  algoritma  Schmidt  & Druffel bisa menyelesaikan permasalahan “ISOMORPH”  lebih  cepat  dibandingkan  dengan algoritma  VF2  dengan  waktu  penyelesaian  sebesar 0,00 detik dibandingkan dengan 0,23 detik.
Gambar 8. Grafik Perbandingan Hasil Uji Coba Algoritma VF2 dengan Algoritma Schmidt & Druffel
Perbedaan waktu penyelesaian permasalahan “ISOMORPH” disebabkan oleh perbedaan
kompleksitas  waktu  dari  kedua  algoritma.  Algoritma VF2  memiliki  kompleksitas  waktu  sebesar  O(N!N 2 )
sedangkan  algoritma  Schmidt  &  Druffel  memiliki kompleksitas  waktu  yang  lebih  baik  yaitu  sebesar O(KN 3 )

## IV. KESIMPULAN
Dari  hasil  ji  coba  yang  telah  dilakukan  terhadap implementasi penyelesaian
permasalahan “ISOMORPH”  dapat  diambil  kesimpulan  sebagai berikut:
1. Implementasi  algoritma  VF2  dan  Schmidt  & Druffel dapat menyelesaikan permasalahan “ISOMORPH”
2. Algoritma Schmidt & Druffel memiliki kompleksitas O(KN 3 ) yang lebih cepat dibandingkan dengan algoritma VF2 O(N!N 2 ).
3. Algoritma VF2 bisa menyelesaikan permasalahan “ISOMORPH” dengan waktu rata-rata 0.239 detik dengan  memori  maksimum  sebesar  2.8MB,  dan algoritma  Schmidt  &  Druffel  bisa  menyelesaikan permasalahan  dengan  waktu  konstan  0.0  detik dengan memori maksimum sebesar 2.8MB.

## UCAPAN TERIMA KASIH
Penulis  mengucapkan  terima  kasih  Tuhan  Yang Maha  Esa  atas  segala  karunia  dan  rahmat-Nya  yang telah diberikan selama ini.
Penulis  juga  mengucapkan  terima  kasih  kepada orang  tua,  saudara  serta  keluarga  penulis  yang  tiada henti-hentinya  memberikan  semangat,  Bapak  Arya Yudhi  Wijaya  dan  Bapak  Rully  Soelaiman  selaku dosen  pembimbing  penulis  serta  seluruh  pihak  yang tidak  bisa  penulis  sebutkan  satu  persatu  yang  telah memberikan  dukungan  selama  penulis  mengerjakan penelitian ini.

## DAFTAR PUSTAKA
[1] Douglas  C.  Schmidt,  Larry  E.  Druffel.  "A  Fast  Bactktracking Algorithm  to  Test  Directed  Graphs  for  Isomorphism  Using Distance Matrices." Journal of the Association for Computing Machinery 23, no. 3 (July 1976): 433 - 445.
[2] Jonatan  L.  Gross,  Jay  Yellen  ,  Ping  Zhang. Handbook  Of Graph Theory Second Edition. Taylor & Francis Group, 2014.
[3] L.P.Cordella,  P.Foggia,  C.Sansone,  M.Vento.  "Performance Evaluation  of  the  VF  Graph  Matching  Algorithm." IEEE , 1999: 1172-1177.
[4] Luigi  P.  Cordella,  Pasquale  Foggia,  Carlo  Sansone,  Mario Vento.  "A  (Sub)Graph  Isomorphism  Algorithm  for  Matching Large  Graphs." IEEE  Transcations  on  Pattern  Analysis  and Machine Intelligence 26, no. 10 (Oktober 2004): 1367-1372.