graf(pohon)

MATEMATIKA DISTRIT

=POHON=

1.      Defenisi

Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit .

2.      Sifat-sifat pohon 

3.       

Pohon Merentang

Pohon merentang di perole dengan memutus sirkuit di dalam graf.

           

Setiap graf terhubung mempunyai paling sedikit  satu buah ppohon merentang.

Graf tak-terhubung dengan k komponen mempunyai k buah  hutan merentang yang disebut hutan merentang (spanning  forest).

4.      Aplikasi pohon merentang

1.Jumlah ruas jalan seminimum mungkin  yang  menghubungkan semua kota sehingga setiap kota tetap  terhubung  satu sama lain.

2.Perutean (routing) pesan pada jaringan komputer.

             Pohon merentang minimum

Graf terhubung-berbobot mungkin mempunyai lebih dari 1  pohon merentang.

Pohon merentang yang berbobot minimum –dinamakan pohon  merentang minimum (minimum spanning tree)

5.      Algoritma Prim

Langkah1 : ambil sisi dari graf           G yang berbobot minimum,masukkan ke dalam T.

Langkah 2 : pilih sisi (u, v) yang mempunyai bobot minimum dan  bersisian dengan    simpul di T, tetapi (u, v) tidak  membentuk sirkuit di T. Masukkan (u, v) ke dalam T.

Langkah 3 :ulangi langkah 2 sebanyak n – 2 kali.

Contoh :