Materi Pohon (tree) pada Matematika Diskrit

Baca Juga

Pohon (tree) adalah :

F Graf tak-berarah terhubung yang tidak mengandung sirkuit

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

 Download file lengkapnya disini 

Contoh

Sebuah pohon mempunyai 2n buah simpul berderajat 1, 3n buah simpul berderajat 2 dan n buah simpul berderajat 3.

Tentukan banyaknya simpul dan sisi di dalam pohon tersebut !

Penyelesaian :

Berdasarkan lemma jabat tangan :

            jumlah semua simpul di dalam graf adalah 2 kali jumlah sisi di dalam graf tersebut

            (2n x 1) + (3n x 2) + (n x 3) = 2 |E|

                                    11n = 2 |E| ……………………………          (1)

Jumlah sisi pada sebuah pohon adalah jumlah simpul minus satu, sehingga :

            |E| = (2n + 3n + 1) – 1 = 6n – 1  …………………     (2)

Persamaan (1) dan (2) menjadi :

            11n = 2 (6n – 1)

            11n = 12n – 2

               n = 2

Jadi :

Ä  Jumlah simpul pada pohon 6n = 6 x 2 = 12 buah simpul

Ä  Jumlah sisi 6n – 1 = 11 buah sisi

Pohon Merentang (Spanning Tree)

Pohon merentang adalah :

F Subgraf dari graf terhubung berbentuk pohon

Jika n buah simpul dan m buah sisi maka :

F Untuk graf terhubung :

Ä  Jumlah cabang : n – 1

Ä  Jumlah tali hubung : m – n + 1

F Untuk graf tak-terhubung dengan k komponen :

Ä  Jumlah cabang : n – k

Ä  Jumlah tali-hubung : m – n + k

Rank graf G adalah :

F Jumlah cabang pada pohon merentang dari sebuah graf G

Nullity graf G adalah :

F Jumlah tali hubung pada graf G

Sehingga :

                        jumlah sisi graf G = rank + nullity

Nullity graf sering diacu sebagai bilangan siklomatik atau bilangan Betti pertama

Sirkuit fundamental (fundamental circuit) adalah :

F Sirkuit yang terbentuk dengan penambahan sebuah tali-hubung pada pohon merentang