GRAF dan POHON
A.
Pengertian Graf
Sebuah graf G didefinisikan sebagai pasangan himpunan (V,E) ,
dengan V adalah himpunan tak kosong yang terdiri dari simpul-simpul (vertices) atau titik pada G. Sedangkan E adalah
himpunan rusuk (edge) atau sisi pada G yang menghubungkan sepasang simpul atau
titik. Himpunan simpul atau titik pada G dinotasikan sebagai V, dan himpunan
rusuk atau sisi pada G dinotasikan sebagai E. Jadi G=(V, E)
Berdasarkan
ada tidaknya gelang atau sisi ganda pada suatu graph, maka graph digolongkan
menjadi dua jenis:
1.
Graph sederhana (simple graph).
Graf yang tidak mempunyai gelang
atau loop maupun sisi ganda.
2.
Graph tak-sederhana (unsimple-graph).
Graf yang mempunyai gelang atau
loop maupun sisi ganda.
Berdasarkan
jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan
menjadi dua jenis:
1. Graph tak-berarah (undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah atau panah disebut graph tak-berarah.
1. Graph tak-berarah (undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah atau panah disebut graph tak-berarah.
2. Graph berarah (directed
graph atau digraph)
Graph yang setiap
sisinya diberikan orientasi arah atau panah disebut sebagai graph berarah.
*Algoritma Graf
Algoritma Graf yang
dibahas dalam laporan ini ada 2 yaitu :
a). Algoritma
Dijkstra (Pencarian Jalur Terpendek)
Algoritma ini
bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu
titik ke titik lainnya. Misalkan titik mengambarkan gedung dan garis
menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasiatau total terhadap semua kemungkinan bobot terkecil dari setiap titik yang dilalui.
Pertama-tama tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan
pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi
tahap. Inilah urutan logika dari 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 (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. Sebagai contoh, jika titik
keberangkatan A ke B memiliki
bobot jarak 6 dan dari B ke node C
berjarak 2, maka jarak
ke C melewati B menjadi
6+2=8. Jika jarak ini lebih kecil dari jarak
sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data
jarak dengan jarak yang baru.
4. Saat kita 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.
2. Algoritma Kruskal
Algoritma Kruskal
adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum tree untuk
sebuah graf berbobot yang terhubung. Jika grafik tidak terhubung, maka
menemukan hutan rentang minimum (pohon rentan minimum untuk setiap komponen
terhubung). Dasar pembentukan algoritma Kruskal berasal dari analogi glowing
forest. Glowing forest maksudnya adalah
untuk membentuk pohon merentang minimum
T dari graf G adalah dengan cara mengambil satu persatu sisi dari
graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya.
Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki
pohon yang semakain
sedikit. Algoritma Kruskal
akan terus menambah sisi-sisi kedalam hutan yang sesuai hingga akhirnya tidak
akan ada lagi forest, melainkan hanyalah sebuah pohon yang merentang minimum.
Secara umum Algoritma
Kruskal ditulis:
1. T masih kosong
2. Pilih sisi (i, j) dengan bobot minimum
3. Pilih
sisi (i, j) dengan bobot minimum yang berikutnya yang tidak membentuk cycle di
T, tambahkan (i,j) ke T
4. Ulangi langkah 3 sebanyak (n-2) kali
Total langkah (n-1) kali
Karakteristik dari
Algoritma Kruskal :
a. Sifat dari
Algoritma Kruskal
1. Bekerja
tidak hanya dengan grafik diarahkan.
2. Bekeja dengan bobot dan tidak grafik tertimbang. tapi yang lebih menarik, apabila tepi yang berbobot.
3. Kruskal
adalah jenis algoritma yang menghasilkan solusi optimal MST.
Langkah-Langkah
Algoritma Kruskal
Langkah-langkah
algoritma Kruskal adalah sebagai berikut:
1. Atur
tepi berat: pling berat pertama dan terberat
terakhir.
2. Pilih
yang ringan tidak diperiksa tapi dari diagram.
3. Tambahkan
tepi memilih ini ke pohon, hanya jika hal itu tidak membuat siklus.
4. Menghentikan
proses kapanpun n-1 tapi lebih ditambahkan kepohon.
b. Pengertian Pohon
Pohon
(tree) adalah merupakan graf yang tak berarah terhubung yang tidak memuat sirkuit
sederhana. 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 .
Hutan ( forest ) merupakan kumpulan
pohon yang saling
lepas. Dengan kata lain, hutan merupakan graf tidak
terhubung yang tidak mengandung sirkuit.
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.- PermasalahanPermasalahan yang
terdapat pada laporan ini adalah sebagai berikut:
1. Membuat sebuah pembahasan tentang graf dan pohon serta algoritma djikstra dan kruskal.2. Membuat sebuah program mencari jalur terpendek antar rumah makan terdekat di Pelaihari menggunakan algoritma djikstra dan kruskal.
d. Penjelasan KasusKasus
yang diambil dalam laporan ini adalah kasus rumah makan terdekat di pelaihari.
Disini diambil beberapa rumah makan ada sekitar 10 rumah makan. Dari 10 rumah
makan tersebut diukur
jaraknya di google map untuk memuat grafnya. Setelah itu dibuat
jarak satu persatu rumah makan untuk membuat matriks berbobotnya.
a. Map
a. Map
b. Graf
Djikstra dan Kruskal
c. Matriks Djikstra
d. Matriks Kruskal
e. Codingan
Algoritma Djikstra
Hasil
Running Djikstra
f. Codingan
Algoritma Kruskal
Hasil
Running Kruskal
DAFTAR PUSTAKA
Rifanti, Marina Utti. 2017. “PEMILIHAN RUTE TERBAIK
MENGGUNAKAN ALGORITMA DIJKSTRA UNTUK MENGURANGI KEMACETAN LALU LINTAS DI
PURWOKERTO (BEST ROUTE SELECTION USE DIJKSTRA ALGORITHM TO REDUCE TRAFFIC
CONGESTION
IN PURWOKERTO)”. Diakses pada tanggal 25 Mei 2019 pukul 09.30 WITA dari https://www.researchgate.net/publication/325059321_Pemilihan_Rute_ Terbaik_Menggunakan_Algoritma_Dijkstra_Untuk_Mengurangi_Kem acetan_Lalu_Lintas_di_Purwokerto/download
Amrullah. 2018. “APLIKASI GRAF POHON PADA ALGORITMA
HUFFMAN”.
Diakses pada tanggal 25 Mei 2019 pukul 10.45 WITA dari https://www.researchgate.net/publication/322423546
Komentar
Posting Komentar