POHON ( TREE )

Assalamualaikum wr.wb

                                       P O H O N ( T R E E )

     Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf.
Misalkan A merupakan sebuah himpunan berhingga simpul (vertex) pada suatu graf G
yang terhubung. Untuk setiap pasangan simpul di A dapat ditentukan suatu lintasan yang
menghubungkan pasangan simpul tersebut. Suatu graf terhubung yang setiap pasangan
simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut
dinamakan pohon (tree). Dengan kata lain, pohon (tree) merupakan graf tak-berarah yang terhubung dan tidak memiliki sirkuit.

• Gambar G1 dan G2 disebut pohon karena telah memenuhi syarat sesuai definisi pohon itu sendiri.
• Gambar G3 tidak bisa disebut pohon karena gambar tersebut mengandung sirkuit.

• Gambar G4 tidak bisa disebut pohon karena gambar tersebut memiliki graf yang tidak terhubung.

Hutan (forest) adalah kumpulan pohon yang saling lepas. Bisa juga diartikan dengan graf tak terhubung yang tidak mengandung sirkuit, dalam hal ini setiap komponen di dalam graf terhubung.

 

 

Sifat-sifat Pohon

Misalkan G = (V,E) adalah graf tak-berarah sederhana dan jumlah simpulnya n, maka :

1.      G adalah pohon

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

3.      G terhubung dan memiliki m = n -1 buah sisi

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

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

6.      G terhubung dan semua sisinya adalah jembatan (jembatan adalah sisi yang bila dihapus menyebabkan graf terpecah menjadi dua komponen)

         Jika hutan F dengan k komponen mempunyai

                        m = n – 1 buah sisi

 

Pohon Merentang (Spanning Tree)

Pohon merentang adalah subgraf dari graf terhubung berbentuk pohon.

• Setiap graf terhubung mempunyai paling sedikit 1 buah pohon merentang.
• Cabang (branch) adalah sisi dari graf semula (sisi pada pohon merentang).
• Tali-hubung (chord atau link) dari pohon adalah sisi dari graf yang tidak terdapat di dalam pohon merentang.

 

Pohon Berakar (Rooted Tree) 

• Pohon berakar adalah pohon yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar.
• Akar mempunyai derajat masuk nol dan simpul-simpul lainnya berderajat masuk sama dengan satu.
• Daun atau simpul terminal adalah simpul yang mempunyai derajat keluar sama dengan nol.
• Simpul dalam atau simpul cabang adalah simpul yang mempunyai derajat keluar tidak sama dengan nol.