pohon : matematika diskrit

POHON (TREE) MATEMATIKA DISKRET

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.
• Pohon (tree) adalah merupakan graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. Diagram pohon dapat digunakan sebagai alat untuk memecahkan masalah dengan menggambarkan semua alternative  pemecahan.

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 

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

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 :

T₁, T₂, T₃, T₄ ® merupakan spanning tree dari G

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

Contoh   :

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   :

CONTOH:

Gunakan Algoritma Prim untuk mendapatkan pohon rentang minimal dari graf berikut.

—-INISIASI: ALGORITMA PRIM—–
Step 1: Pilih salah satu titik, misalnya titik a.
Step 2: Misalkan  dan . Dengan meninjau keterhubungan langsung titik pada himpunan  dengan titik pada himpunan , diperoleh


Pilih titik  (bobot c ke a adalah 3).
Tulis 
Step 3: Tidak semua titik berada pada himpunan , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan  dan . Gunakan prinsip yang sama.
Untuk selanjutnya, titik yang tidak terhubung langsung dengan titik-titik di  tidak ditulis.

Ada 2 pilihan. Pilih salah satu, misalkan dipilih  (bobot b ke a adalah 4).
Tulis 
Step 3: Tidak semua titik berada pada himpunan , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan  dan 

Pilih  (bobot d ke c adalah 4).
Tulis 
Step 3: Tidak semua titik berada pada himpunan , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan  dan 

Pilih  (bobot e ke d adalah 2).
Tulis 
Step 3: Tidak semua titik berada pada himpunan , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan  dan 

Pilih  (bobot g ke e adalah 1).
Tulis 
Step 3: Tidak semua titik berada pada himpunan , berarti kembali ke step 2.
—-ITERASI—
Step 2: Misalkan  dan 

Ambil salah satu. Misal dipilih  (bobot h ke e adalah 2).
Tulis 
Step 3: Tidak semua titik berada pada himpunan , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan  dan 

Pilih  (bobot i ke g adalah 2).
Tulis 
Step 3: Tidak semua titik berada pada himpunan , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan  dan 

Pilih  (bobot f ke i adalah 3).
Tulis 
Step 3: Semua titik berada pada himpunan . Beri pesan: adalah pohon rentang minimal dengan bobot