Materi MatDis (Matematika Diskrit) : Pohon Part 2

1. Pohon Berakar 

          adalah pohon yang sebuah simpulnya diperlukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar.

Terminologi pada pohon berakar

Anak(Child atau children) dan Orangtua (parent)

Misalkan Xx adalah sebuah simpul di dalam pohon berakar. Simpul y dkatakan anak simpul x jika ada sisi dari simpul x ke y. Dalam hal demikian, x disebut orangtua (parent)  y. Pada gambar dibawah, b, c dan d adalah anak-anak simpul a, dan a adalah orangtua dari anak-anak itu. e dan f adalah anak-anak simpul b dan b adalah orangtua dari e dan f. g adalah anak simpul d dan d adalah orangtua g. Simpul h,i, j, l dan m tidak mempunyai anak.

2. Pohon Berakar Terurut

    adalah pohon berakar yang urutan anak-anaknya penting.

3. Pohon Ekspresi
   adalah pohon biner dengan daun menyatakan operand dan simpul dalam (termasuk akar) menyatakan operator. Perhatikan bahwa tanda kurang tidak lagi diperlukan bila suatu ekspresi aritmetik diprsentasikan sebagai pohon biner.
contoh :
(a+b) * c/(d+e) Infix
Prefix : *+ ab/c + de
Posfix : ab + cde +/*


INFIX, POSTFIX dan PREFIX

1. Infix
    Digunakan manusia sebagai input di komputer
2. Postfix
    Digunakan komputer sebagai proses
3. Prefix
    Sama Seperti Postfix yaitu digunakan komputer sebagai proses.

• Konversi Infix ke Postfix

ada 3 cara yaitu :
1. Cara Manual
    Caranya adalah dengan menyederhanakan  notasi menjadi dua operand (variabel) da satu operator, seperti A + B

2. Cara Stack
    Stack adalah tumpukan (jadi, memori diibaratkan dengan tumpukan) yang memiliki cara kerja yang pertama masuk ke kotak, maka akan terakhir kali diambil kembali atau first in last out atau sebaliknya, yang terakhir masuk ke kotak akan diambil yang pertama kali, atau last in first out.

3. Cara Binary Tree

• Konversi Infix ke Prefix

Ada 2 cara :
1. Cara Manual
    Sama seperti mengonversi notasi infix ke prefix
2. Cara Binary Tree
    Sama seperti mengonversi notasi infix ke prefix

• Konversi Prefix ke Infix dan/atau Postfix

Bisa dilakukan melalui bantuan manual dan pohon binar.

• Konversi Postfix ke Infix dan/atau Prefix

Sama seperti Konversi Prefix ke Infix dan/atau Postfix

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