POHON (TREE)

-


   A.  Pengertian Pohon (Tree)

·         Pohon (tree) telah digunakan sejak tahun 1857 oleh matematikawan Inggris yang bernama Arthur Cayley untuk menghitung jumlah senyawa kimia.Silsilah keluarga biasanya juga digambarkan pasa bentuk pohon.

Defenisi Pohon (Tree) adalah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung maka pada pohon selalu terdapat path atau jalur yang menghubungkan kedua simpul di dalam pohon.
 Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. Misalkan A merupakan sebuah himpunan berhingga simpul (vertex) pada suatu graf G yang terhubung. Untuk setiap pasangan simpul di A dapat ditentukan suatu lintasan yang menghubungkan pasangan simpul tersebut.  Untuk itu perlu diingat kembali bahwa :
1.     Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari graf G selalu terdapat jalur yang menghubungkan kedua simpul tersebut.
2.    Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap simpul dua.
Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut dinamakan pohon (tree). Dengan kata lain, pohon (tree) merupakan graf tak-berarah yang terhubung dan tidak memiliki sirkuit.
Jadi, dapat disimpulkan bahwa pohon adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika :
~ Graph tersebut tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1).
~ Graph tersebut terhubung .

Contoh   : 


Hutan ( forest ) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit.
Ciri – ciri hutan :
banyaknya titik = n
banyaknya pohon = k
banyaknya rusuk = n-k 
   
B. Berikut adalah beberapa sifat pohon :
1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi.
2. Jika G tidak mempunyai sirkuit maka G merupakan pohon.
3. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.
4. Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.
5.Misalkan G adalah graf sederhana dengan jumlah simpul n,jika G tidakmengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuatsatu sirkuit. 

C. Spanning Tree
Spanning Tree adalah subgraph G merupakan pohon dan mencakup semua titik dari G.Pohon merentang di peroleh dengan cara menghilangkan sirkuit didalam graf tersebut. 
Contoh :


T1, T2, T3, T4 ® merupakan spanning tree dari G

Minimal spanning tree dari labeled graph  Adalah spanning tree dari graph yang mempunyai jumlah panjang edge minimum.
Contoh   :


D.   Rooted Tree ( Pohon Berakar )

Rooted tree adalah suatu tree yang mempunyai akar . Istilah-istilah / unsur - unsur yang ada pada pohon berakar :
1.  Akar :dinyatakan dengan lingkar-aN
2. Daun
3.  Cabang
4.  Tinggi / level / dept / dalamnya suatu vertex
Contoh   :


E.   Sifat utama Pohon Berakar

1.   Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).
2.   Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0.
3.  Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.
4.  Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke - n pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling
5.  Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi
6.  Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.
7.  Banyaknya Simpul Maksimum sampai Level N adalah :
               2 (N) – 1
8. Banyaknya Simpul untuk setiap Level I adalah
              N
             ∑ 2 (I -1)
             (I-1)

Pohon Berurut Berakar (Ordered Rooted Tree) adalah  pohon berakar yang diberi label berurut secara sistematis. Sistem itu disebut Universal Adress System.

Contoh : dengan memberi nomor urutan; NOL pada akar, kemudian memberikan nomor atas n gugus pada setiap titik simpul yang berjarak n dari akar.


Gambar pohon berurut berakar di atas disebut Lexicographic order.
Pernyataan arimetika (a-b) / [(cxd)+e] dapat digambar dalam Lexicographic.




Contoh Soal Pohon
1.      Spanning Tree
Perhatikan gambar suatu graf berikut :


Penyelesaian dengan Spanning Tree adalah :





Komentar

Posting Komentar

Postingan populer dari blog ini

TERMINOLOGI PADA POHON

-
Gambar
Pohon yang satu buah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah sehingga menjadi graf berarah dinamakan pohon berakar ( rooted tree ). 1.      Pohon berakar adalah pohon yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar. 2.     Akar mempunyai derajat masuk nol dan simpul-simpul lainnya berderajat masuk sama dengan satu. 3.     Daun atau simpul terminal adalah simpul yang mempunyai derajat keluar sama dengan nol. 4.     Simpul dalam atau simpul cabang adalah simpul yang mempunyai derajat keluar tidak sama dengan nol Terminologi pada Pohon Berakar 1.      Child atau children (Anak) dan parent (orangtua) 2.     Path (lintasan) 3.     Descendant (Keturunan) dan ancestor (leluhur) 4.     Sibling (saudara kandung) 5.  ...
Baca selengkapnya

FUNGSI

-
F U N G S I Definisi Fungsi Fungsi f adalah suatu relasi yang menghubungkan setiap anggota x dalam suatu  himpunan yang disebut daerah asal (Domain) dengan suatu nilai tunggal f(x) dari suatu himpunan kedua yang disebut daerah kawan (Kodomain).  Himpunan nilai yang diperoleh dari relasi tersebut disebut daerah hasil ( Range).  Untuk memberi nama suatu fungsi dipakai sebuah huruf tunggal seperti f, g, dan huruf  lainnya. Maka f(x), yang di baca “ f dari x “ menunjukkan nilai yang diberikan oleh f  kepada x. Misalkan : f(x) = x+ 2, maka f(3) = 3 + 2. Sifat Fungsi : 1) Fungsi f :A? B disebut fungsi INTO. Karena ada kodomain yang tidak berpasangan dengan domain. 2) Fungsi f :A? B disebut fungsi INJEKTIF. Karena setiap kodomain berpasangan tepat satu dengan domain. 3) Fungsi f:A? B disebut fungsi SUBJEKTIF. Karena setiap kodomain berpasangan dengan domain. 4) Fungsi f:A? B disebut fungsi BIJEKTIF. Karena sebuah fungsi bersifat injekti...
Baca selengkapnya