Maysarah: Penerapan Kasus sehari-hari pada Graf dan Pohon

Politala 2A

GRAF DAN POHON

A. Definisi Graf dan Pohon

Pohon (tree) adalah graf tak-berarah terhubung yang tidak memuat sirkuit sederhana. Menurut definisi di atas, suatu pohon merupakan graf yang terhubung, tak berarah, dan tidak memuat sirkuit, ini merupakan tiga kriteria utama untuk pohon. Pohon adalah bentuk khusus dari suatu graf yang banyak diterapkan untuk berbagai keperluan. Misalnya struktur organisasi suatu perusahaan, silsilah suatu keluarga, skema sistem gugur suatu pertandingan, dan ikatan kimia suatu molekul adalah jenis graf yang tergolong sebagai pohon. Pada pohon, simpul-simpul yang berderajat satu dinamakan daun (leave), sedangkan simpul yang derajatnya lebih besar daripada satu dinamakan simpul cabang (branchnode) atau simpul internal (internal node) dan kumpulan pohon-pohon yang terpisahkan satu sama lain disebut hutan (forest) Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur ini biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan hierarkykal antara elemen-elemen mereka.Bentuk pohon khusus yang lebih mudah dikeloladalam komputer adalah pohon binary. Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar T didefinisikan terdiri dari sebuah himpunan hingga elemen yang disebut simpul [2], sedemikian sehingga :

a. T adalah hampa (disebut pohon null) atau

b. T mengandung simpul R yang dipilih disebut akar (root) dari T, dan simpul sisanya membentuk 2 pohon binary T1 dan T2 yang saling lepas.

B. Sifat-sifat Pohon

Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan dibawah ini adalah ekivalen :

a. G adalah pohon.

b. Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.

c. G terhubung dan memiliki m = n – 1 buah sisi.

d. G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi.

e. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit.

f. G terhubung dan semua sisinya adalah jembatan.

C. Pohon Merentang (Spanning Tree)

Suatu pohon rentangan atau spanning tree adalah suatu subgraf dari graf G yang mengandung semua simpul dariG dan merupakan suatu pohon [3]. Pohon merentang darigraf terhubung adalah upagraf merentang yang berupa pohon. Artinya, setiap vertex terletak di pohon, tetapi tidak ada siklus (atau loop) terbentuk. Di sisi lain, setiap jembatan dari G harus milik T.Sebuah pohon rentang dari graf terhubung G juga dapat didefinisikan sebagai satu set maksimal tepi G yang berisi siklus tidak ada, atau sebagai seperangkat minimal tepi yang menghubungkan semua titik. Dalam bidang-bidang tertentu teori grafik sering berguna untuk mencaripohon rentang minimum dari sebuah graf berbobot. Masalah optimasi lain di pohon mencakup juga telah dipelajari, termasuk mencakup pohon maksimum, pohon minimum yang mencakup setidaknya simpul k, pohon rentang minimum dengan di tepi k paling per titik (Gelar-Dibatasi Spanning Tree) , pohon merentang dengan jumlah daun terbesar (erat kaitannya dengan terkecil terhubung mendominasi set ), pohon merentang dengan daun paling sedikit (berkaitan erat dengan masalah jalan Hamilton ), dengan rentang diameter pohon minimal, dan dilatasi mini-mum spanning tree Perhatikan graf G dibawah ini dengan beberapa pohon perentang dari graf G tersebut yaitu T1, T2, dan T3.

1. Algoritma Kruskal

Algoritma Kruskal adalah algoritma pohon rentang minimum yang menemukan tepi dengan bobot sekecil mungkin yang menghubungkan dua pohon di hutan. Ini adalah algoritma serakah dalam teori grafik karena ia menemukan pohon spanning minimum untuk grafik tertimbang yang terhubung yang menambah kenaikan biaya busur pada setiap langkah. Ini berarti ia menemukan subset dari tepi yang membentuk pohon yang mencakup setiap titik , di mana total berat semua tepi di pohon diminimalkan. Jika grafik tidak terhubung, maka ia akan menemukan hutan spanning minimum (pohon spanning minimum untuk setiap komponen yang terhubung ).

Langkah Algoritma Kruskal :

1) Atur tepi berat : paling berat pertama dan terberat terakhir

2) Pilih yang ringan tidak diperiksa tepi dari diagram

3) Tambahkan tepi memilih ini ke pohon, jika hal itu tidak akan membuat siklus

4) Menghentikan proses kapanpun n-1 tepi lebih ditambahkan ke pohon-pohon

a) Listing Program

b) Hasil Running Program

2. Algoritma Dijkstra

Algoritme Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritme rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif. Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. Input algoritme ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G. Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.

Langkah-langkah Algoritma Dijkstra :

1) 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.

2) 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.

3) Set semua node yang belum dilalui dan set node awal sebagai “Node keberangkatan”

4) Dari node keberangkatan, pertimbangkan node tetangga yang belum dilalui dan hitung jaraknya dari titik keberangkatan. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru

5) Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah dilalui sebagai “Node dilewati”. Node yang dilewati tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

6) Set “Node belum dilewati” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan ulangi langkah e.

a) Listing Program