Materi MatDis (Matematika Diskrit) : Pohon

DEFINISI POHON

Pohon adalah graf tak berarah terhubung yang tidak mengandung sirkuit.
Beberapa pohon dapat membentuk hutan. Hutan adalah kumpulan pohon yang saling lepas. Atau hutan adalah graf tak terhubung yang tidak mengandung sirkuit, dalam hal ini setiap komponen graf terhubung adalah pohon.
Pohon juga seringkali didefinisikan sebagai graf tak berarah dengan sifat bahwa hanya terdapat sebuah lintasan unik antara setiap pasang simpul.


POHON MERENTANG

adalah semua simpul pada pohon T sama dengan semua simpul pada graf G.
Pohon merentang didefinisikan hanya untuk graf terhubung, karena pohon selalu terhubung. Pada graf terhubung terdapat setidaknya satu buah pohon merentang.Graf yang tidak mengandung sirkuit adalah pohon merentang itu sendiri. Pada graf yang mengandung sirkuit, pohon merentangnya diperoleh dengan cara memutuskan sirkuit yang ada.
Sisi pada pohon merentang disebut cabang. Sedangkan sisi dari graf yang tidak terdapat di dalam pohon merentang disebut tali hubung.Himpunan tali hubung beserta simpul yang bersisian disebut komplemen pohon. Rumus menghitung jumlah cabang dan jumlah tali hubung :

                                Jumlah cabang = n - 1
                                Jumlah tali hubung = m - n + 1

dan pada graf tidak terhubung dengan k komponen, m buah sisi dan n buah simpul,

                                Jumlah cabang = n - k
                                Jumlah tali hubung = m - n + k

Sirkuit yang terbentuk dengan penambahan sebuah tali hubung pada pohon merentang disebut sirkuit fundamental.


POHON MERENTANG MINIMUM

adalah pohon merentang yang berbobot minimum dimana pohon merentang ini merupakan pohon merentang yang paling penting karena mempunyai terapan yang luas dalam praktik.
Terdapat dua buah algoritma dalam membuat pohon merentang minimum :

1. Algoritma Prim

          Algoritma Prim membentuk pohon merentang minimum langkah per langkah. 

          1. Ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam T

          2. Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi e                        tidak  membentuk sirkuit di T. Masukkan e ke dalam T

          3. Ulangi langkah 2 sebanyak n - 2 kali

         Jumlah langkah seluruhnya di dalam algoritma prim adalah 1 + (n - 2) = n - 1, yaitu sebanyak             jumlah sisi di dalam pohon merentang dengan n buah simpul.

     2. Algoritma Kruskal

         Pada algoritma kruskal, sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari           kecil ke besar. Perbedaan prinsip antara algoritma prim dan algoritma kruskal adalah : jika pada           algoritma prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T,               maka pada algoritma kruskal sisi yang dipilih tidak perlu bersisian dengan sebuah simpul di T             asalkan penambahan sisi tersebut tidak membentuk sirkuit.

         

         Algoritma Kruskal :

1. T Masih Kosong
2. Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T. Masukkan e ke dalam T
3. Ulangi langkah 2 sebanyak n - 1 kali