POHON (Tree)
Just Because my Path is Different
Doesn't Mean I'm Lost.
- Unknown
A. Definisi
Pohon (Tree) telah di gunakan sejak tahun 1857 oleh Arthur Cayley (seorang matematikawan asal Inggris) untuk menghitung jumlah senyawa kimia. Pohon (tree) adalah sejenis graf tak berarah yang tidak mengandung sirkuit.
Sifat-Sifat Pohon
Misalkan G = (V,E) adalah graf tak-berarah sederhana dan jumlah simpulnya n, maka
- G adalah pohon.
- Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.
- G terhubung memiliki m = n-1 buah sisi.
- G tidak mengandung sirkuit dan memiliki m = n-1 buah sisi.
- G tidak mengandung sirkuit dan penambahan sati sisi pada graf akan membuat hanya satu sirkuit.
- G terhubung dan semua sisinya adalah jembatan (jembatan adalah sisi yang bila dihapus menyebabkan graf terpecah menjadi dua komponen).
B. Spanning Tree
Adalah subgraf G yang merupakan pohondan mencangkup semua titik dari G. Pohon merentang di peroleh dengan cara menghilangkan sirkuit di dalam graf tersebut.
Contoh :
Minimal Spanning Tree dari Labeled Graph
Adalah spanning tree dari graph yang mempunyai jumlah panjang edge minimum
Contoh :
C. Rooted Tree (Pohon Berakar)
Adalah suatu tree yang mempunyai akar. Istilah-istilah / unsur-unsur yang ada pada pohon berakar:
- Akar : Dinyatakan dengan lingkaran.
- Daun
- Cabang
- Tinggi / Level / dept / dalamnya suatu vertex
Contoh :
SIfat Utama Pohon Berakar
- Jika Pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).
- Mempunyai Simpul Khusus yang disebut Root, jika simpul tersebut memiliki derajat keluar>=0, derajad masuk = 0.
- Mempunyai simpul yang disebut sebagai daun / Leaf, jika Simpul tersebut berderajat keluar=0, dan berderajat masuk = 1.
- Setiap simpul memiliki tingkatan / level yang dimulai dar root yang levelnya = 1 sampai dengan level ke - npada daun paling bawah. Simpul yang mempunyai Level sama disebut bersaudara atau brother atau stribling.
- Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi.
- Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.
- Banyaknya Simpul Maksimim sampai Level N adalah : 2(N) - 1
- Banyaknya Simpul untuk setiap Level I adalah :
Pohon Berurut Berakar (Ordered Rooted Tree)
Adalah pohon berakar yang diberi label berurut secara sistematis. Sistem itu disebut Universal Address System.
Contoh : Dengan memberi nomor urutan.
NOL : Pada akar
Nomor atas n gigis pada setiap titik simpul yang berjarak dari n akar.
Gambar pohon berurut berakar di atas disebut Lexicographic order.
Pernyataan Aritmatika (a-b) / [(cxd)+e] dapat digambarkan dalam Lexicographic.
D. Algoritma Prim dan Algoritma Kruskal
Kedua Algoritma ini berbeda dalam metodeloginya, tetapi keduanya mempunyai tujuan menemukan minimum spanning.
- Algorithm Kruskal menggunakan edge.
- Algorithm Prim menggunakan vertex yang terhubung.
Perbedaan prinsip antara Algoritma Prim dan Algoritma Kruskal adalah, jika pada Algoritma Prim sisi yang dimasukkan ke dalam T harus bersisihan dengan sebuah simpul di T, maka pada Algoritma Kruskal sisi yang dipilih tidak perlu bersisian dengan sebuah simpul di T, asalkan penambahan sisi tersebut tidak membentuk cyrcle.
Algoritma Kruskal
Pada Algoritma Kruskal, sisi (edge) dari Graph diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan kedalam himpunan T adalah sisi graph G yang sedemikian sehingga T adalah ( Tree ) Pohon. Sisi dari graph G ditambahkan ke T jiika ia tidak membentuk cycle.
- T masik kosong.
- Pilih sisi (i,j) dengan bobot minimum.
- Pilih sisi (i,j) dengan bobot minimum berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T.
- Ulangi langkah 3 sebanyak (n-2) kali.
- Total langkah (n-1) kali.
Syntax Penulisan Program Algoritma Kruskal :
program kruskal;
uses wincrt;
var
{kamus}
i = integer;
x = integer; // banyaknya vertex, x > 0
G = integer; // banyaknya edge dalam graph, G > 0
z = integer; // banyaknya edge dalam spinning tree, z = 0
xv = string; // edge, bukan angka
e = integer; // wight, e < 0
a = integer;
jum = integer; // total minimum spanning tree
begin
{program}
{input harus sesuai agar tidak membingungkan user}
write ('masukkan banyaknya vertex : ');
readln(x);
z := x-1; // rumus mencari banyak edge dalam spinning tree
writeln ('banyaknya edge dalam spinning tree : ' , z);
writeln;
writeln ('masukkan banyaknya edge dalam graph : ');
readln (G) ; // inisialisasi
i := 1; // elemen pertama
while (i<=G) do
begin
write ('masukkan edge ke-',i,'(pisahkan dengan koma) : ');
readln (xv);
write ('masukkan weight dari edge ke-',i,' : ');
readln (e);
if (i<=G) then // eksekusi selama i <= G
begin
writeln ('edge ke-',i,' = {',xv,'} , weight edge ke-',i,' = ',e);
writeln;
end;
i := i + 1; // next element
if (i > G) then // eksekusi apabila i > G
begin
a :=1; // elemen pertama untuk looping
jum := 0; // inisialisasi untuk addition
while (a <= z) do
begin
writeln;
writeln (a, 'edge dari ',z,'edge di spining tree');
write ('masukkan edge yang memiliki weight terkecil : ');
readln(xv);
write ('masukkan wight dari edge tersebut : ');
readln(e); // elemen pertama / elemen selanjutnya untuk addition
jum := jum+e;
a := a+1; //elemen selanjutnya untuk looping
end;
end;
end;
writeln;
write ('total minimum spaning tree : ', jum);
{terminasi}
END.
Algoritma Prim
Pada Algoritma Prim, dimulai pada vertex yang mempunyai sisi (edge) dengan bobot terkecil.
Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang bersisian dengan sebuah simpul di T, sedemikian sehingga T adalah Pohon. Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle.
(NOTE : Dua atau lebih edge kemungkinan mempunyai bobot yang sama, sehingga terdapat pilihan vertice, dalam hal ini dapat diambil salah satunya)
- Ambil sisi (edge) dari graph yang ber bobot minimum, masukkan kedalam T.
- Pilih sisi (edge) (i,j) yang berbobot minimum dan bersisihan dengan simpul di T, tetapi (i,j) tidak membentuk cycle di T. Tambahkan (i,j) kedalam T.
- Ulangi prosedur no 2 sebanyak (n-2) kali.
Syntax Penulisan Program Algoritma Prim :
uses crt;
type
rec = record
d1 : byte;
d2 : byte;
uz : word;
var
mst, tree : array [1 .... 100] of rec; i,j,k,l,m,n,t1,t2,s : integer;
check : array [1 .... 50] of byte; ch : char;
jum = integer; // total minimum spanning tree
BEGIN
clrscr;
write ('Number of nodes : ');
readln(n);
write('Number of connections : ');
readln(m);
writeln ('Input node numbers and distance in sorted order .....');
k :=3;
for i : =1 to m do
begin
gotoxy(1,k+i); write ('Node 1 : '); read (mst[i].d1);
gotoxy(15,k+i); write ('Node 2 : '); read (mst[i].d2);
gotoxy(28,k+i); write ('distance : '); read (mst[i].uz);
end;
writeln;
i :=1; s :=1; i :=0;
while i<=n do
begin
t1 := mst[i].d1;
t2 := mst[i].d2;
if check [t1] + check[t2] = 0 then
begin
check[t1] := s;
check[t2] := s;
inc(s); inc(l);
tree[l] := mst[i];
end
else if check [t1] * check[t2] = then
begin
k := t1+t2;
check[t1] := k;
check[t2] := k;
inc(s); inc(l);
tree[l] := mst[i];
end
else if check [t1] <> check[t2] then
if check [t1] < check[t2] then
begin
for j := 1 to i-1 do
if (mst[j].d1=t2) or (mst.[j].d2=t2) then
begin
check [mst[j].d1] := check[t1]
check [mst[j].d2] := check[t1]
inc(l);
tree[l] := mst[i];
end;
inc(s);
end
else if check [t1] > check[t2] then
begin
for j := 1 to i-1 do
if (mst[j].d1=t2) or (mst.[j].d2=t2) then
begin
check [mst[j].d1] := check[t1]
check [mst[j].d2] := check[t1]
inc(l);
tree[l] := mst[i];
end;
end;
writeln ('Minimum Spinning Tree.');
write ('Node 1'); for i :=1 to l do write (tree[i].d1:3); writeln;
write ('Node 2'); for i :=1 to l do write (tree[i].d2:3); writeln;
write ('Distance'); for i :=1 to l do write (tree[i].uz:3); writeln;
repeat ch := readkey until ch = #27;
END.
