Tree and Path
1. Path
Pembahasan mengenai Path
2
Path
◍ Sebuah graph G dikatakan connected jika setidaknya terdapat
sebuah path yang menghubungkan setiap pasang vertex pada
graph tsb.
◍ Disebut disconnected jika sebaliknya. Dan sebuah disconnected
graph akan memiliki 2 atau lebih component.
2
◍ Contoh : 5
1 4
6
3 8 7
Path
◍ Sebuah walk (W) didefinisikan sebagai urutan (tdk
nol) vertex & edge. Diawali origin vertex dan diakhiri
terminus vertex. Dan setiap 2 edge berurutan adalah
series. Contoh, W = A1B3C4B1A2
◍ Walk dengan setiap edge berbeda adalah trail. Contoh,
T = C4B3C7E
◍ Walk dengan setiap vertex berbeda adalah path.
Contoh, P = D5B4C2A
◍ Walk dengan origin dan terminus identik adalah
cycle/circuit. Atau, cycle adalah sebuah closed walk.
Contoh, C = A1B3C7E8B1A
Contoh Path
◍ Tinjau graph G1: Panjang lintasan adalah
lintasan 1, 2, 4, 3 adalah jumlah sisi dalam lintasan
lintasan dengan barisan tersebut.
sisi (1,2), (2,4), (4,3). Lintasan 1, 2, 4, 3 pada G1
memiliki panjang 3.
2. CYCLE ATAU CIRCUIT
Pembahasan mengenai Cycle atau
Circuit
Cycle atau Circuit
Tinjau graph G1:
Lintasan yang berawal dan 1, 2, 3, 1 adalah sebuah
berakhir pada simpul yang sirkuit.
Sirkuit 1, 2, 3, 1 pada G1
sama disebut sirkuit atau memiliki panjang 3.
siklus.
Panjang sirkuit adalah
jumlah sisi dalam sirkuit
tersebut.
3. Tree
Pembahasan mengenai Tree
Pengertian
◍ Pohon (Tree) didefinisikan sebagai
graph terhubung yang tidak
mengandung sirkuit atau cycle.
◍ Hutan (Forest) adalah graf yang tidak
mengandung sirkuit.
◍ Pohon adalah hutan yang terhubung.
Pengertian
◍ Daun adalah titik di dalam Pohon yang
berderajat 1.
◍ Titik dalam Pohon yang berderajat > 1
disebut Titik Cabang.
◍ Suatu pohon dengan n titik memiliki (n-
1) garis.
10
Pengertian
◍ Suatu Graf G adalah Pohon jika dan
hanya jika terdapat satu dan hanya satu
jalur diantara setiap pasang simpul dari
Graf G.
◍ Jika acyclic graph adalah sebutan untuk
graph yang tidak memiliki cycle di
dalamnya, maka tree adalah connected
acyclic graph. 11
Contoh Penggambaran Tree
Aneka tree dengan 6 vertex
12
Teorema Tree
◍ Suatu Graf G dengan n buah simpul
adalah Pohon jika :
○ G terhubung dan tak mengandung sirkuit, atau
○ G tidak mengandung sirkuit dan mempunyai n - 1
buah ruas, atau
○ G mempunyai n - 1 buah ruas dan terhubung
Jenis Tree
Pohon Rentangan
(Spanning Tree)
Pohon Berakar (Rooted
Tree)
Pohon Biner (Binary Tree)
Pohon Terurut (Ordered
Tree)
14
“
Pohon Rentangan (Spanning Tree)
15
Spanning Tree
◍ Suatu pohon rentangan atau spanning tree adalah
suatu subgraf dari graf G yang mengandung semua
simpul dari G dan merupakan suatu pohon.
Spanning Tree
◍ Karena pohon dengan n simpul memuat
(n-1) sisi, maka untuk mendapatkan
spanning tree dari suatu graph
terhubung G dengan n simpul dan q sisi
dilakukan dengan cara menghapus (q-
n+1) sisi.
17
Contoh Spanning Tree
Contoh Spanning Tree
◍ Graf G ◍ Spanning Tree dari Graf G
Minimal Spanning Tree
◍ Apabila G suatu Graf berbobot (Suatu
Network), maka pohon rentangan
minimal dari graf adalah pohon
rentangan dengan jumlah bobot terkecil.
◍ Untuk mendapatkan pohon rentangan
minimal dapat digunakan Algoritma:
○ Solin
○ Kruskal
○ Prim’s
“
Pohon Berakar (Rooted Tree)
21
Pohon Berakar (Rooted Tree)
◍ Pohon berakar (Rooted Tree) adalah
pohon yang satu buah simpulnya
diperlakukan sebagai akar dan sisi-sisinya
diberi arah sehingga menjadi graf berarah.
◍ Suatu pohon berakar R adalah suatu
pohon bersama dengan suatu simpul r
yang dirancang/ditunjuk sebagai akar
(root) dari R.
◍ Pohon berakar adalah graf berarah
(digraf) T yang mempunyai dua syarat,
yaitu :
○ Bila arah sisi-sisi pada T diabaikan, hasil graf
tidak berarahnya merupakan sebuah pohon.
○ Ada titik tunggal R sedemikian hingga derajat
masuk R adalah 0 dan derajat masuk sembarang
titik lainya adalah 1. Titik R disebut akar dari
pohon berakar.
23
Rooted Tree
◍ Contoh :
◍ Hanya terdapat satu jalur antara r dengan simpul
lain v pada pohon pohon tersebut.
◍ Panjang jalur antara r dengan simpul v disebut
level atau kedalaman simpul v.
◍ Simpul bukan akar, yang berderajat satu disebut
daun.
◍ Jalur antara suatu simpul dengan suatu daun
disebut cabang (branch).
25
Rooted Tree
◍ Suatu pohon berakar dapat digunakan
untuk menelusuri semua kemungkinan
dari kejadian, dengan masing-masing
kejadian dapat muncul dalam sejumlah
hingga cara.
Terminologi Pohon Berakar
Saudara
Anak (Child atau Orangtua
Lintasan (Path) Kandung
Children) (Parent)
(Sibling)
Upapohon Simpul Dalam
Derajat (Degree) Daun (Leaf)
(Subtree) (Internal Nodes)
Tinggi (Height)
Aras (Level) atau
atau Kedalaman
Tingkat
(Depth)
27
Terminologi Pohon Berakar
◍ Child
○ Child atau anak adalah simpul setelah suatu
simpul dalam pohon
◍ Parent
○ Parent atau orang tua adalah simpul sebelum
suatu simpul lain dalam satu pohon
◍ Sibling
○ Sibling atau Saudara kandung adalah simpul yang
mempunyai orangtua yang sama.
28
Terminologi Pohon Berakar
◍ Lintasan
○ Lintasan adalah jalur yang harus ditempuh dari
suatu simpul ke simpul lainnya, panjang lintasan
ditentukan dari simpul asal.
◍ Derajat
○ Sebuah simpul adalah jumlah upapohon (atau
jumlah anak) pada simpul tersebut
○ Derajat maksimum dari semua simpul merupakan
derajat pohon itu sendiri.
29
Terminologi Pohon Berakar
◍ Subtree
○ Upapohon atau subtree adalah pohon yang
dibentuk dengan memotong pohon yang sudah
ada
◍ Daun
○ Adalah simpul yang berderajat nol (atau tidak
mempunyai anak).
◍ Simpul dalam
○ Adalah simpul yang mempunyai anak.
30
Terminologi Pohon Berakar
◍ Aras
○ Level dari pohon
◍ Tinggi atau kedalaman pohon
○ Adalah aras maksimum dari suatu pohon
31
Contoh Pohon Berakar
Aras 0
◍ Diketahui :
○ a adalah orangtua dari b, c dan d
Aras 1
○ b, c, dan d adalah anak-anak simpul a
○ b adalah saudara kandung c dan d
○ e bukan saudara kandung g Aras 2
○ h, i, j, f, c, l, dan m adalah daun
Aras 3
○ b, d, e, g, dan k adalah simpul dalam
○ lintasan dari a ke j adalah a, b, e, j dan
panjang lintasan dari a ke j adalah 3. Aras 4
○ Tinggi pohon adalah 4
32
“
Pohon Biner (Binary Tree)
33
Pohon Biner (Binary Tree)
◍ Pohon Biner adalah pohon berakar yang
setiap titiknya memiliki paling banyak
dua anak dan setiap anak ditunjuk
sebagai anak kiri dan anak kanan.
◍ Pohon biner digunakan dalam ilmu
computer untuk mengolah data.
34
Pohon Biner (Binary Tree)
◍ Pada pohon biner setiap titik mungkin
memiliki 1 atau 2 anak. Anak kiri
digambarkan disebelah kiri dan dibawah
orang tuanya, serta anak kanan
disebelah kanan dibawah orang tuanya.
◍ Pohon biner memiliki akar (root), dan
tree di bawahnya disebut dengan
subtree kiri dan subtree kanan. 35
Pohon Biner (Binary Tree)
◍ Akar dari subtree merupakan successor
bagi root tree sehingga menjadi left
successor dan right successor.
◍ Sebarang node dalam pohon biner akan
mempunyai 0 atau 1 atau 2 buah
successor, sedangkan untuk node yang
tidak mempunyai successor dinamakan
terminal node. 36
Contoh Pohon Biner
37
Terminologi Pohon Biner
◍ Similar
○ Dua buah tree dikatakan
Similar jika keduanya
mempunyai struktur
(bentuk) yang sama.
38
Jenis Binary Tree
◍ Complete Binary Tree
○ Sebuah tree dikatakan Complete
Binary Tree jika semua level
(kecuali level terakhir)
mempunyai jumlah node
maksimum (2r) dan bila semua
simpul pada tingkat terakhir
muncul dibagian kiri pohon.
Untuk setiap level r mempunyai
paling banyak 2r node.
39
Terminologi Pohon Biner
◍ Extanded Binary Tree : 2-tree
○ Sebuah binary tree T dikatakan sebagai 2-tree atau Extanded
Binary Tree jika setiap node N mempunyai 0 atau 2 buah
Child.
○ Node dengan 2 buah Child dikatakan internal node.
○ Node dengan o Child dikatakan external node.
○ Aplikasi 2-tree digunakan untuk menyajikan suatu ekspresi
aritmatik yang mengandung operasi biner.
○ External node digunakan untuk menyajikan operand dan
Internal node digunakan sebagai operator yang bekerja
terhadap 2 suppohon. 40
Penelusuran Pohon Biner
Preorder Inorder Postorder
Telusuri cabang Telusuri cabang
Kunjungi akar kiri kiri
Telusuri cabang Telusuri cabang
kiri Kunjungi akar kanan
Telusuri cabang Telusuri cabang
kanan kanan Kunjungi akar
41
Contoh Penelusuran Pohon Biner
◍ 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
42
“
Pohon Terurut (Ordered Tree)
43
Pohon terurut (Ordered Tree)
◍ Pohon terurut (Ordered Tree) adalah pohon berakar
yang urutan anak-anaknya penting.
◍ Dalam hal ini urutan bisa di definisikan sendiri.
◍ Hutan adalah graf tanpa sirkuit.
◍ Titik Terminal adalah titik dengan derajat keluar 0.
◍ Titik Internal adalah titik yang memiliki derajat
keluar yang tidak nol
44
Contoh Pohon Terurut
45
4. Teorema Pohon
Pembahasan mengenai Algoritma
Pohon Berakar
Teorema 1
◍ Bila (T,V0) adalah pohon
berakar (T adalah relasi dan V0
adalah akar) maka:
○ Tidak ada siklus dalam T
■ Gambar di samping
bukanlah suatu pohon
berakar karena ada suatu
siklus dari V0 - V2 - V3
kembali ke V0.
Teorema 1
◍ V0 merupakan satu-
satunya akar dari T
◍ Tidak ada akar selain V0
pada suatu pohon.
○ Gambar di samping
bukanlah pohon berakar
karena mempunyai 2 akar
pohon yaitu V0 dan V1.
48
Teorema 1
◍ Tiap simpul di T kecuali V0
memiliki derajat masuk satu
sedangkan V0 berderajat
masuk 0.
◍ Gambar di samping
bukanlah suatu pohon
berakar karena akarnya (V0)
berderajat masuk 1 dan ada
simpul lain yang berderajat
masuk 2 yaitu V4. 49
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).
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.
50
Teorema 2
◍ Gambar di
samping
bukanlah
pohon berakar
karena simpul
V5 berelasi
dengan dirinya
sendiri.
51
Teorema 2
◍ Gambar di
samping bukan
pohon berakar
karena V2 dan V5
berelasi bolak-
balik.
52
Teorema 3
◍ Bila (T, vo) adalah
pohon berakar dan v
∈ T maka :
○ T(v) juga pohon
berakar dengan akar v.
○ T(v) juga subtree dari T
dengan awal v.
53
4. Algoritma Pohon Merentang
Pembahasan mengenai Algoritma
Pohon Merentang (Spanning Tree)
Algoritma yang Digunakan untuk
Menentukan Pohon Merentang Minimum
Algoritma
Solin
Algoritma
Prim
Algoritma
Kruskal
Konsep Algoritma Sollin
◍ Algoritma Sollin diturunkan dari
algoritma Borůvka
◍ Algoritma Sollin menentukan pohon
merentang minimum dengan cara
melakukan penghapusan sisi-sisi yang
tidak menyebabkan graf menjadi tidak
terhubung atau membentuk sirkuit.
56
Konsep Algoritma Sollin
◍ Penghapusan tersebut dimulai dari sisi
atau busur yang memiliki bobot terbesar
hingga terkecil.
◍ Penghapusan dilakukan setelah
sebelumnya sisi-sisi pada graf diurutkan
berdasarkan bobotnya dari besar ke
kecil.
57
Cara Penggunaan Algoritma Sollin
◍ Algoritma Sollin dapat dituliskan secara
terurut sebagai berikut :
○ Urutkan sisi-sisi pada graf berdasarkan bobotnya
dari besar ke kecil, misalkan jumlah sisinya n
○ Lakukan penghapusan setiap sisi yang tidak
menyebabkan graf menjadi tidak terhubung
sampai didapat n – 1 sisi yang tersisa
Pseudo Code Algoritma Sollin
59
Contoh Soal
◍ Graf G : ◍ Ini adalah graf berbobot awal.
◍ Graf ini bukan pohon karena ada
sirkuit.
◍ Nama yang lebih tepat untuk diagram
ini adalah Graf atau Network.
◍ Angka-angka dekat garis
penghubung/ruas adalah bobotnya.
◍ Nilai bobot dari Graf tesebut adalah :
86
Penyelesaian dengan Algoritma Solin
◍ Urutkan Ruas Graf (G) menurut
bobotnya dari bobot yang terbesar
sampai bobot yang terkecil
Penyelesaian dengan Algoritma Solin
◍ Bobot : 15 -> D,E ◍ Bobot : 9 -> B,D dan E,F
◍ Ruas D,E tidak dihapus ◍ Ruas B,D dan E,F tidak dihapus
karena ruas tersebut karena kedua ruas tersebut
menghubungkan D dan E menyebabkan graf terhubung
Penyelesaian dengan Algoritma Solin
◍ Bobot : 8 -> B,C,B,E dan F,G ◍ Bobot : 7 -> A,D dan C,E
◍ Ruas B,C dan F,G tidak ◍ Ruas A,D tidak dihapus.
dihapus. ◍ Ruas C,E dihapus, karena
◍ Ruas B,E dihapus, karena membentuk sirkuit (D,B,C,E,D)
membentuk sirkuit (B,D,E,B)
Penyelesaian dengan Algoritma Solin
◍ Bobot : 6 -> A,B dan E,G ◍ Bobot : 5 -> D,F
◍ Ruas D,F dihapus karena membentuk
◍ Ruas A,B dan E,G dihapus sirkuit (D,E,F,D)
karena membentuk sirkuit ◍ Tahap Penghapusan Selesai, Gambar 6
(A,B,D,A) dan (E,F,G,E) adalah Minimun Spanning Tree dari Graf
G dengan Nilai Bobot : 56
Konsep Algortima Kruskal
◍ Algortima Kruskal adalah salah satu
algortima dasar yang dapat digunakan untuk
menentukan pohon merentang minimum
dengan cara menurutkan terlebih dahulu sisi-
sisi graf dari kecil ke besar.
◍ Kemudian, secara berulang sisi yang
memiliki bobot terkecil dan tidak membentuk
siklus di T dimasukkan ke himpunan T. 65
Cara Penggunaan Algoritma Kruskal
◍ Algoritmanya dapat disusun ke dalam langkah-langkah
terurut sebagai berikut
Langkah 1 Langkah 2 Langkah 3
• Urutkan sisi-sisi • Pilih sisi (u, v) • Ulangi langkah 2
graf dari kecil ke dengan bobot sebanyak n-1 kali
besar. T minimum yang
merupakan tidak membentuk
himpunan kosong sirkuit di T.
Masukkan ke
dalam T
66
Pseudo Code Algoritma Kruskal
Contoh Soal
◍ Graf G : ◍ Ini adalah graf berbobot awal.
◍ Graf ini bukan pohon karena ada
sirkuit.
◍ Nama yang lebih tepat untuk diagram
ini adalah Graf atau Network.
◍ Angka-angka dekat garis
penghubung/ruas adalah bobotnya.
◍ Nilai bobot dari Graf tesebut adalah :
86
Penyelesaian dengan Algoritma Kruskal
◍ Mula-mula kita buat Graf G hanya terdiri
dari Simpul saja.
Penyelesaian dengan Algoritma Kruskal
◍ Urutkan Ruas dari bobot kecil ke besar
(DF, AB, EG, AD, CE, BC, BE, FG, BD,
EF,DE), kemudian berdasarkan urutan
tersebut, kita menambahkan ruas
dengan mencegah terbentuknya sirkuit.
Penyelesaian dengan Algoritma Kruskal
71
Penyelesaian dengan Algoritma Kruskal
Penyelesaian dengan Algoritma Kruskal
Penyelesaian dengan Algoritma Kruskal
Penyelesaian dengan Algoritma Kruskal
Penyelesaian dengan Algoritma Kruskal
Algoritma Prim’s
◍ Algoritma Prim merupakan algoritma untuk
mencari pohon merentang minimum dari sebuah
graf berbobot langkah demi langkah dengan
mengambil sisi atau busur dari graf yang
mempunyai bobot minimum kemudian mengulang
proses yang sama (mengambil sisi yang berbobot
minimum) yang tidak membentuk sirkuit.
77
Algoritma Prim’s
◍ Adalah pengembangan algoritma Kruskal
ditambah dengan menjaga graf agar tetap
terhubung
◍ Contoh :
Algoritma Prim’s
• Ambil sisi dari graf G
Langkah 2 • Ulangi langkah 2
yang berbobot minimum, sebanyak n – 2 kali.
masukkan ke dalam T. • Pilih sisi (u, v) yang
mempunyai bobot
minimum dan bersisian
dengan simpul di T, tetapi
(u, v) tidak membentuk
sirkuit di T. Masukkan (u,
v) ke dalam T.
Langkah 1 Langkah 3
79
THANK YOU
80