| Juni 2024 | Volume 6 Nomor 1 | Hal. 7 – 13 DOI https://doi.org/10.30598/jmsvol6issue1pp7-13 Website: https://ojs3.unpatti.ac.id/index.php/sciencemap
ALGORITMA BRANCH AND BOUND UNTUK MENDETEKSI CLIQUE PADA KECAMATAN SYIAH KUALA KOTA BANDA ACEH
Wiwin Apriani 1* , Nurhayati 2
1 Prodi Teknik Komputer, Universitas Sains Cut Nyak Dhien
2 Prodi Pendidikan Matematika FKIP, Universitas Almuslim
Submitted: February 18,2024 Revised: April 8, 2024 Accepted: May 20, 2024 *Corresponding author. Email : wiwina10@gmail.com

## Abstrak
Kota  Banda  Aceh  merupakan  ibu  kota  provinsi  Aceh  yang  memiliki  akses  jalan  yang  sangat banyak,  baik  itu  jalan  utama  maupun  jalan-jalan  kecil  yang  menghubungkan  antar  desa (Gampong). sehingga perlu mengetahui daerah-daerah mana saja yang memiliki akses jalan yang banyak agar tidak terjadi perulangan melintasi jalan yang sama apabila ingin berpindah dari suatu daerah kedaerah lainnya. Oleh sebab itu perlu mengelompokkan daerah-daerah mana saja yang langsung  terhubung  dan  membentuk  cycle  (clique)  dan  mencari  kelompok  yang  bernilai maksimum  berdasarkan  nilai  jarak  yang  dimiliki  masing-masing  kelompok,  yang  disebuk sebagai clique maksimum. Selanjutnya dilakukan pencarian clique maksimum dimana masing- masing kelompok clique akan dicatat jumlah verteks yang saling terhubung satu sama lain dan akan  diperoleh  clique  dengan  jumlah  verteks  paling  banyak  (Maksimum).  Proses  ini  disebut sebagai  proses  bounding.  Pada  kecamatan  Syiah  Kuala  Kota  Banda  Aceh  diperoleh  clique sebanyak 3 buah yaitu 2 buah clique berukuran 4 {E, G, F, H}, {E, G, F, D}, dan 1 buah clique berukuran  3  {E,  G,  I}.  Clique  maksimum  yang  diperoleh  ialah  clique  dengan  ukur  4  dimana jumlah verteks  yang saling terhubung  ialah 4 buah verteks.  Pada penelitian  ini  juga diperoleh clique maksimal EGFD yaitu clique maksimum yang memiliki nilai bobot paling besar.
Kata Kunci : branch and bound algorithm, clique, maximal clique

## Abstract
Banda Aceh City is the capital of Aceh province which has a lot of road access, both main roads and small roads that connect between villages (Gampong). and thus it is necessary to know which areas have many road access, so there won’t be any repetition of crossing the same road if you want to move  from one area to another. Therefore, it  is necessary to classify which areas are directly connected and form a cycle (clique) and look for groups with maximum value based on the distance value owned by each group, which is called the maximum clique. Next, a maximum clique search is performed where each clique group will record the number of vertices connected to each other and the clique with the most number of vertices will be obtained (Maximum). This process  is  known as the  bounding process. In the Syiah  Kuala sub-district, Banda Aceh City, there were 3 clique namely 2 clique of size 4 {E, G, F, H}, {E, G, F, D}, and 1 clique of size 3 {E, G, I }. The maximum clique obtained is a clique of size 4 where the number of connected vertices  is  4  vertices.  In  this  study  also  obtained  the  maximum  clique  of  EGFD,  that  is  the maximum clique that has the greatest weight value.A
Keywords : branch and bound algorithm, clique, maximal clique

## Apriani & Nurhayati

## 1. Pendahuluan
Dalam kehidupan nyata banyak ditemukan permasalahan yang dapat direpresentasikan dengan titik dan garis. Permasalahan tersebut dapat direpresentasikan sebagai sebuah diagram yang terdiri atas  titik  dan  garis  yang  saling  terhubung.  Misal  pada  suatu  daerah,  andaikan  tempat direpresentasikan  sebagai  titik,  maka  jalan  yang  menghubungkan  antar  wilayah  tersebut direpresentasikan sebagai garis. Selain itu misal dalam kehidupan setiap orang memiliki hubungan saudara, baik saudara dekat maupun saudara jauh. Sehingga dalam ilmu matematika permasalahan- permasalah yang memiliki hubungan tersebut dikenal dengan istilah graf.
Andai  suatu  graf  G direpresentasikan  sebagai  suatu  masalah  yang  terdiri  dari  titik  (verteks) dan garis (edge), dimana setiap titik (vertek) saling terhubung oleh garis (edge). Sehingga pada suatu graf  terdapat  himpunan  vertkes  dan  himpunan  edge  yang  disimbolkan  dengan  (V,  E),  dimana  V adalah kumpulan verteks berhingga dan tidak kosong v1, v2, …, vn, dan E adalah kumpulan edge yang menghubungkan sekumpulan verteks tersebut e1, e2, …, en.  Dengan demikian permasalahan tersebut  dapat  dituliskan  sebagai  G  =  (V,  E).  Suatu  graf  dikatakan  mengandung  clique  jika  setiap verteks  saling  terhubung  oleh  edge  dan  membentuk  cycle,  sehingga  clique  dikatan  sebagai  subset dari graf G. Clique merupakan subgraf lengkap tak berarah yang terdiri dari dua atau lebih vertek yang  saling  terhubung  oleh  edge.  Salah  satu  permasalahan  clique  yang  sering  dibahas  yaitu permasalahan clique maksimal. Persamaan clique maksimal merupakan suatu permasalahan untuk mencari clique dengan jumlah verteks paling banyak terhubung satu sama lain oleh sebuah edge dan membentuk  cycle  dalam  suatu  graf.  Adapun  pencarian  clique  maksimum  telah  banyak  diterapkan pada bidang keilmuan seperti dalam dunia kedokteran, listrik, ekonomi, dan lain sebagainya. Pada suatu graf lengkap terdapat sedikitnya sebuah clique yang terbentuk dari dua buah verteks yang saling terhubung.  Ada  4  masalah  yang  paling  sering  dijumpai  dalam  permasalah  clique  yaitu  pencarian clique  maksimum,  pencarian  bobot  maksimum,  list  clique  maksimal,  dan  pemecahan  masalah keputusan apakah suatu graf mempunyai subgraf (clique) dengan ukuran tertentu atau tidak (Aldou dan wilson 2000).
Cavique et al, (2002) menjelaskan bahwa algoritma clique merupakan suatu algoritma yang menggabungkan pengelompokan  berdasarkan grid dan density. Selain itu menyatakan cavique et al menyelesaikan  persamaan  clique  dengan  menggunakan  algoritma  clique  dengan  menggunakan konsep pengelompokan. Selanjutnya dalam Konz (2007)  menyelesaikan permasalahan maksimum clique dengan menggunakan algoritma dasar branch and bound dan algoritma pewarnan. Sedangkan dalam Tomita dan Kameda (2007) mencari maximum clique dengan menggunakan algoritma branch and  bound  MCR  dan  menggunakan  pendekatan  pewarnaan,  selanjutnya  melakukan  percobaan komputasi  dengan  menggunakan  bahasa  pemograman  C.  Dalam  Mehotra  dan  Trick  (1998) menyebutkan bahwa permasalahan clique merupakan suatu permasalahan NP-Complete dan klasik dimana  untuk  memperoleh  penyelesaian  secara  eksak  dan  efisien  dari  setiap  permasalahan  sangat tidak  mudah,  sehingga  untuk  menyelesaikan  permasalahan  clique  dan  pengelompokan  dengan menggunakan  pendekatan  kombinatorial  coulum  generation.  Margiyani  dan  Mussafi  (2014) menjelaskan  aplikasi  algoritma  branch  and  bound  untuk  jalur  pemadaman  kebakaran  Kota Yogyakarta. Selain itu Ningsih dan Khasanah (2018) membahas aplikasi algoritma branch and bound untk merekomendasikan objek wisata di Provinsi Jawa Barat.
Kota Banda Aceh merupakan ibu kota provinsi Aceh yang memiliki akses jalan yang sangat banyak,  baik  itu  jalan  utama  maupun  jalan-jalan  kecil  yang  menghubungkan  antar  desa  atau masyarakat  Kota  Banda  Aceh  menyebutnya  sebagai  Gampong.  Oleh  sebab  itu  perlu  mengetahui daerah-daerah  mana  saja  yang  memiliki  akses  jalan  yang  banyak  dan  daerah-daerah  yang  akses jalannya terbatas. Hal ini bertujuan agar tidak terjadi perulangan melintasi jalan yang sama apabila ingin berpindah dari suatu daerah kedaerah lainnya. Sehingga perlu mengelompokkan daerah-daerah mana saja yang langsung terhubung dan membentuk cycle, dalam teori graf dikenal sebagai clique. Dengan demikian peneliti merasa tertarik untuk mengetahui daerah-daerah mana saja yang memiliki kelompok dengan nilai jarak yang paling maksimum atau disebuk sebagai clique maksimum. Dalam penelitian ini pencarian clique maksimum ialah dengan menggunakan algoritma branch and bound.

## 2. Metode Penelitian
Pada penelitian ini menggunakan salah satu Kecamatan yang ada di Kota Banda Aceh yaitu Kecamatan Syiah kuala. Kecamatan Syiah Kuala diambil secara acak dari 9 Kecamatan yang ada di Kota Banda Aceh. Kota, yaitu Meuraxa, Kuta Raja, Jaya Baru, Baiturrahman, Banda Raya, Leung Bata, Kuta Alam, Ulee Kareng, dan Syiah Kuala. Gambar 1 menunjukkan peta kota banda aceh yang diperoleh dari Kota Banda Aceh dalam angka 2020 ( https://bandaacehkota.bps.go.id/publication ).

## Gambar 1. Peta Kota Banda Aceh
Pada peta tersebut terlihat bahwa kecamatan syiah kuala terletak paling ujung kota banda aceh dan ditandai dengan warna orange. Kecamatan Syiah Kuala memiliki 10 buah gampong yaitu Deah Raya  (A),  Alue  Naga  (B),  Tibang  (C),  Jeulingke  (D),  Lamgugop  (E),  Pineung  (F),  Prada  (G),  Ie Masen Kayee Adang (H), Rukoh (I), Kopelma Darussalam (J).
Selanjutnya  untuk  proses  pengelompokan  daaerah-daerah  yang  padat  dan  yang  tidak digunakan  salah  satu  tekhnik  pengelompokan  dengan  menggubakan  algoritma  branch  and  bound. Algoritma branch and bound merupakan salah satu algoritma yang dapat digunakan untuk mencari clique dalam suatu grap lengkap. Adapun proses pencariannya dimulai dari clique yang berukuran kecil  sampai  clique  yang  berukuran  besar  sehingga  diperoleh  clique  yang  berukuran  paling  besar yang disebut Maksimum clique. Proses pencarian dengan menggunakan algoritma branch and boun, terebih dahulu menginisialisasikan Q dan Qmax. Dimana Q merupakan kumpulan (kelompok) vertex yang saling terhubung membentuk clique dan Qmax merupakan clique yang ditemukan sementara dengan  ukuran  paling  besar.  Proses  algoritma  branch  and  bound  pada  suatu  grap  lengkap  dimulai dengan mencari verteks-verteks yang saling terhubung dan membentuk clique Q. Proses ini disebut dengan  proses  brancing.  Setelah  proses  brancing  selesai,  dilakukan  perhitungan  ukuran  clique  Q yang telah detemukan pada proses brancing. Selanjutnya clique dengan verteks terbanyak yang saling terhubung dan memperoleh ukuran paling besar dicatat sebagai Qmax, dan proses ini disebut sebagai proses bounding. Diberikan graf suatu G dengan n buah verteks, dimana himpunan verteks V saling terhubung oleh sebuah edge U, akan dicari clique Q dan Qmax dalam graf G dengan menggunakan algoritma  dasar  dasar  branch  and  bound.  Penyelesaian  pencarian  clique  dan  clique  maksimum dengan aloritma branch and bound dimulai dari himpunan kosong pada Q kemudian secara bertahap akan ditambah dan dihapus vertek-vertek dari Q pada G, hingga tidak ada lagi clique dengan vertek yang berukuran lebih besar. Selanjutnya memilih verteks vi yang merupakan himpunan bagian dari V  yang  akan  ditambah  pada  clique  Q.  Pada  setiap  langkah,  akan  diambil  suatu  verteks  vi  yang merupakan anggota dari V dengan jumlah edge yang maksimal di U(v) diantara verteks-verteks pada V. pada saat verteks v terpilih, maka verteks v akan dihapus dari V. U(v) adalah upper bound untuk ukuran clique maksimum pada himpunan V. Jika jumlah dari |Q| + U(v) lebih besar dari ukuran dari Qmax, maka verteks v akan ditambahkan ke himpunan Q. β(v) merupakan himpunan semua verteks yang bertetangga dengan verteks v. Himpunan yang akan terbentuk ialah V ∩ β (v) dengan vertex- verteks yang saling terhubung dengan verteks U dan akan dijadikan parameter pada proses pencarian selanjutnya dengan prosedur MaxCique. Jika Vv = ∅ dan |Q| > |Qmax| maka vertex-verteks dari Q akan dicatat pada Qmax. Algoritma selanjutnya akan melakukan backtracking dengan menghapus v dari Q dan kemudian memilih simpul selanjutnya dari V. Prosedur ini akan terus dijalankan sampai V = ∅ . Berikut ini adalah peusedocode untuk algoritma branch and bound:
Procedure MaxClique(V,U) while V tidak sama dengan ∅ do pilih vertex vi dengan jumlah edge maksimum U(v) dari himpunan V V = V/{v} // vertek v dihapus dari V if |Q| + U(v) > |Qmax| then Q = Q ∪ {v}; if V ∩ β(v) tidak sama dengan ∅ then MaxClique(V∩ β(v), U); else if |Q| > |Qmax| then Qmax = Q; Q = Q/{v} // vertek v dihapus di Q else return end while

## 3. Hasil dan Pembahasan
Pada Kecamatan Syiah Kuala memiliki 10 buah gampong yaitu Deah Raya (A), Alue Naga (B), Tibang (C), Jeulingke (D), Lamgugop (E), Pineung (F), Prada (G), Ie Masen Kayee Adang (H), Rukoh (I), Kopelma Darussalam (J). Selanjutnya nama-nama desa tersebut dapat disajikan kedalam matriks adjacency yang berukuran n x n, dimana akan bernilai 1 jika antar desa tersebut langsung terhubung, dan bernilai 0 jika tidak langsung terhubung. Adapun matriks adjacency yang diperoleh adalah sebagai berikut:
A B C D E F G H I J A 0 1 0 0 0 0 0 0 0 0 B 1 0 1 0 0 0 0 0 0 0 C 0 1 0 1 0 0 0 0 0 0 D 0 0 1 0 1 1 1 0 0 0 E 0 0 0 1 0 1 1 1 1 0 F 0 0 0 1 1 0 1 1 0 0 G 0 0 0 1 1 1 0 1 1 0 H 0 0 0 0 1 1 1 0 0 0 I 0 0 0 0 1 0 1 0 0 1 J 0 0 0 0 0 0 0 0 1 0
Gambar 2 . Matriks adjacency berukuran 10 x 10
Berdasarkan matriks adjacency pada gambar 2 diperoleh bentuk graf sebagai berikut:
Gambar 3 . Graf nama-nama gampong pada Kecamatan Syiah Kuala

## 1. Mendeteksi Clique dengan algoritma branch and bound
Dari  graf  diatas  maka  kita  dapat  mendifinisikan  graf  G  =  (V,U),  dimana  V  merupakan himpunan vertek, V = {A, B, C, D, E, F, G, H, I, J}dan U  merupakan edge yang menghubungkan antar tiap vertex tersebut. Hal pertama yang dilakukan yaitu membuat variabel Q = {} dan Qmax = {}. Selanjutnya didefinisikan suatu himpunan U yang akan bernilai U(v) dimana v merupakan salah
satu verteks pada graf G. Himpunan U merupakan edge yang menghubungkan tiap vertek, kemudian menerapkan  metode  percabangan  pada  verteks  yang  saling  tehubung  dengan  sebuah  edge  sampai semua verteks melalui pengecekan percabangan. Selanjutnya mencari clique dan maksimum clique dengan menggunakan algoritma dasar branch and bound. Jika nilai V tidak sama dengan himpunan kosong, maka diambil verteks v dari V yang memiliki cabang maksimum. Pada gambar 1 diketahui verteks  yang  memiliki  cabang  maksimum  yaitu  verteks  E,  dan  G,  selanjutnya  dipilih  secara sembarang satu vertek yang memiliki cabang maksimum tersebut yaitu vertex E. Sehingga diambil verteks E dan akan dihapus dari himpunan V. Selanjutnya himpunan V bersisa V = {A, B, C, D, F, G, H, I, J}. Vertek E akan ditambahkan pada himpunan clique C sehingga C = {E} dan didefinisikan β(E). β(E) = {D, F, G, H, I}. sehingga diperoleh V∩ β(E) = {D, F, G, H, I} dan tidak sama dengan himpunan  kosong  maka  program  secara  rekursif  menjalankan  proses  algoritma  maxclique  dengan parameter masukan maxclique yaitu (V∩ β(E), U).
Selanjutnya, karena V∩ β(v) = {D, F, G, H, I} tidak sama dengan himpunan kosong maka verteks  G  akan  diambil  karena  memiliki  cabang  yang  maksimum  dibandingan  verteks  lainnya. Dengan demikian vertek G dihapus dari V∩ β(E) sehingga V∩ β(E) sekarang bernilai {D, F, H, I}. Kemudian  verteks  G  akan  ditambahkan  pada  himpunan  Q  sehingga  diperoleh  Q  =  {E,  G}. selanjutnya didefinisikan β(G) = {D, F, H, I}.  Sehingga diperoleh V∩ β(E) ∩ β(G) = {D, F, H, I} yang tidak sama dengan himpunan kosong maka program akam memasuki proses rekursif kembali dengan parameter masukan MaxClique (V, U) dengan V = V∩ β(E) ∩ β(G). Selanjutnya karena V∩ β(E)  ∩  β(G)  =  {D,  F,  H,  I}  tidak  sama  dengan  himpunan  kosong  maka  diambil  verteks  F  untuk dihapus  dari  (V∩  β(E)  ∩  β(G)  )  sehingga  sekarang  bernilai  {D,  H,  I}.  Kemudian  verteks  F  akan ditambah pada himpunan Q sehingga diperoleh Q = {E, G, F}. Selanjutnya didefinisikan β(F) = {D, H}. Sehingga diperoleh V∩ β(E) ∩ β(G) ∩ β(F) = {D, H} tidak sama dengan himpunan kosong maka diambil  vertex  D  atau  vertek  H  untuk  ditambahkan  pada  himpunan  Q.  Sehingga  diperoleh  clique berukuran 4 yatu Q = {E, G, F, H} dan Q = {E, G, F, D}. karena V ∩  β(H) dan  V ∩ β(D) sama dengan himpunan kosong maka program akan melanjukan ke intruksi
else if |Q| > |Qmax| then Qmax = Q;
Karena jumlah |Q| = 4 > |Qmax| = 0, maka Qmax = Q sehingga diperoleh nilai Qmax sementara bernilai Qmax = {E, G, F, H} dan Qmax = {E, G, F, D}.
Karena  X  =  {},  maka  prosedur  MaxClique  (V,  U)  berakhir  dan  beralih  kembali  pada prosedur MaxClique (V∩ β(E) ∩ β(G), U), diperoleh Q = {E, G}. karena V∩ β(E) ∩ β(G) = {D, F, H, I} tidak sama dengan himpunan kosong maka diambil verteks  I untuk dihapus dari (V∩ β(G) ∩ β(D) ) sehingga sekarang bernilai {D, F, H}.  Kemudian verteks I akan ditambah pada himpunan Q sehingga diperoleh Q = {E, G, I}. Selanjutnya didefinisikan β(I) = {J}. Selanjutnya diperoleh Clique Q berukuran 3 yaitu Q = {E, G, I}, karena V ∩ β(I) sama dengan himpunan kosong maka program akan melanjukan ke intruksi
else if |Q| > |Qmax| then Qmax = Q;
Karena  jumlah  |Q|  =  3  >  |Qmax|  =  4,  maka  Qmax  =  Q  sehingga  diperoleh  nilai  Qmax berikutnya bernilai Qmax = 4 yaitu Qmax = {E, G, F, H} dan Qmax = {E, G, F, D}. Begitu pula proses pencarian vertek-verteks untuk loop selanjutnya. Dan pada titik ini program akan kembali ke prosedur MaxClique (V, U). Begitu seterusnya sampai V mencapai himpunan kosong dimana semua himpunan V telah diperiksa.
Berdasarkan  proses  pencarian  clique  dengan  menggunakan  algoritma  dasar  branch  and bound pada gambar 3 diatas diperoleh clique sebanyak 3 buah yaitu:

## Gambar 4. Hasil pencarian Clique dari Gambar 3
Gambar 4(a) menunjukkan bahwa clique yang diperoleh yaitu {E, G, F, D} yang berarti bahwa pada gampong  Lamgugop, Prada, Pineung, dan Jeulingke membentuk  sebuah clique berukuran 4; Gambar 4(b) menunjukkan bahwa clique yang diperoleh yaitu {E, G, F, H} yang berarti bahwa pada gampong  Lamgugop,  Prada,  Pineung,  dan  Ie  Masen  Kaye  Adang  membentuk  sebuah  clique berukuran 4; dan Gambar 4(c) menunjukkan bahwa clique yang diperoleh yaitu {G, E, I} yang berarti bahwa pada gampong Prada, Lamgugop, dan Rukoh membentuk sebuah clique berukuran 3.

## 2. Mendeteksi clique maksimal pada graf berbobot
Pada permasalahan graf berbobot, proses pencarian  clique  hampir sama  seperti pada proses pencarian graf tidak berbobot. Andaikan w ij merupakan bobot pada edge (𝑖, 𝑗) ∈ U dalam suatu graf, maka  pencarian clique untuk  graf  berbobot  dapat  menggunakan  perhitungan  jarak  pada  tiap percabangan.  Pada  proses  ini  bertujuan  untuk  memperoleh clique dengan  jumlah  bobot  yang maksimum  pada  suatu  graf.    Untuk  mencari  clique  pada  graf  berbobot  proses  dilakukan  dengan menggunakan algoritma branch and bound . Misalnya pada graf gambar 3 diberi  nilai jarak antar tiap verteknya yang merupakan nilai jarak antar tiap desa dalam kecamatan syiah kuala kota Banda Aceh (Dalam satuan kilomater). Selanjutnya diperoleh graf dengan nilai bobot w ij sebagai berikut:
Gambar 5 . Graf berbobot antar tiap Gampong
Pada bagian 1 telah dijelaskan pencarian clique dengan menggunakan algoritma branch and bound dan diperoleh 3 buah clique yaitu clique berukuran 4 sebanyak 2 buah {E, G, F,  H} dan {E, G, F, D}, serta clique yang berukuran 3 yaitu {E, G, I}. Selanjunya dilakukan perhitungan nilai bobot pada  masing-masing  clique  pada  gambar  4.  Adapun  perhitungan  nilai  bobot  clique  tersebut berdasarkan jarak antar tiap verteks yang terdapat pada Gambar 5 yaitu: pada Gambar 4(a) diperoleh clique berukuran 4 yaitu {E, G, F, H} = 0,60 + 0,56 + 0,96 + 1,34 + 0,44 + 1,00 = 4,9; selanjutnya pada gambar 4(b) diperoleh clique berukuran 4 yaitu {E, G, F, D} =0,60 + 0,56 + 1,36 + 1.75 + 0,96 + 0,82 = 6,05; dan pada gambar 4(c) diperoleh clique berukuran 3 yaitu {E, G, I} = 0,69 + 1,29 + 0,60 = 2,58.
Hal  ini  menunjukkan  bahwa  clique  yang  berukuran  maksimum  akan  memiliki  bobot  yang maksimum pula. Jika terdapat 2 atau lebih clique yang berukuran maksimum,  maka dicari jumlah bobot  yang  dimiliki  masing-masing  clique  maksimum  tersebut.  Clique  maksimum  yang  memiliki bobot paling besar disebut  sebagai  clique optimum. Adapun  gampong-gampong yang membentuk clique ialah gampong Lamgugop, Prada, Pineung, dan Jeulingke dengan jumlan nilai bobot sebesar 6,05;  sedangkan  gampong  Lamgugop,  Prada,  Pineung,  dan  Ie  Masen  Kaye  Adang  memperoleh
(a)                                               (b)                                         (c)
jumlah nilai bobot sebesar 4,9; dan gampong Prada, Lamgugop, dan Rukoh memperoleh jumlah nilai bobot sebesar 2,58. Dengan demikian pada contoh graf nama-nama desa di Kecamatan Syiah Kuala Kota  banda  Aceh  diketahui  bahwa  desa  yang  membentuk  clique  yang  optimum  yaitu  Lamgugop, Prada, Pineung, dan Jeulingke.

## 4. Kesimpulan
Berdasarkan proses pencarian clique dengan menggunakan algoritma branch and bound pada peta kecamatan Syiah Kuala Kota Banda Aceh diperoleh clique sebanyak 3 buah yaitu {E, G, F, D} yang  berarti  gampong  Lamgugop,  Prada,  Pineung,  dan  Jeulingke  membentuk  clique  berukuran  4; {E,  G,  F,  H}  yang  berarti  gampong  Lamgugop,  Prada,  Pineung,  dan  Ie  Masen  Kaye  Adang membentuk clique berukuran 4; dan {G, E, I} yang berarti gampong Prada, Lamgugop, dan Rukoh membentuk sebuah clique berukuran 3. Selanjutnya pada permasalahan graf berbobot, jumlah bobot maksimum  diperoleh  pada  clique  maksimum.  Hal  ini  dikarenakan  pada  clique  maksimum mengandung jumlah verteks dan edge yang paling banyak, sehingga secara otomatis akan diperoleh bobot yang maksimum. Jika terdapat 2 atau lebih clique maksimum, maka dicari jumlah bobot dari masing-masing clique maksimum tersebut. Clique maksimum yang memiliki nilai bobot paling besar disebut clique optimum, sehingga diperoleh clique optimum yaitu Lamgugop, Prada, Pineung, dan Jeulingke.

## Daftar Pustaka
Aldous, Joan., M., and Wilson, R., J. (2000). Graph and Applications: An Introductory Approach . Great Britain: Springer.
Cavique,  L.,  Rego,  C.,and  Themido,  I.  (2002).A  Scatter  Search  Algorithm  for  Maximum  Clique Problem.  in:Essays  and  Surveys  in  Metahauristics. Jurnal  of  Computer  Science  Interfaces Series , 15, 227-244.
Konc,  J.,  and  Janezic,  D.  (2007).  An  Improved  Branch  and  Bound  Algorithm  for  the  Maximum Clique  Problem. Journal  of  Communications  in  Mathematical  and  in Computer  Chemistry , 58, 569-590.
Margiyani, S., dan Mussafi, M., S., N. (2014). Aplikasi Algoritma Branch and Bound untuk Optimasi Jalur Pemadam Kebakaran Kota Yogyakarta. Jurnal Fourier , 3 (1), 59 – 66. Mehrotra, A., and Trick, A., M. (1998).Cliques and clustering: A combinatorial approach. Journal of Elsevier : Operation Research letters ,22, 1-12.
Ningsih,  R.,  E.,  dan  Khasanah,  N.,  F.  (2018).  Rekomendasi  Objek  Wisata  Provinsi  Jawa  Barat dengan Algoritma Branch and Bound. Jurnal Penelitian Ilmu Komputer, System Embedded & Logic (Jurnal Piksel) , 6 (1), 29 – 40.
Tomita, E., and Kameda, T. (2007). An efficient branch and bound algorithm for finding a maximum clique with computational experiments. J Glob Optim, 37, 95 – 111 .