Puspa Riri: 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 $G$ berikut.

—-INISIASI: ALGORITMA PRIM—–
Step 1: Pilih salah satu titik, misalnya titik a.
Step 2: Misalkan $T = \{a\}$ dan $F = \{b, c, d, e, f, g, h, i\}$ . Dengan meninjau keterhubungan langsung titik pada himpunan $F$ dengan titik pada himpunan $T$ , diperoleh
$a(-, -); b(a, 4)~\boxed{c(a, 3)}$
$d(a, 5)~e(-, -)~f(-, -)~g(-, -)~h(-, -)~i(-. -)$
Pilih titik $c(a, 3)$ (bobot c ke a adalah 3).
Tulis $T = \{a, c\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c\}$ dan $F = \{b, d, e, f, g, h, i\}$ . Gunakan prinsip yang sama.
Untuk selanjutnya, titik yang tidak terhubung langsung dengan titik-titik di $T$ tidak ditulis.
$c(a, 3); \boxed{b(a, 4)}~b(c,6)~d(a,5)~\boxed{d(c,4)}$
Ada 2 pilihan. Pilih salah satu, misalkan dipilih $b(a, 4)$ (bobot b ke a adalah 4).
Tulis $T = \{a, c, b\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b\}$ dan $F = \{d, e, f, g, h, i\}$
$b(a, 4); d(a,5)~\boxed{d(c,4)}$
Pilih $d(c, 4)$ (bobot d ke c adalah 4).
Tulis $T = \{a, c, b, d\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b, d\}$ dan $F = \{e, f, g, h, i\}$
$d(c, 4); ~\boxed{e(d, 2)}$
Pilih $e(d, 2)$ (bobot e ke d adalah 2).
Tulis $T = \{a, c, b, d, e\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b, d, e\}$ dan $F = \{f, g, h, i\}$
$e(d, 2); h(e,2)~\boxed{g(e, 1)}~f(e, 4)$
Pilih $g(e, 1)$ (bobot g ke e adalah 1).
Tulis $T = \{a, c, b, d, e, g\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—
Step 2: Misalkan $T = \{a, c, b, d, e, g\}$ dan $F = \{f, h, i\}$
$g(e, 1); \boxed{h(e, 2)}~f(e, 4)~h(g, 4)~\boxed{i(g, 2)}$
Ambil salah satu. Misal dipilih $h(e, 2)$ (bobot h ke e adalah 2).
Tulis $T = \{a, c, b, d, e, g, h\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b, d, e, g, h\}$ dan $F = \{f, i\}$
$h(e, 2); i(h,3)~\boxed{i(g, 2)}~f(e, 4)$
Pilih $i(g, 2)$ (bobot i ke g adalah 2).
Tulis $T = \{a, c, b, d, e, g, h, i\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b, d, e, g, h, i\}$ dan $F = \{f\}$
$i(g, 2); \boxed{f(i,3)}~f(e, 4)$
Pilih $f(i, 3)$ (bobot f ke i adalah 3).
Tulis $T = \{a, c, b, d, e, g, h, i, f\}$
Step 3: Semua titik berada pada himpunan $T$ . Beri pesan: $T = \{a, c, b, d, e, g, h, i, f\}$ adalah pohon rentang minimal dengan bobot $3 + 4 + 4 + 2 + 1 + 2 + 2 + 3 + 3 = 24$
—ALGORITMA SELESAI—–

Puspa Riri

Sabtu, 02 Juni 2018

POHON (TREE) MATEMATIKA DISKRET

Sifat-sifat Pohon

Tidak ada komentar:

Posting Komentar