Pohon (Tree) pada Teori Graph

Definisi Pohon (Tree) dapa Teori Graph

Graf terhubung tak berarah G disebut pohon jika penghapusan salah satu sisinya membuat G terputus. Sekumpulan pohon Tree disebut hutan (forest).

Dalam teori graf, tree adalah graf tak berarah, terhubung, dan asiklik. Dengan kata lain, graf terhubung yang tidak memuat satu siklus pun disebut pohon.

Sebuah pohon mewakili struktur hierarkis dalam bentuk grafik. Elemen-elemen pohon disebut simpulnya dan tepi pohon disebut cabang. Sebuah pohon dengan n simpul memiliki (n-1) sisi.

Daun pada pohon adalah simpul berderajat 1 atau setiap simpul yang tidak memiliki cabang ke bawah disebut daun.

Sifat-sifat Tree Pohon

Setiap pohon pada dua atau lebih simpul memiliki setidaknya satu simpul daun.

Simpul yang berada di bagian atas pohon  dikenal sebagai akar pohon.

Item data yang tersisa dibagi menjadi himpunan bagian yang terpisah-pisah yang disebut sebagai subpohon.

Pohon itu diperluas dari atas ke arah bawah.

Graf T adalah pohon jika dan hanya jika antara setiap pasangan simpul berbeda dari T terdapat lintasan yang unik.

Sebuah pohon dengan n simpul memiliki tepat n−1 cabang atau sisi.

Sebuah pohon dengan simpul berderajat k≥1 memiliki setidaknya k simpul daun. Secara khusus, setiap pohon dengan setidaknya dua simpul memiliki setidaknya dua simpul daun.

Sebuah titik potong pada graf terhubung G adalah sebuah titik yang penghilangannya memutuskan graf tersebut. Setiap graf terhubung memiliki simpul daun yang bukan merupakan titik potong.

Elemen elemen pada Tree

Edge – Garis yang menghubungkan dua node.

Level – Sebuah pohon dipartisi menjadi beberapa level sedemikian rupa sehingga simpul akar berada pada level 0. Kemudian, anak-anak terdekatnya berada di level 1, dan anak-anak terdekatnya berada pada level 2 dan seterusnya hingga terminal atau simpul daun.

Derajat – Ini adalah jumlah subpohon dari sebuah simpul di pohon tertentu.

Depth – Ini adalah tingkat maksimum dari setiap simpul di pohon tertentu dan juga dikenal sebagai ketinggian.

Node terminal – Node level tertinggi adalah node terminal sementara node lain kecuali terminal dan node root dikenal sebagai node non-terminal.

Perbedaan Tree dan Graf

Pada tree pohon hanya ada satu jalur antara dua simpul sedangkan grafik dapat memiliki jalur searah dan dua arah antara node.

Pada pohon, ada tepat satu simpul akar, dan setiap anak hanya dapat memiliki satu orang tua. Sebaliknya, dalam grafik, tidak ada konsep simpul akar.

Sebuah pohon tidak dapat memiliki loop dan self-loop sedangkan graph dapat memiliki loop dan self-loop.

Grafik lebih rumit karena dapat memiliki loop dan self-loop. Sebaliknya, pohon sederhana dibandingkan dengan grafik.

Sebuah pohon dapat memiliki n-1 sisi. Sebaliknya, dalam grafik, tidak ada jumlah tepi yang ditentukan sebelumnya, dan itu tergantung pada grafik.

Pohon memiliki struktur hierarkis sedangkan grafik memiliki model jaringan.

Pohon Merentang (Spanning Tree)

Jika G adalah graf terhubung pada n simpul, pohon merentang pada G adalah subgraf dari G yang merupakan pohon pada n simpul. Setiap graf terhubung memiliki spanning tree.

 Metode Spanning Tree 

Kita dapat menemukan pohon merentang secara sistematis dengan menggunakan salah satu dari dua metode:

1. Metode pemotongan

Mulailah memilih graf melingkar apa pun di Grafik G.

Hapus salah satu tepi graf melingkar.

Ulangi proses ini sampai tidak ada lingkaran yang tersisa.

2. Metode membangun

Pilih tepi graf G satu per satu. Sedemikian rupa sehingga tidak ada siklus yang dibuat.

Ulangi proses ini sampai semua simpul dimasukkan.