PENJELASAN LENGKAP DAN MUDAH DIPAHAMI MENGENAI GRAF POHON BERAKAR PDF

DOWNLOAD PDF DISINI

PENJELASAN LENGKAP DAN MUDAH DIPAHAMI MENGENAI GRAF POHON BERAKAR


Rinaldi M/IF2091 Strukdis 1
Pohon berakar (rooted tree)
• Pohon yang satu buah simpulnya diperlakukan sebagai akar dan
sisi-sisinya diberi arah sehingga menjadi graf berarah
dinamakan pohon berakar (rooted tree).
(a) Pohon berakar (b) sebagai perjanjian, tanda panah pada sisi dapat
dibuang
a
b
c
d
e
f g
h i j
a
b
c
d
e
f g
h i j
Rinaldi M/IF2091 Strukdis
2
b sebagai akar e sebagai akar
Pohon dan dua buah pohon berakar yang dihasilkan dari pemilihan
dua simpul berbeda sebagai akar a b c d e f gh f g a bc d e f g h d e h b a c
Rinaldi M/IF2091 Strukdis 3
Terminologi pada Pohon Berakar
Anak (child atau children) dan Orangtua (parent)
b, c, dan d adalah anak-anak simpul a,
a adalah orangtua dari anak-anak itu
a
b
k

PENJELASAN LENGKAP DAN MUDAH DIPAHAMI MENGENAI GRAF POHON BERAKAR

g
j
f
c d
l m
i
e
h
Rinaldi M/IF2091 Strukdis
4
2. Lintasan (path)
Lintasan dari a ke j adalah a, b, e, j.
Panjang lintasan dari a ke j adalah 3.
3. Saudara kandung (sibling) f adalah saudara kandung e, tetapi g bukan
saudara kandung e, karena orangtua mereka
berbeda.
a
b
kg
j
f
c
d
l
m
i
e
h
Rinaldi M/IF2091 Strukdis 5
4. Upapohon (subtree)
a
b
k
g
j
f
c d
l m
i
e
h
Rinaldi M/IF2091 Strukdis
6
5. Derajat (degree)
Derajat sebuah simpul adalah jumlah upapohon (atau jumlah
anak) pada simpul tersebut.
Derajat a adalah 3, derajat b adalah 2,
Derajat d adalah satu dan derajat c adalah 0.
Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar.

PENJELASAN LENGKAP DAN MUDAH DIPAHAMI MENGENAI GRAF POHON BERAKAR

Derajat maksimum dari semua simpul merupakan derajat pohon itu
sendiri. Pohon di atas berderajat 3 a b kg j f c d l m i e h
Rinaldi M/IF2091 Strukdis 7
6. Daun (leaf)
Simpul yang berderajat nol (atau tidak mempunyai anak) disebut
daun. Simpul h, i, j, f, c, l, dan m adalah daun.
7. Simpul Dalam (internal nodes)
Simpul yang mempunyai anak disebut simpul dalam. Simpul b, d,
e, g, dan k adalah simpul dalam. a
b
k
g
j
f
c d
l m
i
e
h
Rinaldi M/IF2091 Strukdis
8
8. Aras (level) atau Tingkat
9. Tinggi (height) atau Kedalaman (depth)
Aras maksimum dari suatu pohon disebut tinggi atau kedalaman
pohon tersebut. Pohon di atas mempunyai tinggi 4. a b kg j f c d l m i e h 01234
Aras
Rinaldi M/IF2091 Strukdis 9
Pohon Terurut (ordered tree)
Pohon berakar yang urutan anak-anaknya penting disebut pohon
terurut (ordered tree).
(a) (b)
(a) dan (b) adalah dua pohon terurut yang berbeda
1
2
6 7 8
3
4
9
10
5
1
2

PENJELASAN LENGKAP DAN MUDAH DIPAHAMI MENGENAI GRAF POHON BERAKAR

8 6 7
3 4
9
10
5
Rinaldi M/IF2091 Strukdis 10
Pohon n-ary
• Pohon berakar yang setiap simpul cabangnya mempunyai
paling banyak n buah anak disebut pohon n-ary.
< sentence>

Tweet

Postingan terkait:

— Sunday, May 31, 2020 — Add Comment — matematika