PENJELASAN LENGKAP MENGENAI GRAF POHON MUDAH DIPAHAMI

DOWNLOAD PDF DISINI

PENJELASAN LENGKAPP MENGENAI GRAF POHON MUDAH DIPAHAMI

Rinaldi M/IF2091 Strukdis 1
Pohon
Bahan Kuliah IF2091 Struktur Diskrit
Program Studi Teknik Informatika ITB
Rinaldi M/IF2091 Strukdis 2
Definisi
◼ Pohon adalah graf tak-berarah terhubung
yang tidak mengandung sirkuit
pohon pohon bukan pohon bukan pohon
a b
c d
e f
a b
c d
e f
a b
c d
e f
a b
c d
e f
Rinaldi M/IF2091 Strukdis
3
Hutan (forest) adalah - kumpulan pohon yang saling lepas, atau - graf tidak terhubung yang tidak mengandung sirkuit. Setiap
komponen di dalam graf terhubung tersebut adalah pohon.
Hutan yang terdiri dari tiga buah pohon
Rinaldi M/IF2091 Strukdis 4
Sifat-sifat (properti) pohon
• Teorema. Misalkan G = (V, E) adalah graf tak-berarah
sederhana dan jumlah simpulnya n. Maka, semua pernyataan
di bawah ini adalah ekivalen:
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.
• Teorema di atas dapat dikatakan sebagai definisi lain dari
pohon.
Rinaldi M/IF2091 Strukdis 5
Pohon Merentang (spanning tree)
• Pohon merentang dari graf terhubung adalah upagraf
merentang yang berupa pohon.
• Pohon merentang diperoleh dengan memutus sirkuit di
dalam graf.
G T1 T2 T3 T4
Rinaldi M/IF2091 Strukdis
6 • Setiap graf terhubung mempunyai paling sedikit satu buah
pohon merentang. • Graf tak-terhubung dengan k komponen mempunyai k buah
hutan merentang yang disebut hutan merentang (spanning
forest).
Rinaldi M/IF2091 Strukdis 7
Aplikasi Pohon Merentang
1. Jumlah ruas jalan seminimum mungkin yang
menghubungkan semua kota sehingga setiap kota tetap
terhubung satu sama lain.
2. Perutean (routing) pesan pada jaringan komputer.
(a) (b)
Router
Subnetwork
(a) Jaringan komputer, (b) Pohon merentang multicast
Rinaldi M/IF2091 Strukdis 8
Pohon Merentang Minimum
• Graf terhubung-berbobot mungkin mempunyai lebih dari 1
pohon merentang.
• Pohon merentang yang berbobot minimum –dinamakan pohon
merentang minimum (minimum spanning tree).
a
b
c

PENJELASAN LENGKAPP MENGENAI GRAF POHON MUDAH DIPAHAMI

d
e
f
g
h
55
5
40
25
45
30
50
20
15
35 10
a
b
c
d
e
f
g
h
5
40
25 30
20
15
10
Rinaldi M/IF2091 Strukdis
9
Algoritma Prim
Langkah 1: ambil sisi dari graf
G yang berbobot minimum,
masukkan ke dalam T.
Langkah 2: 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 3: ulangi langkah 2 sebanyak n – 2 kali.
Rinaldi M/IF2091 Strukdis 10
procedure Prim(input G : graf, output T : pohon)
{ Membentuk pohon merentang minimum T dari graf terhubungberbobot G.
Masukan: graf-berbobot terhubung G = (V, E), dengan V= n
Keluaran: pohon rentang minimum T = (V, E’) }
Deklarasi
i, p, q, u, v : integer
Algoritma
Cari sisi (p,q) dari E yang berbobot terkecil
T
 {(p,q)}
for i
1 to n-2 do
Pilih sisi (u,v) dari E yang bobotnya terkecil namun
bersisian dengan simpul di T
T
 T
 {(u,v)}
endfor
Rinaldi M/IF2091 Strukdis 11

PENJELASAN LENGKAPP MENGENAI GRAF POHON MUDAH DIPAHAMI

Contoh: 1 2 3 4 5 6
10
50
30 45
20
15
35
55
25
40
Rinaldi M/IF2091 Strukdis 12
Langkah Sisi Bobot Pohon rentang 1 (1, 2) 1 0 1 1 0 2 2 (2, 6) 2 5 1 2 6
1 0
2 5 3 (3, 6) 15 1 3 6
10
15
25 4 (4, 6) 20 1 2 3 4 6
10
20
15
25 5 (3, 5) 35 1 2 3 4 5 6
10
45
20
15
35
55
25
Rinaldi M/IF2091 Strukdis 13
Pohon merentang minimum yang dihasilkan:
Bobot = 10 + 25 + 15 + 20 + 35 = 105 1 2 3 4 5 6
10
45
20
15
35
55
25
Rinaldi M/IF2091 Strukdis 14
◼ Pohon merentang yang dihasilkan tidak
selalu unik meskipun bobotnya tetap sama.
◼ Hal ini terjadi jika ada beberapa sisi yang
akan dipilih berbobot sama.
Rinaldi M/IF2091 Strukdis 15
Contoh:
Tiga buah pohon merentang minimumnya: a b c d e f g h i j k l 3 2 4 2 3 5 4 4 2 4 a b c d e f h i j k l 3 2 4 2 3 5 3 4 4 24 a b c d e f g h i j k l 3 4 2 4 2 3 5 3 4 24 3
Bobotnya sama yaitu = 36 a b c d e f g h i j k l 356 5 3 5 4 4 2 4 4 4 2 2 3 6 4
Rinaldi M/IF2091 Strukdis 16
Algoritma Kruskal
( Langkah 0: sisi-sisi dari graf sudah diurut menaik berdasarkan
bobotnya – dari bobot kecil ke bobot besar)
Langkah 1: T masih kosong
Langkah 2: pilih sisi (u, v) dengan bobot minimum yang tidak
membentuk sirkuit di T. Tambahkan (u, v) ke dalam T.
Langkah 3: ulangi langkah 2 sebanyak n – 1 kali.
Rinaldi M/IF2091 Strukdis 17
procedure Kruskal(input G : graf, output T : pohon)
{ Membentuk pohon merentang minimum T dari graf terhubung –
berbobot G.
Masukan: graf-berbobot terhubung G = (V, E), dengan V= n
Keluaran: pohon rentang minimum T = (V, E’) }
Deklarasi
i, p, q, u, v : integer
Algoritma
( Asumsi: sisi-sisi dari graf sudah diurut menaik
berdasarkan bobotnya – dari bobot kecil ke bobot
besar)
T  {}
while jumlah sisi T < n-1 do
Pilih sisi (u,v) dari E yang bobotnya terkecil

PENJELASAN LENGKAPP MENGENAI GRAF POHON MUDAH DIPAHAMI

if (u,v) tidak membentuk siklus di T then
T
 T
 {(u,v)}
endif
endfor
Rinaldi M/IF2091 Strukdis 18
Contoh: 1 2 3 4 5 6
10
50
30 45
20
15
35
55
25
40
Rinaldi M/IF2091 Strukdis 19
Sisi-sisi diurut menaik:
Sisi (1,2) (3,6) (4,6) (2,6) (1,4) (3,5) (2,5) (1,5) (2,3) (5,6)
Bobot 10 15 20 25 30 35 40 45 50 55
Langkah Sisi Bobot Hutan merentang 1 (1, 2) 10 2 (3, 6) 15 3 (4, 6) 20 0 1 2 3 4 5 6 1 2 1 2 3 6 4 5 1 2 3 6 4 5 4 (2, 6) 25 1 2 3 4 5
Rinaldi M/IF2091 Strukdis 20
Pohon merentang minimum yang dihasilkan:
Bobot = 10 + 25 + 15 + 20 + 35 = 105 4 (2, 6) 25 1 2 3 4 5 5 (1, 4) 30 ditolak 6 (3, 5) 35 1 2 3 6 4 5 1 2 3 4 5 6
10

PENJELASAN LENGKAPP MENGENAI GRAF POHON MUDAH DIPAHAMI

45
20
15
35
55
25

Tweet

Postingan terkait:

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