Pohon (Tree)

   Pohon(tree) merupakan salah satu bentuk khusus graf. Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut dinamakan pohon(tree).
   Dengan kata lain, pohon merupakan graf tak berarah yang terhubung dan tidak memiliki sirkuit.

   Hutan(forest) merupakan kumpulan pohon yang saling lepas.

Sifat-sifat pohon

• G adalah sebuah pohon
• Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal
• G terhubung dan memiliki m = n-1 buah sisi
• G tidak mengandung sirkuit dan memiliki m = n-1 buah sisi
• G tidak mengandung sirkuit dan penambahan saru sisi pada graf akan membuat hanya satu sirkuit
• G terhubung dan semua sisinya adalah jembatan

===============Pohon Merentang (spanning tree)==============

   Spanning tree dari suatu graf terhubung merupakan subgraf merentang yang berupa pohon. Pohon merentang diperoleh dengan cara menghilangkan sirkuit didalam graf tersebut.
    Pohon merentang memiliki bobot minimum yang dinamakan pohon merentang minimum. Untuk menentukan suatu pohon merentang minimum dari suatu graf terhubung, dapat menggunakan dua cara yaitu algoritma Prim dan algoritma Kruskal.

Algoritma Prim :
1. Pilih sisi dari graf G yang berbobot minimum, masukkan ke dalam T.
2. Pilih sisi (u,v) dalam G yang mempunyai bobot minimum dan bersisian dengan simpul di T, dengan syarat sisi tersebut tidak membentuk sirkuit di T. Masukkan (u,v) ke dalam T
3. Ulangi langkah 2 sebanyak n-2 kali

    Pohon merentang yang dihasilkan tidak selalu unik meskipun bobotnya tetap sama. Hal ini terjadi jika ada beberapa sisi yang akan dipilih berbobot sama.

Algoritma Kruskal :
*sisi-sisi dari graf yang sudah di urut menaik berdasarkan bobotnya, dari yang terkecil hingga terbesar*
1. T masih kosong
2. Pilih sisi(u,v) dengan bobot minimjm yang tidak membentuk sirkuit di T. Tambahkan (u,v) ke dalam T.
3. Ulangi langkah 2 sebanyak n-1 kali