TREE (POHON)

A.    KONSEP POHON

              Pohon didefinisikan sebagai suatu graf tak berarah terhubungkan (connected undirected graph) yang tidak mengandung rangkaian sederhana. Pohon adalah bentuk khusus dari suatu graf yang banyak diterapkan untuk berbagai keperluan. Misalnya struktur organisasi suatu perusahaan, silsilah suatu keluarga, skema sistem gugur suatu pertandingan, dan ikatan kimia suatu molekul adalah jenis graf yang tergolong sebagai pohon. Pada pohon, simpul-simpul yang berderajat satu dinamakan daun (leave), sedangkan simpul yang derajatnya lebih besar daripada satu dinamakan simpul cabang (branch node) atau simpul internal (internal node) dan kumpulan pohon-pohon yang terpisahkan satu sama lain disebut hutan (forest).

Contoh pohon :

B.           POHON BERAKAR

             Suatu  graf dinamakan pohon berarah bila arah rusuknya diabaikan dan suatu pohon berarah dinamakan pohon berakar (rooted tree) bila ada tepat satu simpul yang berderajat masuk 0, dan semua simpul lain berderajat masuk 1. simpul berderajat masuk 0 dinamakan akar, simpul berderajat keluar 0 dinamakan daun, sedangkan simpul yang berderajat masuk 1 tetapi derajat keluarnya tidak 0 disebut simpul cabang. 

                   pada gambar di atas simpul a adalah akar, simpul-simpul b, c adalah simpul cabang sedangkan        simpul-simpul d, e, f, dan g adalah daun.

                         Simpul d disebut anak (child)  dari simpul b bila ada rusuk dari b ke d, dalam hal ini simpul       b disebut ayah (parent) dari simpul d. Bila simpul d memiliki anak lagi maka anak dari simpul          merupakan keturunan (descendent) dari simpul a, b, d , karena ada lintasan berarah dari simpul-       simpul tersebut ke simpul anak dari d. Sebaliknya, simpul-simpul a, b, dan d disebut leluhur             (ancestor) dari simpul anak dari d.

                        Bila dalam menggambar suatu pohon berakar, anak suatu simpul cabang selalu ditempatkan       di bawahnya, maka tanda panah rusuk dapat diabaikan saja.

            Teorema Pohon Berakar

            Teorema 1 (Teorema geometrik pohon)

            Bila (T,V0) adalah pohon berakar (T adalah relasi dan V0 adalah akar) maka:

·         Tidak ada siklus dalam T

Gambar di atas bukanlah suatu pohon berakar karena ada suatu siklus dari V0 - V2  -  V3 kembali ke V0.

·               V0 merupakan  satu-satunya akar dari T

            Tidak ada akar selain V0 pada suatu pohon.

Gambar di atas bukanlah pohon berakar  karena mempunyai 2 akar pohon yaitu V0 dan V1.

·               Tiap simpul di T kecuali V0 memiliki derajat masuk satu   sedangkan V0 berderajat 

           masuk 0.

          Gambar di atas bukanlah suatu pohon berakar karena akarnya (V0) berderajat masuk 1 dan ada simpul lain yang berderajat masuk 2 yaitu V4.

Teorema 2

·         Irreflexive

     Setiap simpul tidak berelasi dengan simpul itu sendiri. 

·         Asymmetric

      Relasi yang terjadi antar simpul bukanlah merupakan relasi bolak-balik (relasi satu arah).

     Gambar di atas bukan pohon berakar karena V₂ dan V₅ berelasi bolak – balik.

·         Jika (a, b) Î T dan (b, c) ÎT, maka (a, c) ÏT

      Bila b berelasi dengan a dan bila c berelasi dengan b, maka c tidak memiliki relasi dengan a.

           Teorema 3

           Bila (T, v_o) adalah pohon berakar dan v Î T maka :

♣    T(v) juga pohon berakar dengan akar v . T(v) juga subtree dari T dengan awal v.

 

Sebuah pohon berakar yang simpul cabangnya memiliki paling banyak m anak (maksimal), disebut dengan pohon m-er (m-ary tree).Dan sebuah pohon m-er dikatakan teratur bila setiap simpul cabangnya tepat memiliki m anak.

            Contoh:

Hubungan antara banyakya simpul cabang dengan banyaknya daun pada suatu pohon m-er teratur bisa kita lihat pada contoh berikut. Misalkan ada sebuah turnamen, pada setiap pertandingan menggunakan sistem gugur. Ada 16 klub peserta turnamen, sehingga pada akhir turnamen hanya tersisa satu tim yang menjadi juara. Bila kita tuangkan jadwal pertandingannya dalam bentuk grafik, ini merupakan contoh sebuah pohon biner teratur dimana setiap simpul cabang tepat memiliki 2 anak. Maka kita dapat menemukan bahwa jumlah pertandingan yang dilangsungkan adalah 15 pertandingan (satu lebih sedikit daripada jumlah klub peserta).

       Bila i menyatakan banyak simpul cabang, dan t menyatakan banyaknya daun, maka diperoleh hubungan :

i = t – 1

           hasil ini dapat diperluas untuk pohon m-er teratur lainnya menjadi :

(m–1) i = t – 1

           Contoh :

           Bila sebuah komputer dapat menghitung 3 buah bilangan sekaligus dengan sebuah instruksi, berapa instruksikah yang dibutuhkan untuk menjumlahkan 7 buah bilangan ?

            Jawab :  dengan menggunakan rumus yang sudah kita definisikan diatas, maka:

(m–1) i = t – 1    ; m=3 dan t=7

                                                          (3–1) i = 7 – 1

                                                                   i = 3

            Ini berarti komputer harus melakukan 3 kali instruksi untuk menjumlahkan ketujuh bilangan tersebut dan dapat digambarkan sebagai berikut (dalam dua cara)

               POHON BINER

          Pohon biner merupakan jenis pohon m-er yang simpul cabangnya memiliki maksimal dua anak. Karena anak dari suatu cabang maksimal hanya dua, maka anak cangan ini dinamakan anak cabang kiri atau anak cabang kanan. Dalam pohon biner, cabang kiri dan kanan ini dibedakan (untuk pohon secara umum tidak). Bukan hny cabangnya saja, bahkan urutan cabang kiri atau vabang kanan pun dibedakan. Perhatikan gambar dibawah  ini, kedua contoh ini merupakan pohon biner yang berbeda.

           

           Penenlusuran pohon biner

           Penelusuran pohon berakar ada 3 macam :

1.            Preorder

§  Kunjungi akar

§  Telusuri  cabang kiri

§  Telusuri cabang kanan 

2.              Inorder

§  Telusuri cabang kiri

§  Kunjungi akar

§  Telusuri cabang kanan

3.             Postorder

§  Telusuri cabang kiri

§  Telusuri cabang kanan

§  Kunjungi akar

                    Preorder : a-b-d-h-e-i-c-f-i-g-k-l

                    Inorder : h-d-b-e-i-a-j-f-c-k-g-l

                    Postorder : h-d-i-e-b-j-f-k-l-g-c-a

sumber: makalah matematika diskrit mahasiswa elektro UGM 2002 

			A
	A