8. graf, diagram pohon dan aplikasinya

5/14/2018 8. Graf, Diagram Pohon Dan Aplikasinya - slidepdf.com

http://slidepdf.com/reader/full/8-graf-diagram-pohon-dan-aplikasinya-55a92fa74f39e 1/36

8. Graf, Diagram Pohon dan

Aplikasinya

Pengantar

Definisi. Suatu graf sederhana G=(V , E ) terdiri dari himpunan tak kosong dari simpul (vertex)

V , dan himpunan pasangan tak berurut anggota berlainan dari V yang disebut sebagai garis

hubung (edge) E .

Graf sederhana mirip seperti graf berarah, tetapi arah garis hubungnya tidak ditentukan (tidak

memiliki arah). Kadangkala kita ingin memodelkan berbagai hubungan antar simpul yang

tidak mungkin dilakukan dengan graf sederhana. Pada kasus ini, kita harus memakai

multigraf .

Definisi. Suatu multigraf G=(V , E ) terdiri dari himpunan simpul V , himpunan garis hubung E ,

dan sebuah fungsi f dari E ke {{u, v} | u, v ∈ V , u ≠ v}.

Garis hubung e1 dan e2 disebut garis hubung ganda atau garis hubung sejajar jika f (e1)= f (e2).

Catatan:

• Garis hubung dalam multigraf tidak perlu didefinisikan sebagai pasangan, tapi bisa

berjenis apapun.

• Loop tidak diperbolehkan di dalam multigraf (u ≠ v).

Contoh 8.1: Suatu multigraf G dengan simpul V ={a, b, c, d }, garis hubung {1, 2, 3, 4, 5} dan

fungsi f dengan f (1)={a, b}, f (2) = {a, b}, f (3) = {b, c}, f (4) = {c, d } dan f (5) = {c, d } dapatdigambarkan sebagai berikut.

aa bb cc dd

11

22

33

44

55

8. Graf, Diagram Pohon dan Aplikasinya - 1



Untuk mengantisipasi keberadaan loop didalam graf, kita perlu mendefinisikan graf berjenis

berikut ini.

Definisi. Suatu pseudograf G=(V , E ) terdiri dari himpunan simpul V , himpunan garis hubung

E , dan fungsi f dari E ke {{u, v} | u, v ∈ V }.

Suatu garis hubung disebut loop jika f (e) = {u, u} untuk suatu u∈V .

Definisi. Suatu graf berarah G=(V , E ) terdiri dari himpunan simpul V dan himpunan garis

hubung E yaitu pasangan berurut anggota V .

Definisi. Suatu multigraf berarah G=(V , E ) terdiri dari himpunan simpul V , himpunan garis

hubung E , dan fungsi f dari E ke {(u, v) | u, v ∈ V}.

Garis hubung e1 dan e2 disebut sebgai garis hubung ganda jika f (e1) = f (e2).

Contoh 8.2: Suatu multigraf berarah G dengan simpul V ={a, b, c, d }, garis hubung {1, 2, 3, 4,

5} dan fungsi f dimana f (1) = (a, b), f (2) = (b, a), f (3) = (c, b), f (4) = (c, d ) dan f (5) = (c, d )

digambarkan sebagai berikut.

aa bb cc dd

11

22

33

44

55

Risalah dari beberapa jenis graf dan sifat-sifatnya diiberikan pada tabel berikut ini.

No Jenis Garis hubung? Ada Grs. Hub. Ganda? Ada Loop?

1 Graf Sederhana Tak berarah Tidak Tidak

2 Multigraf Tak berarah Ya Tidak

3 Pseudograf Tak berarah Ya Ya

4 Graf Berarah Berarah Tidak Ya

5 Multigraf Berarah Berarah Ya Ya




Model dari Graf

Contoh 8.3: Bagaimana cara menyatakan jaringan (dua arah) Kerta Api yang

menghubungkan sekumpulan kota? Kita harus memakai graf sederhana dengan garis hubung{a, b} merupakan jalur langsung yang menghubungkan kota a dengan kota b.

BBaanndduunngg

JJaakkaarrttaa

TTaassiikkmmaallaayyaa

PPoonnoorrooggoo CCiirreebboonn

MMaaddiiuunn

Contoh 8.4: Di dalam suatu turnamen sepakbola, setiap tim bertanding dengan tim lain tepat

satu kali. Bagaimana cara merepresentasikan hasil turnamen (suatu tim mengalahkan tim

lain)? Kita harus menggunakan graf berarah dengan garis hubung (a, b) menunjukkan tim a mengalahkan tim b.

RReeaall MMaaddrriidd JJuuvveennttuuss

Beberapa Terminologi dalam Graf

Definisi. Dua buah simpul, u dan v, dalam graf tak berarah G disebut berdekatan (atau

bertetangga) dalam G jika {u, v} adalah suatu garis hubung dalam G.

PPeerrssiibb AACC MMiillaann




Jika e = {u, v}, garis hubung e disebut sebagai incident dengan simpul u dan v, atau disebut

juga menghubungkan u dengan v. Simpul u dan v disebut juga titik ujung (endpoints) dari

garis hubung {u, v}.

Definisi. Derajat dari suatu simpul pada graf tak berarah adalah banyaknya garis hubung

yang berasal dari- /berakhir ke- simpul tersebut, kecuali loop di dalam simpul yang

menyumbang derajat simpul sebanyak dua.

Dengan kata lain, derajat dari simpul dapat ditentukan secara sederhana, yaitu dengan

menghitung banyaknya garis yang menyentuh simpul tersebut. Derajat dari suatu simpul v

dituliskan sebagai deg(v). Simpul dengan derajat nol disebut sebagai simpul yang terisolasi,

karena tidak terhubung (adjacent ) dengan simpul lain manapun.

Catatan: Suatu simpul yang memiliki loop setidaknya akan berderajat 2 dan, perdefinisi,

tidak terisolasi, meski dia tidak terhubung ke simpul yang lain. Simpul berderajat satu disebut

sebagai simpul yang tergelantung ( pendant ). Simpul ini terhubung dengan tepat satu buah

simpul lainnya.

Contoh 8.5: Diantara graf berikut, manakah simpul yang terisolasi, yang tergelantung, dan

berapakah derajat maksimumnya? Tentukan juga jenis dari graf?

aa

bb cc

dd

ii hh

gg

j j ff

ee

Jawab: Simpul f terisolasi, dan simpul a, d, dan j tergelantung. Derajat maksimum adalah

deg(g)=5. Graf tersebut merupakan pseudograf (tak berarah, loop).

Contoh 8.6 : Amati graf yang sama dan tentukan banyaknya garis hubung dan jumlah dariderajat semua simpulnya.




Jawab : Ada 9 garis hubung, dan jumlah seluruh derajat simpulnya adalah 18. Penjelasannya:

setiap garis hubung baru menambah hasil penjumlahan derajat sebanyak dua (2×9=18).

Teorema Handshaking. Misalkan G = (V , E ) suatu graf tak berarah dengan garis hubung e.

Maka

( )2 degv V

e v∈

= ∑

Catatan: Teorema ini tetap berlaku meskipun pada graf terdapat garis hubung ganda maupun

loop ganda.

Contoh 8.7 : Ada berapa garis hubungkah dalam suatu graf yang memiliki 6 simpul, yang

masing-masing simpulnya berderajat 10?

Jawab: Jumlah seluruh derajat simpul adalah 6⋅10=60. Menurut teorema handshaking, maka

2e=60 sehingga e = 30. Jadi akan ada 30 buah garis hubung.

Teorema. Suatu graf yang tak berarah, akan selalu memiliki simpul berderajat ganjil dengan

jumlah genap.

Ide: Ada tiga kemungkinan untuk menambahkan garis hubung untuk menyambung dua

simpul dalam graf, yakni.

Sebelum Sesudah

Kedua simpul berderajat genap ⇒ Kedua simpul berderajat ganjil

Kedua simpul berderajat ganjil ⇒ Kedua simpul berderajat genap

Satu simpul berderajat ganjil, yang

lainnya berderajat genap⇒ Satu simpul berderajat genap, yang

lainnya berderajat ganjil

Ada dua kemungkinan menambahkan suatu loop ke simpul dalam graf , yakni




Sebelum Sesudah

Simpul berderajat genap ⇒ Simpul berderajat genap

Simpul berderajat ganjil ⇒ Simpul berderajat ganjil

Jadi, jika dalam graf ada sejumlah genap simpul berderajat ganjil, hasil penambahan garis

hubung masih saja menghasilkan simpul berjumlah genap. Maka, karena suatu graf tak

berarah tanpa garis hubung memiliki sejumlah genap simpul berderajat ganjil (nol), hal yang

sama berlaku untuk sebarang graf tak berarah. Bukti dapat dipelajari dari buku referensi.

Definisi. Jika (u, v) suatu garis hubung dari graf dengan garis hubung berarah G, u disebut

terhubung ke (adjacent to) v, dan v dikatakan terhubung dari (adjacent from) u.

Simpul u disebut sebagai simpul awal (initial vertex) dari (u,v), dan v disebut sebagai simpul

akhir (terminal vertex) dari (u,v). Simpul awal dan simpul akhir dari suatu loop adalah sama.

Definisi. Dalam graf dengan garis hubung berarah, derajat kedalam (in-degree) dari simpul v,

dituliskan sebagai deg-(v), adalah banyaknya garis hubung dengan v sebagai simpul akhirnya.

Derajat keluar (out-degree) dari v, dituliskan sebagai deg+(v), adalah banyaknya garis hubung

dengan v sebagai simpul awalnya.

Bagaimana perubahan derajat keluar dan kedalam suatu simpul terhadap penambahan suatu

loop ke simpul tsb? Penambahan ini meningkatkan baik derajat keluar maupun kedalam dari

simpul yang bersangkutan sebesar satu.

Contoh 8.8: Berapakah derajat keluar dan kedalam dari simpul a, b, c, d pada graf berikut?

aa bb

cc dd

ddeegg--((aa)) == 11

ddeegg++((aa)) == 22

ddeegg--((bb)) == 44

ddeegg++((bb)) == 22

ddeegg

--

((dd)) == 22 ddee == 11 dd

ee

gg--

((cc))

==

00

ddee++dd

++cc == 22




Teorema. Misalkan G = (V , E ) graf dengan garis hubung berarah, maka:

( ) ( )deg degv V v V v v

− +

∈ ∈= =∑ ∑ E

Ini mudah diperiksa, sebab setiap penambahan garis hubung baru akan meningkatkan baik

derajat kedalam maupun derajat keluar sebanyak satu.

Graf-Graf Khusus

Definisi: Graf lengkap (complete graph) pada n buah simpul, dituliskan sebagai K n, adalah

graf sederhana yang mengandung tepat satu garis hubung antara dua simpul yang berbeda.

KK11 KK22 KK33 KK44 KK55

Definisi. Siklus (cycle) C n, n≥3, terdiri atas n buah simpul v1, v21, …, vn dan garis hubung

{v1,v2}, { v1, v3}, …, { vn-1, vn}, { vn, v1}.

CC33 CC44 CC55 CC66

Definisi. Pemberian satu simpul tambahan pada suatu siklus C n, n ≥ 3, dan lalu

menghubungkan simpul tsb ke setiap simpul pada C n dengan garis hubung baru akan

menghasilkan roda (wheel).




WW33 WW44 WW55 WW66

Definisi. Kubus-n (n-cube) dituliskan sebagai Qn adalah graf yang simpulnya merepresen-

tasikan string 2n

bit sepanjang n. Dua simpul terhubung jika dan hanya jika bit string yang

direpresentasikannya berbeda tepat satu bit.

Definisi. Suatu graf sederhana G disebut bipartite jika himpunan simpul V -nya dapat

dipartisi menjadi dua himpunan tak kosong yang tak beririsan V 1 dan V 2 sedemikian hingga

setiap garis hubung dalam graf menghubungkan suatu simpul di V 1 dengan simpul di V 2

(sedemikian hingga tak ada garis hubung di dalam G menghubungkan dua simpul di V 1

maupun di V 2).

Sebagai conoth, tinjau suatu graf yang merepresen-tasikan setiap penduduk di suatu desa

dengan simpul dan setiap pernikahan dengan garis hubung. Graf ini bipartite, karena setiap

garis hubung menghubungkan simpul dalam himpunan bagian penduduk pria dengan simpul

didalam himpunan bagian penduduk wanita (dalam pernikahan tradisional).

QQ11 QQ22 QQ33

00 11

0000 0011

1111 1100

000000 000011

110011 110000

001100 001111

111111 111100




Contoh 8.9: Apakah C 3 bipartite?

Tidak, sebab tidak ada cara mem-partisi simpul menjadi dua

himpunan sedemikian hingga tidak ada garis hubung dengan

kedua titik akhir di himpunan yang sama.

vv11

vv22 vv33

Contoh 8.10: Apakah C 6

bipartite?

Ya, sebab C 6 bisa ditampilkan

sebagai berikut:

Definisi. Graf bipartite lengkap K m,n adalah graf yang himpunan simpulnya dipartisi kedalam

dua himpunan bagian, masing-masing dengan m dan n buah simpul. Dua simpul terhubung

jika dan hanya jika mereka berada di himpunan bagian yang berbeda.

Operasi Pada Graf

Definisi. Suatu subgraf dari graf G = (V, E) adalah graf H = (W, F) dimana W⊆V dan F⊆E.

Catatan: Tentu saja H adalah graf yang valid, sehingga kita tidak bisa membuang titik ujung

dari garis hubung yang tersisa saat kita membentuk H.

KK33,,44

vv55

vv11

vv22

vv33 vv44

vv66 vv11 vv66

vv22 vv55

vv33 vv44

KK33,,22




Contoh 8.11

ssuubbggrraaff ddaarrii KK55

Definisi. Gabungan dari dua graf sederhana G1 = (V 1, E 1) dan G2 = (V 2, E 2) adalah graf

sederhana dengan himpunan simpul V 1∪V 2 dan himpunan garis hubung E 1∪ E 2.

Gabungan dari G1 dan G2 dituliskan sebagai G1∪G2.

KK55

GG11 GG11 ∪∪ GG22 == KK55

Representasi Graf

Perhatikan dua graf berikut ini. Simpula awal, tetangga dan simpul akhir didaftarkan pada

tabel di bawahnya.

GG22

aa aa

bb

cc

dd bb

cc

dd




Simpul Simpul tetangga Simpul Simpul akhir

a b, c, d a c

b a, d b a

c a, d cd a, b, c d a, b, c

Definisi: Misalkan G = (V , E ) adalah sebuah graf sederhana dengan |V | = n. Anggap simpul

pada G disusun dengan urutan v1, v2 …, vn Matriks kedekatan ( Adjacency matrix) dari graf

G, AG, yang berkaitan dengan simpul-simpul, adalah sebuah matriks boolean n×n dengan

elemen ke (i, j) berharga 1 jika vi dan v j bertetangga, dan selainnya itu berharga 0.

Dengan kata lain, untuk sebuah matriks kedekatan ija⎡ ⎤= ⎣ ⎦A , maka berlaku

{ },

1, jika , adalahsebuahgarishubungdari

0, jikabukangaris hubung dari

i j

i j

v v Ga

G

⎧⎪= ⎨

⎪⎩

Contoh 8.12 Tentukan matriks kedekatan AG untuk graf di

samping berdasarkan urutan simpul a, b, c, dan d !

Jawab:

0 1 1 1

1 0 0 1

1 0 0 1

1 1 1 0

⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦

GA

aa

bb

cc

dd

Catatan: Matriks kedekatan dari graf tak berarah selalu simetris

Untuk representasi graf dengan garis hubung ganda (multiple edge), matriks boolean tidak

bisa dipakai dan sebagai gantinya dipergunakan matriks bilangan cacah. Elemen ke (i, j) dari

matriks tersebut sama dengan jumlah garis hubung yang terdapat pada kedua simpul {vi, v j}.




Contoh 8.13 Tentukan matriks kedekatan AG untuk graf di

samping berdasarkan urutan simpul a, b, c, dan d !

Jawab:

0 1 1 21 1 0 1

1 0 0 3

2 1 3 0

⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦

GA

Definisi. Misalkan G = (V , E ) sebuah graf tak berarah dengan |V | = n. Anggap simpul dan

garis hubung pada G disusun dengan urutan seperti v1, v2, …, vn dan e1, e2, …, em. Matriks

insiden ( Incidence matrix) dari G yang berkaitan dengan simpul dan garis hubung adalah

matriks boolean n×m dengan elemen ke (i, j) =1 jika garis e j terhubung dengan simpul vi, dan

selain itu berharga 0.

Dengan kata lain , untuk sebuah incidence matrix M = [mij], maka berlaku

,

1, jika garis terhubung dengan

0,selainitu

j i

i j

e vm

⎧= ⎨

⎩

Contoh 8.14: Tentukan matriks insiden M untuk graf

berikut berdasarkan urutan simpul a, b, c, d dan urutan garis

hubung 1, 2, 3, 4, 5, 6!

Jawab:

1 1 0 0 1 0

1 0 1 0 0 0

0 0 0 1 1 1

0 1 1 1 0 0

M

⎡ ⎤⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦

Catatan : Matriks insiden dari graf tidak berarah, setiap kolomnya akan berisi 2 buah nilai 1

jika garis hubung menghubungkan dua buah simpul dan berisi 1 buah nilai 1 untuk loop.

Graf-Graf yang Isomorfis

Definisi. Graf sederhana G1 = (V 1, E 1) dan G2 = (V 2, E 2) disebut isomorfis jika ada sebuah

fungsi bijektif (satu-ke-satu dan onto) dari V 1 ke V 2 dengan sifat bahwa a bertetangga dengan

aa

bb

cc

dd

11 22

44 55

33

66

aa

bb

cc

dd




b pada G1 jika dan hanya jika f (a) bertetangga dengan f (b) pada G2, untuk seluruh a dan b

pada V 1.

Fungsi f seperti itu disebut isomorfisme. Dengan kata lain, G1

dan G2

adalah isomorfis jika

simpul-simpulnya dapat diurutkan dengan suatu cara sedemikian rupa sehingga matriks

kedekatan dan adalah identik. Secara visual, dua buah graf, G1GM

2GM 1 dan G2, isomorfis

jika graf-graf tersebut dapat disusun dengan suatu cara sedemikian rupa sehingga

tampilannya identik (tentu tanpa merubah ketetanggaan).

Menentukan dua buah graf tidak isomorfis lebih mudah dibandingkan dengan menentukan

apakah dua buah graf isomorfis. Untuk dua buah graf sederhana dengan masing-masingsimpulnya berjumlah n buah, maka akan ada n! kemungkinan isomorfisme yang harus

diperiksa. Untuk itu kita dapat memeriksa invarian, yaitu, sifat yang harus dimiliki oleh dua

buah graf sederhana yang isomorfis. Keduanya haruslah

memiliki jumlah simpul yang sama, dan

jumlah garis hubung yang sama , dan

derajat dari simpul-simpulnya sama.

Perhatikan bahwa dua graf yang salah satu dari invarian di atas berbeda pasti menyebabkan

kedua graf tersebut tidak isomorfis, tetapi jika seluruhnya sesuai, belum tentu graf tersebut

isomorfis.

Contoh 8.15: Apakah kedua graf berikut isomorfis ?

aa

bb

cc

Jawab : Ya, keduanya isomorfis karena dapat disusun sehingga terlihat identik. Dapat

diamati, jika pada graf sebelah kanan kita gerakkan simpul b kesebelah kiri garis hubung

dd

aa

bb

cc

ee

dd

ee




{a,c}. Maka fungsi isomorfis f dari graf kiri ke graf sebelah kanan adalah: f (a) = e, f (b) = a,

f (c) = b, f (d ) = c, f (e) = d .

Contoh 8.16 : Apakah kedua graf berikut isomorfis ?

aa bb

cc

ee

aa

ee

Jawab : Tidak, karena derajat dari simpul-simpulnya berlainan. Simpul d pada graf dikanan

berderajat satu, tetapi tidak ada satupun simpul pada graf dikiri yang berderajat 1.

Konektivitas Graf

Definisi. Sebuah lintasan ( path) dengan panjang n dari u ke v, dimana n adalah bilangan bulat

positif dalam sebuah graf tidak berarah adalah sebuah urutan garis hubung e1, e2, …, en dari

graf sehingga f (e1)={ x0, x1}, f (e2) = { x1, x2}, f (en) = { xn-1, xn}, dgn x0= u dan xn = v.

Jika graf tersebut adalah sebuah graf sederhana, kita menuliskan lintasan tersebut dengan

urutan/ deretan simpul x0, x1, …, xn, karena secara unik dapat menentukan lintasan. Lintasan

adalah sebuah sirkit jika dimulai dan diakhiri pada simpul yang sama, yaitu jika u = v.

Definisi (Lanjutan). Lintasan atau sirkit ini disebut melalui ( pass through / traverse) x0, x1,

…, xn-1.

Lintasan atau sirkit disebut sederhana jika tidak mengandung garis yang sama lebih dari

sekali.

Definisi. Graf tak berarah disebut terhubung (connected ) jika ada lintasan diantara setiap

pasangan dari simpul yang berbeda dalam graf

dd

bb

ccdd




aa bb

Sebagai contoh, setiap dua komputer dalam jaringan dapat berkomunikasi jika dan hanya jika

graf dari jaringan tersebut terhubung. [Catatan: sebuah graf yang mengandung hanya satu

simpul selalu terhubung karena tidak berisi suatu pasangan simpul yang berbeda]. Gambar di

atas menunjukkan contoh-contoh graf yang terhubung dan yang tak-terhubung.

Teorema. Selalu ada lintasan sederhana antara setiap pasangan simpul yang berbeda dari

suatu graf-tak-berarah yang terhubung

Definisi. sebuah graf yang tidak terhubung adalah gabungan dari dua atau lebih subgraf yang

terhubung dengan masing-masing pasangan darinya tidak memiliki simpul bersama (disjoint ).

Subgraf-subgraf yang terhubung tetapi disjoint ini disebut komponen-komponen terhubung

dari graf.

Contoh 8.17 : tentukan komponen-komponen terhubung dari graf berikut ini?

dd

aa

bb

c

ee

terhubung

dd

aa bb

cc ee

tak terhubungdd

ee

cc

terhubung

dd

aa bb

cc ee

ff tak terhubung

gg

hh

ii

cc

dd

bb

aa ee

ff j j




Jawab: Komponen-komponen terhubung adalah graf dengan simpul-simpul {a, b, c, d }, {e},

{ f }, dan {g, h, i, j}.

Definisi. Sebuah graf berarah disebut terhubung kuat (strongly connected ) jika ada sebuah

lintasan dari a ke b dan dari b ke a untuk semua pasangan simpul a, b pada graf.

Definisi. Sebuah graf berarah disebut terhubung lemah (weakly connected ) jika hanya ada

sebuah lintasan diantara dua simpul dalam graf tidak berarahnya. ( Ada lintasan dari a ke b,

tetapi tidak dari b ke a, atau sebaliknya)

Contoh 8.18: Apakah graf berarah berikut ini terhubung kuat atau lemah?

aa

Terhubung lemah, karena (misalnya)

tidak ada lintasan dari b ke d .

Terhubung kuat, karena ada lintasan diantara

seluruh kemungkinan pasangan simpul.

Jumlah dan ukuran dari komponen dan sirkit terhubung merupakan invarian berkaitan dengan

isomorfisme dari graf sederhana

Contoh 8.19: Apakah dua graf berikut ini isomorfis ?

aa

bb bb

cc

dd

cc

dd




Jawab: tidak , karena graf sebelah kanan berisi sirkit dengan panjang 3 , sedangkan pada graf

sebelah kiri tidak ada sirkit yang demikian.

Masalah Lintasan Terpendek

Kita dapat memberikan bobot pada garis dari graf, sebagai contoh, untuk merepresentasikan

jarak antara kota dalam jaringan jalan kereta, seperti dilukiskan pada graf berikut ini.

JJaakkaarrttaa

BBooggoorr

YYoogg y

Pembobotan graf dapat juga dipakai untuk memodelkan jaringan komputer dengan response

time atau biaya sebagai bobotnya. Satu pertanyaan yang sangat penting yang dapat kita

selidiki pada graf seperti ini adalah: “Yang manakah lintasan terpendek antara dua simpul

dalam graf, yaitu, lintasan dengan jumlah bobot minimal sepanjang jalannya?“ Hal ini

misalnya berkaitan dengan koneksi tercepat pada jaringan komputer atau hubungan lintasan

kereta terpendek

Algoritma Dijkstra

Algoritma Dijkstra adalah sebuah prosedur iteratif untuk mencari lintasan terpendek antara

dua simpul, a dan z, di dalam graf dengan pembobot. Prosedur ini dilaksanakan dengan cara

mencari panjang lintasan terpendek dari sebuah simpul pendahulu dan menambahkan simpul-

simpul tersebut ke himpunan simpul S. Algoritma berhenti setelah simpul z tercapai.

Pseudocode dari algoritma Dijkstra dapat dilihat di bawah ini.

yaakkaarrttaa

BBaanndduunn

2255

118800

440000

g

660000




procedure Dijkstra(G: graf sederhana yang terhubung dan

dengan pembobot, dengan simpul a = v0, v1, …, vn = z dan

bobot positif w(vi, vj), dimana w(vi, vj) = ∞ jika {vi, vj}bukan garis hubung pada G)

for i := 1 to n

L(vi) := ∞

L(a) := 0

S := ∅

{label-label sekarang diinisialisasi sehingga label dari a

adalah nol dan label yang lainnya adalah ∞, dan set S

adalah kosong}

while z∉S

begin

u := simpul tidak pada S dengan minimal L(u)

S := S∪{u}

for seluruh simpul v tidak pada S

if L(u) + w(u, v) < L(v) then L(v) := L(u) + w(u, v)

{ ini menjumlahkan sebuah simpul ke S dengan label

minimal dan memperbaharui label-label simpul yang

tidak di S}

end {L(z) = panjang jalur terpendek dari a ke z}

Contoh 8.20: Tentukan lintasan terpendek dari graf berikut ini dengan menggunakan

algoritma Dijkstra.

STEP-0 STEP-1

aa

bb dd

zz

ee cc

44

22

11

55

88

1100

22

66

33

0

2(a) ∞

∞

∞ 4(a)

aa

bb dd

z

ee cc

44

22

11

55

22

66 88

1100

z

33

0

∞ ∞

∞

∞




STEP-2 STEP-3

STEP-4 STEP-5

STEP-6:

Algoritma Dijkstra akan mencari panjang lintasan terpendek antara dua simpul

dalam graf yang terhubung, sederhana, tidak berarah, dengan pembobot.

Teorema.

aa

bb dd

zz

ee cc

44

22

11

55

88

1100

22

66

33

0

2(a)

3 (a, c) 10 (a, c, b)

10(a, c, b, d)

13 (a, c,

b, d, e)

aa

bb dd

zz

ee cc

44

22

11

55

88

1100

22

66

33

0

2(a)

3 (a, c) 10 (a, c, b)

10(a, c, b, d)

13 (a, c,

d, e)b,

aa

bb dd

zz

ee cc

44

22

11

55

88

1100

22

66

33

0

2(a)

3 (a, c) 10 (a, c, b)

10(a, c, b, d)

14 (a, c, b, d)

aa

bb dd

zz

ee cc

44

22

11

55

88

1100

22

66

33

0

2(a)

∞

3 (a, c) 10 (a, c, b)

12 (a, c)

aa

bb dd

zz

ee cc

44

22

11

55

8822

66

1100

33

0

2(a)

3 (a, c) 8(a, c,b)

12 (a, c)

∞




Teorema. Algorithm Dijkstra menggunakan O(n2) operasi (penjumlahan dan perbandingan)

untuk mencari panjang lintasan terpendek antara dua am graf yang terhubung,

sederhana, tidak berarah, dengan pembobot.

Traveling Salesman Problem (TSP)

TSP adalah salah satu masalah klasik dalam ilmu komputer. Permasalahan ini dapat

dilukiskan sebagai berikut: Seorang tr ng sale engunjungi sejumlah kota dan

kembali ke titik awal mula pemberangkatan. Tentunya ia ingin menghemat waktu dan energi,

hingga ia ingin mementukan lintasan terpendek dalam perjalanannya.

f dengan pembobot,

ngkap, tidak berarah. Masalahnya adalah menentukan sirkit dengan total bobot yang

bil oleh traveling salesman untuk mengunjungi

ota-kota berikut? (Jarak dinyatakan dalam kilometer).

rta, Jorong, Jogja (2,000 Km).

Contoh8.22: Diberikan n buah simpul, berapa banyak siklis C n berbeda, yang dapat kita

bentuk dengan menghubungkan simpul-simpul tersebut dengan garis hubung?

simpul dal

aveli sman ingin m

se

Kita dapat merepresentasikan kota-kota dan jarak nya dengan sebuah gra

le

minimum dan setiap simpul dikunjungi tepat satu kali.

Contoh 8.21: Lintasan mana yang akan diam

k

Jawab: Lintasan terpendek adalah Jogja, Semarang, Jaka

JJaakkaarrttaa

JJoorroonngg

SS

eemm

aarraanngg

660000

770000 200

665500 555500 770000

JJoo

gg j jaa




Jawab: Pertama kita pilih titik awal. Kemudian kita memiliki (n–1) pilihan untuk simpul ke

dua dalam siklis, (n–2) untuk simpul ketiga, dst, sehingga ada (n–1)! Buah pilihan untuk

seluruh siklis. Akan tetapi,jumlah ini termasuk siklis yang identik yang dibentuk dalam arah

kebalikannya. Oleh karena itu jumlah siklis yang berbeda sesungguhnya adalah

C n = (n – 1)!/2.

Sampai saat ini belum ada algoritma yang dapat menyelesaikan masalah TSP dengan

kompleksitas polynomial worst-case time complexity .Ini artinya, untuk jumlah simpul yang

anyak, penyelesaian TSP (secara analitik) tidak praktis. Dalam kasus ini, kita dapat

imana

ntasan yang diperoleh mungkin sedikit lebih panjang dibanding lintasan traveling salesman

Karena tree tidak mempunyai sirkit sederhana, maka tidak akan ada garis-hubung paralel atau

loop didalam s karena itu, tree haruslah sebuah graf yang sederhana.

b

menggunakan algoritma pendekatan yang efisien dalam menentukan sebuah lintasan, d

li

yang seharusnya tetapi dengan kompleksitas perhitungan polinomial, misalnya dengan

algoritma jaringan syaraf tiruan.

Diagram Pohon (Tree )

Definisi. Diagram pohon (tree) adalah sebuah graf tak berarah yang terhubung (connected ),

yang tidak mengandung sirkit sederhana.

ebuah tree. Oleh

Teorema. Sebuah graf tidak berarah adalah tree jika dan hanya jika ada sebuah lintasan

sederhana yang unik antara simpul-simpulnya.

Gambar berikut ini menunjukkan graf yang berupa tree dan yang bukan tree.

t t r r e e e e bbuukkaann t t r r e e e e




efinisi. Sebuah graf tidak berarah yang tidak berisi sirkit sederhana dan tidak perlu

terhubung disebut sebuah forest.

Secara umum, kita menggunakan tree untuk merepresentasikan struktur bertingkat

(hierarchical structures). Kita sering memilih simpul tertentu dari tree sebagai akarnya

(root ). Sebuah tree bersama-sama dengan root -nya menghasilkan sebuah graf berarah yang

disebut sebuah rooted-tree. Beberapa is ee:

• Parent dari simpul v (selain root ) adalah simpul u yang unik sedemikian sehingga ada

sebuah garis-hubung berarah dari u ke v. Jika u parent dari v maka v adalah child dari u

• Siblings adalah simpul-simpul dengan parent yang sama

• Ancestors dari suatu simpul (selain root ) adalah simpul-simpul pada lintasan dari root ke

simpul tersebut, diluar simpul itu sendiri dan termasuk root .

• Descendants dari simpul v adalah simpul-simpul dengan v sebagai ancestor -nya.

• Sebuah simpul dari sebuah tree dise af jika ia tidak memiliki en.

Level dari simpul v adalah panjang dari lintasan yang unik dari root ke simpul tersebut.

level maksimum dari simpul

ebuah tree bias menggambarkan silsilah keturunan dari sebuah keluarga, atau direktori

D

tilah dalam tr

but sebagai le childr

•

Level dari root didefinisikan = 0.

• Height dari rooted tree adalah

S

dalam sebuah komputer seperti yang dilukiskan pada gambar berikut ini.

t t r r e e e e bbuukkaannt t r r e e e e




Tree di samping menyatakan ekspresi aritmatika

(y + z)⋅(x - y)

Definisi. Rooted-tree disebut sebuah m-ary tree jika setiap simpul internal tidak memiliki

lebih dari m children. Sebuah tree disebut full m-ary tree jika setiap simpul internal memiliki

tepat m children. Khususnya, m-ary tree dengan m = 2 disebut sebagai binary tree.

Teorema. Tree dengan n simpul memiliki (n – 1) buah garis hubung.

Teorema. e dengan i-buah simpul internal mengandung n = mi + 1 simpul.

Pohon Pencari Biner (Binary Search Tree )

inary search tree (BST) berguna untuk melakukan pencarian besar-besaran pada daftar item

da suatu

mpul lebih besar daripada kunci lain pada subtree kiri dan sekaligus lebih kecil daripada

math, computer, power,

++

Full m-ary tre

B

tertentu. BST adalah sebuah binary tree yang masing-masing child dari simpul ditentukan

sebagai child kanan atau kiri, dan masing-masing simpul dilabeli dengan sebuah key. Saat

membuat tree tersebut, simpul-simpul diberi kunci sedemikian hingga kunci pa

si

semua simpul pada subtree kanan. Sebagai contoh, BST untuk string

north, zoo, dentist, book diberikan pada diagram berikut.

--

y y zz xx y y

⋅

//

uussrr

bbiinn ssppooooll llss

bbiinn temp

UUwweess

T T iinnii BBoonnoo

FrFraannkk y y JJoonnii PPeettrraa




Untuk melakukan pencarian sebuah item pada BST, kita dapat memulai dari root dan

membandingkan key-nya dengan x key, kita teruskan ke child kiri dari

simpul tersebut, dan jika x lebih besar dari key, kita teruskan ke sebelah kanan. Prosedur

tersebut diulang terus sampai kita m muka yang kita cari atau kita tidak dapat

meneruskannya lebih lanjut lagi. Untuk n item, pencarian dapat dibentuk dengan jumlah

ngkah maksimumsebesar ⎡log(n + 1)⎤

• Kompresi data dengan pohon pengkode Huffman ( Huffman coding trees)

pembentang (spanning tree) dari G

ada

Catatan ng dari G=(V , E ) adalah graf terhubung pada V dengan jumlah

garis m

ongan

ang akan menghubungkan seluruh perpustakaan di universitas yang ada di Boston. Berikut

x

. Jika x lebih kecil dari

ene n item

la

Aplikasi dari Tree

Ada sejumlah aplikasi penting dari tree, diantaranya :

• Optimasi jaringan dengan pohon pembentang minimum (minimum spanning trees)

• Penyelesaian masalah dengan proses lacak-balik pada pohon keputusan (backtracking

in decision trees)

Definisi. Misalkan G sebuah graf sederhana. Pohon

lah sebuah sub-graf dari G yang merupakan tree yang berisi setiap simpul dari G.

: Pohon pembenta

inimum = (|V | - 1).

Contoh 8.23: Ketika musim dingin, suhu di Boston bisa menjadi sangat dingin, sehingga

keenam buah universitas di wilayah ini memutuskan untuk membangun sistem terow

y

ini adalah graf lengkap dari rancangan (awal) terowongan tersebut.

mmaatthh

ccoommppuutteerr ppoowweerr

ddeennttiisstt nnoorrtthh bbooookk zzoooo




Akan ada suatu pohon pembentang dari graf ini yang menghubungkan seluruh perpustakaan

dengan jumlah terowongan yang minimum. Sebagai contoh, pohon pembentang berikut ini

yang menyatakan lima buah terowongan sudah cukup untuk menghubungkan ke enam buah

perpustakaan.

Masalah berikutnya adalah bagaimana cara menentukan sistem terowongan tersebut dengan

biaya semurah mungkin. Inilah yang disebut sebagai masalah pohon pembentang minimum

(MST- Minimum Spanning Tree). MST pada graf terhubung dan dengan pembobot adalah

sebuah pohon pembentang yang mempunyai jumlah bobot paling kecil. Jika diberikan sebuah

BBrraannddeeiiss UUnniivv HHaarrvvaarrdd UUnniivv

MMIIT T

T T uuffttss UUnniivv BBoossttoonn UUnniivv

UUnniivv MMaassss

BBrraannddeeiiss UUnniivv HHaarrvvaarrdd UUnniivv

MMIIT T

T

T uuffttss UUnniivv

BBoossttoonn UUnniivv

UUnniivv MMaassss




grf terbobot, bagaimana cara menentukan MST? Berikut ini graf seperto contoh diatas tetapi

dengan bobot yang menyatakan biaya pembangunan terowongan dalam Milyar rupiah.

ranya

ang akan kita bahas adalah algoritma Prim dan algoritma Kruskal.

Algoritma Prim

Berikut ini langkah-langkah dalam algoritma Prim :

• Mulai dengan memilih suatu garis dengan bo terkecil, dan letakkan pada pohon

pembentang,

• Secara berurutan tambahkan pada garis-hubung dengan bobot minimum yang

terhubung pada simpul yan elah ada pada tree dan tidak membentuk sirkit sederhana

dengan garis-garis yang tel da pad ee

• Berhenti saat (n – 1) buah garis-hubung telah ditambahkan.

lgoritma Kruskal

tidak

embutuhkan garis-hubung baru untuk dihubungkan ke simpul yang telah ada pada tree.

BBrraannddeeiiss

Dengan melihat graf diatas, diperoleh bahwa biaya termurah adalah 20 Milyar rupiah.

Untuk graf dengan ukuran besar, diperlukan algoritma untuk mencari MST. Dua dianta

y

bot

g t

ah a a tr

A

Algoritma Kruskal identik dengan algoritma Prim, kecuali bahwa algoritma ini

m

UUnniivv HHaarrvvaarrdd UUnniivv

MMIIT T

T T uuffttss UUnniivv BBoossttoonn UUnniivv

UUnniivv MMaassss

7

8 4

2

9 53

64

9 4 65

4




Kedua algoritma dijamin dapat menghasilkan pohon pembentang yang minimum dari graf

terhubung dan terboboti.

Lacak Balik Pada Pohon Keputusan

Poh

dengan keputusan/tindakan, dengan sub-tree pada simpul-simpul tersebut adalah semua hasil

dar e

pengam

kepada ah berkaitan dengan lintasan dari root ke

leaf

erdapat sekelompok masalah yang memerlukan exhaustive search dari seluruh

n guna mendapatkan pemecahan. Kita dapat menyelesaikan

backtracking).

enya: Kita mulai pada root dari pohon keputusan, lalu bergerak turun, yakni, membuat

da situasi dimana tidak ada solusi

ana cara menempatkan n buah queen pada papan

×n sedemikian hingga tidak ada dua queen dapat saling menangkap/

on keputusan adalah suatu rooted-tree dimana masing-masing simpul internal berkaitan

i k putusan yang mungkin. Pohon keputusan dapat dipakai untuk memodelkan suatu

bilan keputusan terhadap masalah tertentu, dimana rangkaian keputusan membawa

suatu solusi. Kemungkinan solusi dari masal

dari pohon keputusan.

T

kemungkinan rangkaian keputusa

masalah yang demikian dengan membuat pohon keputusan yang lengkap dan kemudian

menentukan lintasan dari root ke leave yang berkorespondensi dengan solusi dari masalah

tersebut. Dalam beberapa kasus, efisiensi dari prosedur ini dapat meningkat secara dramatis

dengan tenik lacak balik (

Id

rangkaian keputusan, sampai tercapai solusi atau sampai pa

yang didapatkan. Dalam kasus terakhir, lacak-balik ke parent dari simpul terkini dan ambil

lintasan lain turun darinya. Jika seluruh lintasan dari simpul ini telah dikaji, lacak-balik ke

parent -nya. Teruskan prosedur sampai kita mendapatkan solusi atau tidak terdapat solusi

(tidak ada lagi lintasan yang dapat dicoba).

Contoh 8.24 : [Masalah n-queen] Bagaim

catur berukuran n

memakan?




Sebuah queen dapat bergerak dalam sejumlah

petak secara horizontal, vertikal, dan

diagonal.

Disini petak target yang mungkin dari queen

Q ditandai dengan X.

X X XX X X

X X X

X X X Q X X X X

X X X

X X X

X X X

X X

Jelaslah bahwa pada suatu solusi dari masalah n-queen, akan ada tepat satu queen pada

masing-masing kolom dari papan. Oleh karena itu, kita dapat menggambarkan solusi dari

masalah ini sebagai rangkaian dari n buah keputusan :

Keputusan 1: Tempatkan queen pada kolom ke-1

Keputusan 2: Tempatkan queen pada kolom ke-2

….

…

Keputusan n: Tempatkan queen pada kolom ke-n

Kita sekarang akan menyelesaikan masalah 4-queens menggunakan metoda backtracking.




Papan Kosong

at queen ke-1

Tempat queen ke-2

Tempat queen ke-4

dapat memainkan suatu game anatara komputer dengan manusia sebagai lawannya.

Contoh 8.25: Pada permulaan permainan, ada 7 buah koin diatas meja. Pemain pertama

mendapat giliran pertama, kemudian pemain ke-2, dst, bergantian. Setiap mendapat giliran,

pemain mengambil 1, 2, atau 3 koin. Pemain yang dapat mengambil seluruh koin tersisa

adalah yang keluar sebagai pemenangnya

Marilah kita asumsikan bahwa komputer (C) merupakan pemain pertama yang harus

melakukan pergerakan pertama. Kemudian permainan dapat gambarkan sebagai rangkaian

dari keputusan, dimana keputusan pertama oleh komputer, ke-2 oleh manusia, ke-3 oleh

komputer , dst. Sampai seluruh koin habis diambil. Komputer ingin membuat keputusan yang

Temp

QQ

QQ

Tempat queen ke-3

Kita dapat juga menggunakan metoda backtracking untuk menuliskan program “pintar” yang

QQ

QQ

QQ

QQ

QQ

QQ

QQ

QQ

QQ

QQ

QQ

QQ

QQ

QQ

QQ

QQ




menjamin selalu ada ditangannya. Asumsikan bahwa pemain manusia

(H) selalu mencari pergerakan yang optimal.

Komputer harus mulai dengan mengambil 3 buah koin agar terjamin dia akan selalu menang .

Un lebih kompleks dan menarik seperti catur, tidak mungkin

emeriksa setiap kemungkinan urutan pergerakan. Pemain komputer hanya melihat beberapa

ang berbeda, kita dapat menghemat memori dan

ereduksi waktu transmisi dengan cara menggunakan kode yang panjangnya dapt diubah

mengkodekan karakter “e” dengan bit “0”, “a” dengan “1”, dan “t” dengan “01”. Bagaimana

bahwa kemenangan

tuk permainan lain yang

m

jumlah pergerakan tertentu ke depan dan memperkirakan peluang dari kemenangan.

Pohon Pengkode Huffman

Kita biasanya mengkodekan suatu string dengan menggunakan kode yang panjangnya tetap

( fixed-length codes) pada seluruh alfabet (mis. 8 bit untuk ASCII). Akan tetapi, jika karakter

yang berbeda muncul dengan frekuensi y

m

(VLC -variable length codes). Ide dasar dari teknik pengkodean ini adalah nya adalah

memakai kode terpendek untuk karakter yang paling sering muncul.

Ada beberapa hal yang harus diperhatikan ketika menggunakan VLC. Misalnya, kita ingin

CC

HH

CC

HH

CC

66

55

44

33 22 11

11 22 33

22 11

CC CC

11 44

22

CC

33

33

55

2211

11

33 22 11

11 22 33

22 11

HH HH HH

33

11

44

33 22 11

11 22 33

22 11

HH HH HH

33

44

33 22 11

11 22 33

22 11

CC CCCC

33

77




kemudian kita mengkodekan kata “tea”? Dari system ini, maka kodenya adalah “0101”.

Kalau dilihat lebih cermat, kode tersebut rancu, karena kode tersebut bisa juga dihasilkan dari

ata “eat ”, “eaea”, atau “tt ”. Tentu saja kode yang demikian tidak dapat diterima karena

apat menyebabkan kesalahan/ kehilangan informasi.

Untuk menghindari kerancuan ini, kita dapat menggunakan kode prefiks ( prefix code). Pada

kode prefiks, bit string untuk sebuah karakter tidak pernah an menjadi prefiks (bagian

pertama) dari bit string karakter lainnya. Sebagai contoh, pengkodean “e” dengan “0”, “a”

dengan “10”, dan “t ” dengan “11” adalah kode prefiks. Maka, kata “tea” akan dikodekan

sebagai “11010”. Bit string ini adalah unik karena hanya kata tea dan tidak ada kata lain yang

dapat dikodekan dengan hasil yang sama

Kode prefiks dapat disusun dengan bantuan pohon biner, dimana karakter adalah label dari

leaf dalam on ner ebut. Garis dari tree dilabeli sedemikian hingga garis ke child kiri

diberi bit “0” dan ke ichild kanan dengan bit “1”. Bit string yang dipakai untuk mengkodekan

karakter adalah rangkaian label dari garis dalam lintasan yang unik dari root ke leaf ya

ilabeli dengan karakter tersebut. Maka, pohon biner untuk contoh pengkodean “tea” yang

Pada pohon biner ini tidak ada leaf yang dapat menjadi ancestor

dari leaf lainnya. Sehingga, tidak ada kode dari karakter dapat

dari kode karakter lainnya. Inilah yang dimaksud

“eeadfeejjeggebeeggddehhhececddeciedee”

k

d

ak

.

poh bi ters

ng

d

telah dibahas adalah sebagai berikut.

dengan kore prefiks.

Untuk menentukan kode yang optimal (terpendek) dari suatu string, pertama kita harus

mencari frekuensi karakter dalam string tersebut. Ambil contoh string

00 11

00 11 ee

menjadi prefix

aa tt




String ini berisi 1×a, 1×b, 3×c, 6×d, 15×e, 1×f, 4×g, 3×h, 1×i, dan 2× j. Kita sekarang dapat

menggunakan algoritma Huffman untuk membuat coding tree yang optimal.

Untuk alfabet berisi n huruf, algoritma Huffman mulai dengan n simpul, satu untuk masing-asing huruf, dilabeli dengan huruf dan frekuensinya. Kita kemudian menentukan 2 buah

TEP-1

STEP-3

m

simpul yang paling kecil frekuensinya dan gantikan mereka dengan tree dimana root dilabeli

dengan jumlah dari kedua frekuensi tersebut dan yang dua childrennya adalah dua simpul

yang kita gantikan. Pada langkah berikutnya, kita menentukan 2 frekuensi terendah antara

simpul-simpul tunggal dan root-root dari tree-tree yang telah kita buat. Ini diulang sehingga

kita dapatkan tree tunggal.

S

STEP-2

1

1 11 11 11 22 33 33 44 66 1155

aa bb ff ii cc hh dd ee

22 11 11 22 33 33 44 66 1155

ff ii j j cc hh dd ee 11 11

aa bb

1155 22 22 33 33 44 66 22

j j cc hh gg dd ee 11 11

aa bb

11 11

ff ii




STEP-4

STEP-5

STEP-6

2

2

2

2

33 33 44 66 1515

cc hh dd ee 11 11

aa bb

22

11 11

ff ii

44

22 22 33

33 44 66 1155

cc

hh dd ee

11 11

aa bb

22

11 11

ff ii

44 55

22 22 33

66 1155

cc

dd ee

11 11

aa bb

22

11 11

ff ii

44 55 77

33 44

hh




STEP-7

STEP-8

22 22 33

66 1155

cc

dd ee

11 11

aa bb

22

11 11

ff ii

44 55 33 44

hh

77 99

22 22 33

66

1155

cc

dd

ee

11 11

aa bb

22

11 11

ff ii

44 55

33 44

hh

77

99 1133




STEP-9

TEP-10

22

S

22 33

66

1155 2222

cc

dd

ee

11 11

aa bb

22

11 11

ff ii

44 55

33 44

hh

77

99 1133

3377

22 22 33

66

1155

j j cc

dd

ee

11 11

aa bb

22

11 11

ff ii

44 55

33 44

hh gg

77

99 1133

2222




Akhirnya kita bisa mengubahnya menjadi kode prefiks sebagai berikut:

VLC-nya adalah:

a (freq. 1): 00000

b (freq. 1): 00001

c (freq. 3): 0001

d (freq. 6): 011

e (freq. 15): 1

f (freq. 1): 00100

g (freq. 4): 0101

h (freq. 3): 0100

i (freq. 1): 00101

j (freq. 2): 0011

ehingga, string asal “eeadfeejjeggebeeggddehhhececddeciedee” menggunakan

kode dengan panjang tetap, kita memerlukan 4 bit setiap karakternya (ada 10 karakter yang

berbeda). Sehingga, panjang kode dari seluruh string adalah 4⋅37 = 148 bit. Tetapi dengan

VLC, kita hanya membutuhkan

1⋅5 +1⋅5 + 3⋅4 + 6⋅3 + 15⋅1 + 1⋅5 + 4⋅4 + 3⋅4 + 1⋅5 + 2⋅4 = 101 bit.

Dapat diperlihatkan bahwa untuk setiap string yang diberikan, pohon pengkode Huffman

selalu menghasilkan VLC dengan panjang deskripsi yang minimum untuk string tersebut.

00 11

00

S

11 ee

11 00 1100

1100 11

00 11

00 11

00 11

dd

hh

ii ff

cc

bb aa

00


8. graf, diagram pohon dan aplikasinya

Documents