GRAF DAN POHON

A. POHON (TREE)

Pohon (tree) telah digunakan sejak tahun 1857 oleh matematikawan Inggris yang bernama Arthur Cayley untuk menghitung jumlah senyawa kimia.Silsilah keluarga biasanya juga digambarkan pasa bentuk pohon.

Pohon (tree) adalah merupakan graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. Diagram pohon dapat digunakan sebagai alat untuk memecahkan masalah dengan menggambarkan semua alternative  pemecahan.

Jadi, dapat disimpulkan bahwa pohon adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika : 
       - Graph tersebut tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1).  
       - Graph tersebut terhubung 

Contoh   :

Hutan ( forest ) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit.
Ciri – ciri hutan :
banyaknya titik = n
banyaknya pohon = k
banyaknya rusuk = n-k 
  
Berikut adalah beberapa sifat pohon :
1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi.
2. Jika G tidak mempunyai sirkuit maka G merupakan pohon.
3. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.
4. Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.
5. Misalkan G adalah graf sederhana dengan jumlah simpul n,jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit.

Spanning Tree
Spanning Tree adalah subgraph G merupakan pohon dan mencakup semua titik dari G. Pohon merentang di peroleh dengan cara menghilangkan sirkuit didalam graf tersebut.
Contoh :

T1, T2, T3, T4  merupakan spanning tree dari G
Minimal spanning tree dari labeled graph  Adalah spanning tree dari graph yang mempunyai jumlah panjang edge minimum.
Contoh   :

Rooted Tree ( Pohon Berakar )
Rooted tree adalah suatu tree yang mempunyai akar . Istilah-istilah / unsur - unsur yang ada  pada pohon berakar :
1. Akar dinyatakan dengan lingkar-aN
2. Daun
3. Cabang
4. Tinggi / level / dept / dalamnya suatu vertex
Contoh   :

Sifat utama Pohon Berakar
1. Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).
2. Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0.
3. Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.
4. Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke - n pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling
5. Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi
6. Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.
7. Banyaknya Simpul Maksimum sampai Level N adalah :
               2 (N) - 1

8. Banyaknya Simpul untuk setiap Level I adalah
              N
             ∑ 2 (I -1)
             (I-1)
 

B. ALGORITMA KRUSKAL  

Algoritma Kruskal adalah algoritma untuk mencari pohon merentang minimum secara langsung didasarkan pada algoritma MST (Minimum Spanning Tree) umum. Pada algoritma Kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisi-sisi sudah diurut berdasarkan bobot membentuk hutan (forest). Hutan tersebut dinamakan hutan merentang (spanning forest). Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di T. 

Perbedaan prinsip antara algoritma Prim dan Kruskal adalah jika pada algoritma Prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T, maka pada algoritma Kruskal sisi yang dipilih tidak perlu bersisian dengan simpul di T asalkan penambahan sisi tersebut tidak membentuk sirkuit. 

Langkah-langkah dalam algoritma Kruskal adalah sebagai berikut:  

1.      Lakukan pengurutan terhadap setiap sisi di graf mulai dari sisi dengan bobot terkecil sampai terbesar. 

2.      Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sirkuit di pohon. Tambahkan sisi tersebut ke dalam pohon. 

3.      Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang minimum berjumlah n-1 (n adalah jumlah simpul di graf). 

 

Kelebihan dan kekurangan algoritma kruskal
Kelebihan  :

Sangat cocok digunakan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan urutan bobot sisi bukan simpul. 

Kekurangan :

kurang cocok digunakan saat graf dimana setiap simpul terhubungkan dengan semua simpul yang lain. Karena algoritma ini menitik beratkan pada pencarian sisi yang diurutkan.  

Contoh kasus Algoritma Kruskal memecahkan sebuah konsep masalah pada PT. PLN yaitu menggunakan Algoritma Kruskal dalam pendistribusian listrik, dengan asumsi tiap rumah adalah sebuah simpul (node) dan kabel listrik adalah garis (edge). Konsep tersebut diterapkan pada pohon merentang minimum dengan mencari jalur terpendek dari sebuah kabel listrik sehingga diawali dengan mencari bobot yang kecil. Dengan membandingkan jaringan distribusi listrik yang telah dipasang oleh PT. PLN dengan jaringan distribusi listrik menggunakan metode Algoritma Kruskal. Hasil dari aplikasi jaringan distribusi listrik dengan menggunakan metode Algoritma Kruskal dapat menganalisis jaringan PT. PLN dengan meminimalisasi panjang kabel listrik sehingga lebih optimal dalam pemasangannya dan tidak ada pasokan kabel listrik yang terbuang percuma 

C. ALGORITMA DJIKSTRA  

Algoritma Dijkstra, (penemunya adalah seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobotbobot sisi yang bernilai positif.  Tujan Algoritma Dijkstra  

•      Tujuan Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya. 

•      Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses. 

•      Jumlah titik menentukan tingkat efektifitas dari algoritma djikstra. 

 

Urutan Logika Algoritma Dijkstra  

1.      Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi). 

2.      Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”. 

3.      Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan. 

4.      Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya. 

5.      Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3. 

Contoh kasus Algoritma Kruskal :  

Kebun Raya Purwodadi memiliki luas mencapai 85 hektar. Kebun raya purwodadi memiliki koleksi tanaman sejumlah 2002 jenis/spesies, 178 suku/family, 962 marga/genus dan 11.669 specimen. Dengan jumlah tanaman yang begitu banyak, dibutuhkan aplikasi yang dapat menunjukkan jalan dari lokasi pengguna ke lokasi tanaman yang dituju. Dalam pembuatan aplikasi, dibutuhkan suatu metode/algoritma untuk melakukan perhitungan guna mendapatkan jarak terdekat. Algoritma yang digunakan pada penelitian ini menggunakan algortima dijkstra yang dipilih karena memiliki waktu running time lebih cepat dibandingkan algoritma Bellman-Ford. Untuk merancang aplikasi yang dibutuhkan, tahap identifikasi kebutuhan fungsional berdasarkan kebutuhan dari pengunjung kebun raya. Sedangkan untuk kebutuhan non-fungsional adalah tentang usability dan compatibility. Implementasi yang dibuat berdasarkan perancangan yang telah dibuat sebelumnya. Web server dibangun menggunakan bahasa PHP, sedangkan aplikasi android menggunakan bahasa Java dengan tools android studio. Pada pengujiannya dilakukan secara black-box untuk menguji fungsional dari aplikasi dan semuanya valid. Sedangkan pengujian white-box digunakan untuk menguji algoritma dijkstra yang digunakan. Selain itu dilakukan pengujian usability dan menunjukkan hasil yang memuaskan dengan presentase sebesar 70.916% dengan jumlah responden sebanyak 30 orang 

                          

D. KESIMPULAN

Algoritma Kruskal adalah algoritma untuk mencari pohon merentang minimum secara langsung didasarkan pada algoritma MST (Minimum Spanning Tree) umum. Pada algoritma Kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisisisi sudah diurut berdasarkan bobot membentuk hutan (forest). Hutan tersebut dinamakan hutan merentang (spanning forest). Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di T.

Algoritma Dijkstra, (penemunya adalah seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif.  Berdasarkan penelitian yang telah dilakukan, dapat disimpulkan bahwa program algoritma djikstra maupun algoritma kruskal sangat membantu didalam menemukan data berupa jarak yang terdekat sehingga dapat menambah efisiensi waktu dalam pencarian tempat yang terdekat yang akan dituju. Dari kedua program ini, algoritma kruskal lebih unggul daripada algoritma djikstra, karena didalam algoritma kruskal tidak terjadi penginputan yang berulang (prinsipnya misalkan 1,2 = 2,1), sedangkan program algoritma djikstra selalu melakukan penginputan yang berulang (prinsipnya misalkan 1,2 ≠ 2,1). Dengan adanya prinsip seperti ini, tentu sangat mempengaruhi dalam waktu untuk pencarian data berupa jarak yang terdekat.