Jurnal Ilmiah Matematika dan Pendidikan Matematika (JMP) Vol. 11 No. 2, Desember 2019, hal. 29-36 ISSN (Cetak) : 2085-1456; ISSN ( Online ) : 2550-0422

## DEPTH FIRST SEARCH (DFS) UNTUK MENENTUKAN DIAMETER GRAF HIRARKI

## Nugroho Arif Sudibyo
Universitas Duta Bangsa nugroho_arif@udb.ac.id

## Ardymulya Iswardani
Universitas Duta Bangsa ardymulya@udb.ac.id
ABSTRACT. Let G = (V, E) be a graph. The distance d (u, v) between two vertices u and v is the length of the shortest path between them. The diameter of the graph is the length of the longest path of the shortest paths between any two graph vertices (u ,v) of a graph, ( )      * ( )      + .  In  this  paper  we  propose  algorithms  for  finding diameter  of  a  hierarchy  graph  using  DFS.  Diameter  of  the  hierarchy  graph  using  DFS algoritm is four.
Keywords : diameter, hierarchy, depth first search
ABSTRAK. Misalkan (    ) adalah suatu graf. Jarak (    ) di antara dua titik u dan titik  v  adalah  panjang  dari  lintasan  terpendek  di  antara  dua  titik  tersebut.  Diameter  dari suatu graf adalah lintasan terjauh terpendek di antara sembarang dua titik (    ) dari suatu graf, ( )      * ( )      + .  Dalam  makalah  ini  akan  diselidiki  tentang algoritma  untuk  menentukan  diameter  suatu  graf  hirarki  menggunakan  DFS.  Diameter Graf Hirarki yang dicari menggunakan algoritma DFS tersebut adalah empat.
Kata Kunci : diameter, hirarki, depth first search

## 1. PENDAHULUAN
Model topologi jaringan merupakan istilah untuk menunjukan konfigurasi kabel,  komputer  dan  periperal.  Pemodelan  ini  berfungsi  sebagai  pengelolaan jaringan  komputer  yang  bertujuan  untuk  memudahkan  dalam  mengenali kesalahan,  kinerja  jaringan  komputer,  keamanan  jaringan  komputer  hingga akuntabilitas  jaringan  komputer.  (CISCO,  2018;  Winkelman,  2013).  Topologi tersebut dianggap sebagai peta untuk mengenali titik apa saja yang berada dalam jaringan  komputer.  Titik  merupakan  istilah  untuk  menyebut  komputer server , komputer client maupun  perangkat  jaringan  seperti Switch HUB,  HUB, access point , router , dan lain sebagainya.
Topologi  jaringan  komputer  yang  ada  saat  ini  yaitu  bus,  bintang,  pohon, cincin, mesh hingga hybrid (Studytonight,  2019).  Setiap  topologi  memiliki karakteristik  tersendiri.  Kelebihan  dan  kekurangan  yang  dimiliki  oleh  tiap topologi  ini  yang  mendasari  pengembangan  model  topologi  dimasa  mendatang. Model topologi  jaringan  terdiri dari  titik  yang mewakili  perangkat  komputer dan jaringan  dan  lintasan  komunikasi  antar  titik.  Setiap  titik  dapat  berupa  perangkat komputer jaringan individu maupun kelompok.
Peran  topologi  sebagai  penunjuk  posisi  titiks  dalam  jaringan  komputer tersebut  dilengkapi  dengan  mekanisme  sistem  pengelolaan  jaringan  dengan membagi    jaringan  berdasarkan  hirarki/ tier /tingkat  (Kurose  &  Ross,  2008).
Pembagian  hirarki  ini  bertujuan  agar  pemetaan  kinerja  jaringan  komputer  dapat dilakukan  secara  adil/ fair .  Pembagian  ini  umumnya  dibagi  menjadi  tiga  hirarki yaitu tier1, tier2 dan tier3 . tier1 berfungsi sebagai pangkalan data atau pusat data. tier2 berfungsi  sebagai middleware yang  bertanggung  jawab  terhadap  kualitas data  yang  diterima  dari tier3 dan  kualitas  data  yang  dikirimkan  ke tier1 . tier3 berfungsi sebagai alat untuk mengumpulkan data dalam jaringan komputer lokal. Sistem manajemen jaringan dengan model hirarki ditunjukan Gambar 1.
Gambar 1.1 Model hirarki
Gambar  1.1  menunjukan  pembagian  beban  pemrosesan  pada  setiap tier . Pembagian bermodel hirarki ini untuk menunjukan peran server dan client untuk setiap tier .  Misal client pada tier3 dilayani  oleh  komputer server pada tier2 , kemudian data yang telah diperoleh dari tier3 diproses oleh komputer client pada tier2 untuk dikirimkan pada komputer server di tier1 .
Pembagian  jaringan  komputer  menjadi  tiga tier ini  bertujuan  untuk mencapai  QoS  ( Quality  of  Service )  pada  derajat  tertentu.  Kualitas  layanan  yang diberikan  untuk  setiap tier akan  bervariasi,  hal  ini  dipengaruhi  oleh  berbagai macam  faktor  seperti  spesifikasi  perangkat  yang  digunakan,  kualitas  bahan perangkat  yang  digunakan,  besar  kecilnya  volume  data,  tinggi  rendahnya  lalu lintas  data  hingga  beban  kerja  pemrosesan  setiap  tier  dan  faktor  sumberdaya manusia.  Derajat  QoS  tersebut  bertujuan  untuk  menjamin  kualitas  layanan  yang diberikan  pada  pengguna  akhir  untuk  setiap  tier  (Denko,  Yang,  et  al.,  2009). Kualitas  layanan  ini  digunakan  untuk  mengetahui  kinerja  jaringan  komputer berdasarkan feedback pengguna  jaringan  komputer  sistem  dapodik.  Istilah  titiks dan  jalur  dalam  topologi  jaringan  komputer  serupa  dengan  teori  graf.  Model topologi hirarki bertujuan untuk membagi beban kerja berdasarkan struktur hirarki yang disebut tier.
Teori  graf  sebagai  cabang  disiplin  matematika  berkembang  cepat. Penerapan  teori  graf  antar  disiplin  ilmu  sebagai  alasan  utama  pemilihan  metode. Teori  graf  telah  berkembang  cepat  sebagai  cabang  matematika,  hal  tersebut dibuktikan  dengan  banyaknya  hasil  penelitian  yang  dipublikasikan,  sebagai contoh  sudah  lebih  dari dua  ribu  makalah  sudah  diterbitkan  (Gallian,  2018).  Hal tersebut terjadi karena aplikasinya yang luas dalam berbagai masalah.
Teori graf secara formal dapat didefinisikan sebagai himpunan tak kosong berhingga V yang  disertai  relasi  yang  irrefleksif  dan  simetris.  Teori  graf  tidak hanya  suatu  kajian  teori  akan  tetapi  teori  graf  telah  diaplikasikan  pada  berbagai bidang. Sebagai contoh, jaringan interkoneksi (Kamalesh dan Srivatsa, 2008) dan eksentrisitas  dari  titik,  radius,  dan  diameter  pada  jaringan  Caccetta  dan  Vijayan (1987), Caccetta (1989) dan Caccetta (1993). Pada makalah ini diasumsikan graf tree merupakan graf yang tidak berarah.
Pada makalah ini akan dibahas model hirarki yang akan dimodelkan dalam teori  graf  supaya  dapat  ditinjau  topologinya.  Graf  hirarki adalah  suatu tree dengan himpunan titik
( )   { } Graf hirarki disajikan pada Gambar 1.2.
Gambar 1.2 Graf Hirarki
Teori  graf  menjelaskan,  untuk  mencari  suatu tree dapat  digunakan algoritma Depth-First  Search (DFS)  dan Breadth-First  Search (BFS)  (Pribadi,
2015). Algoritma tersebut adalah algoritma pencarian buta yang digunakan dalam kecerdasan  buatan  (Kandaga  dan  Hapendi,  2008).  Algoritma  DFS  diperkenalkan pertama kali oleh Tarjan dan Hopcroft. Salah satu masalah yang paling mendasar pada  teori  graf  adalah  masalah  pencarian.  Salah  satu  algoritma  yang  paling sederhana  untuk  menyelesaikan  masalah  tersebut  adalah  algoritma  DFS.  Dalam mencari  algoritma  DFS  digunakan  matrik adjacency .  Matrik adjacency adalah suatu  matrik  yang  menghubungkan  titik  dengan  titik  dengan  suatu  nilai  tertentu pada suatu graf.
𝑢 𝑣 𝑣 𝑣 𝑛 𝑣 𝑣 𝑣 𝑚 𝑣 𝑣 𝑣 𝑚 2 𝑣 𝑛 𝑣 𝑛 𝑣 𝑛 𝑚

## 2. METODOLOGI PENELITIAN
Penelitian  ini  merupakan  kajian  ilmu  murni  yang  bersifat  studi  literatur. Oleh karenanya pendekatan yang digunakan bersifat eksploratif dan adaptif yaitu memanfaatkan  pengetahuan  yang  penulis  miliki  dari  penelitian-penelitian sebelumnya.  Selain  itu  digunakan  juga  hasil-hasil  penelitian  yang  telah  ada  di literatur.  Penyelesaian  permasalahan  tersebut  dilakukan  tahapan-tahapan  sebagai berikut.
1. Studi literatur terkait penelitian.
2. Masukkan semua titik pada graf hirarki kemudian buatlah matriks adjacency .
3. Tentukan jarak terpendek dari setiap titik pada graf hirarki.
4. Tentukan eksentrisitas dari setiap titik pada graf hirarki.
5. Tentukan diameter setiap titik pada graf hirarki.

## 3. ALGORITMA UNTUK MENCARI DIAMETER
Notasi  dan  terminologi  mengacu  pada  Sudibyo  dan  Kusmayadi  (2017). Misalnya  diberikan  graf G yang  terhubung,  pasti  terdapat  suatu  lintasan  yang menghubungkan  titik v dan titik  lain  dalam .  Salah  satu  algoritma  yang  dapat mencari  diameter  adalah  algoritma  DFS.  Selanjutnya,  dalam  makalah  ini  akan dibahas  algoritma  untuk  mencari  diameter  dengan  menggunakan  DFS  mengacu pada hasil penelitian Baidari, et. al (2012).
Input: n - number of titiks
Cost[50][50]  - adjacency matrix
Output: Eccentricity, Diameter and Radius
1. Input the number of nodes and adjacency matrix
2. For i← 0 to n-1
for j←0 to n-1
D[i][j]=cost[i][j]
End j
End i
3. To find the shortest distance
for k ← 0 to n-1
for i← 0 to n-1
for j←0 to n-1
D[i][j] = min1(D[i][j],D[j][k],D[k][i])
End j End i End k
4. Initialize min and max = e [0] for i← 0 to n-1
if e[i] > max max = e[i]
else if e[i]< min min = e[i]
End i
Diameter = max .

## 4. DIAMETER DARI GRAF HIRARKI
Menentukan  diameter  pada  teori  graf  tampaknya  cukup  memakan  waktu, tetapi  akan    dibatasi  pada  kelas  graf tree .  Eksentrisitas  dari  titik x adalah     y x d x E V y , max   ,  di  mana   y x d , menunjukkan  jarak  antara x dan y , diameter G sama dengan eksentrisitas maksimum dari setiap  titik di V . Misalkan G adalah  graf  dan v adalah  simpul G .  Secara  umum,  diameter G adalah eksentrisitas  maksimum  di  antara  simpul e ,  sehingga  diperoleh  bahwa  
    V v v E G Diam   | max .
Lema 1 . Diberikan Graf  Hirarki dengan n,m ≥  2, maka diameter dari Graf Hirarki adalah empat.
Bukti .  Dengan  menggunakan  Algoritma  DFS  dapat  diketahui  jarak  terjauh  dari titik u ke titik i m i v , adalah dua  dengan *          + .  Jadi  eksentrisitas  titik u adalah  dua.  Jarak  terjauh  dari  titik i v ke  titik j m j v , ,  dengan j i  , adalah  tiga dengan *          + . Jadi eksentrisitas titik i v adalah tiga. Selanjutnya, jarak
terjauh  dari  titik i m i v , ke  titik
j m j v , ,  dengan j i  , adalah  empat  dengan
*          + . Jadi eksentrisitas titik i m i v , adalah empat. Dari eksentrisitas setiap titik dari graf hirarki tersebut, jelas bahwa eksentrisitas terbesar yang diperoleh adalah empat sebagai nilai diameter dari graf hirarki. □
Penelitian  ini  menemukan  bahwa  model  hirarki  yang  telah  dimodelkan dalam graf hirarki mempunyai diameter sebesar empat, sehingga apabila topologi jaringan  berbentuk  seperti  model  hirarki  akan  mengakibatkan  jarak  terjauh terpendek  diantara  sembarang  dua  titik  yang  terkoneksi  adalah  empat.  Namun demikian,  diperlukan  penelitian  lanjutan  terkait  topologi  jaringan  yang  lain  pada model hirarki tersebut.

## 5. KESIMPULAN
Penelitian yang telah dilakukan menemukan dan menyimpulkan beberapa hal sebagai berikut :
1. Langkah  penentuan  diameter  yaitu  dengan  menyusu  matrik  adjaceny  yang bekerja  dengan  menemukan  jarak  terpendek  dari  setiap  titik  dalam menentukan diameter pada setiap titik.
2. Diameter  dari  graf  hirarki  yang  dicari  menggunakan  algoritma  DFS  adalah empat.

## DAFTAR PUSTAKA
Baidari,  I.,  Roogi,  R.  and  Shinde,  S., Algorithmic  Approach  to  Eccentricities, Diameters  and  Radii  of  Graphs  using  DFS ,  International  Journal  of Computer Applications, 54 (18) (2012), 1-4.
Caccetta,  L. and Vijayan, K., Applications of  graph theory , ARS   Combinatoria, 23 (B) (1987), 21-77.
Caccetta,  L., Graph  theory  in  network  design  and  analysis.in    Kulli,  V.R.  (ed.). Recent Studies in Graph Theory , Vishwa International Publications, India, (1989), 26-63.
Caccetta,  L., Graph  theory  modeling  and  applications ,  in  M.  McAleer  and  A.
Jakeman,  eds.,  International  Congress  on  Modeling  and  Simulation’, Uniprint, University of Western Australia, Perth, (1993), 1265-1270
Chartarand, G. & Oellermann, O. R., Applied and Algorithmic Graph Theory , Mc Graw-Hill Inc, 1993
CISCO, Network  Management  System:  Best  Practices  White  Paper . https://www.cisco.com/c/en/us/support/docs/availability/high- availability/15114-NMS-bestpractice.html#networkmanage, 2018
Denko,  M.  K.,  Yang,  L.  T.,  &  Zhang,  Y.  (Eds.), Autonomic  Computing  and Networking , Springer, 2009.
Gallian,  J.  A., Dynamic  Survey  of  Graph  Labeling ,  The  Electronic  Journal  of Combinatorics, 21 (2018), 1-502.
Kandaga,  T.  &  Hapendi,  A., Evaluasi  dan  Usaha  Optimalisasi  Algoritma  Depth First  Search  dan  Breadth  First  Search  dengan  Penerapan  pada  Aplikasi Rat Race dan Web Peta , Jurnal Informatika , 4 (1) (2018), 39 – 47.
Kurose, J. F, & Ross, K. W., Computer networking : a top-down approach, 2008.
Pribadi,  O., Maze  Generator  Dengan  Menggunakan  Algoritma Depth-First- Search , Jurnal TIMES, 4 (1) (2015), 1-5.
Studytonight, Types of Network Topology , https://www.studytonight.com/computer-networks/network-topology- types , 2019.
Sudibyo,  N.  A.  &  Kusmayadi,  T.  A., Pendekatan  Algoritma  Untuk  Mencari Eksentrisitas  Suatu  Tree  dengan  Depth  First  Search ,  Jurnal  Duta.com, 12 (2) (2017), 9-14.
Winkelman, R., Topology , https://fcit.usf.edu/network/chap5/chap5.htm, 2013