25486466 graph-pohon

Oleh: Bandung Arry Sanjoyo 1

1 Modul 6 POHON

Pendahuluan

Dalam bab ini kita akan membahas salah satu jenis dari graf yang dinamakan pohon (tree).

Banyak permasalahan dalam kehidupan sehari-hari yang dapat direpresentasikan sebagai pohon.

Sebagai contoh: silsilah keluarga, susunan organisasi umumnya dinyatakan dalam bentuk

pohon, jaringan komputer yang menggunakan teknologi ethernet atau star juga dimodelkan

dalam bentuk pohon.

Dalam dunia komputer, konsep pohon banyak dipakai. Seperti penguraian kalimat (parsing) dan

pemanggilan fungsi dalam banyak bahasa pemrograman, pohon dipakai juga untuk melakukan

penyandian (coding), dan untuk melakukan pemampatan file dalam algoritma Huffman,

Lempel-Ziv, dan sebagainya. Dari sudut pandang matematika diskrit, bab ini akan membahas

pohon sebagai bagian teori graf dan beberapa penerapanya.

Tujuan Instruksional Umum

Mahasiswa mengerti konsep pohon, macam-macam pohon, dan mengetahui penerapannya

dalam kehidupan sehari-hari, khususnya dalam bidang komputer.

Tujuan Instruksional Khusus

Mahasiswa diharapkan dapat:

1. Memahami definisi pohon, dan dapat mengaitkannya dalam permasalahan sehari-hari.

2. Memahami pengertian pohon perentang, pohon perentang minimal, dan dapat

melakukan pencarian pohon perentang minimal dari suatu graf.

3. Memahami pengertian pohon biner dan penerapannya.


4. Memahami berbagai macam teknik penelusuran pohon.

5. Memahami algoritma Huffman dan dapat melakukan penyandian dengan memanfaatkan

algoritma ini.


6.1 Kegiatan Belajar I:

Definisi Dan Sifat-Sifat Pohon

Pohon (Tree) telah digunakan sejak tahun 1857 oleh matematikawan Inggris yang bernama

Arthur Cayley untuk menghitung jumlah senyawa kimia. Pada Gambar 6.1.1 menggambarkan

dua isomer Butane CnH2n+2 . Sejak itu, pohon banyak dipakai untuk menyelesaikan berbagai

permasalahan dalam berbagai macam disiplin ilmu.

H

C

C

C

C

H

H

H

H

H

H

H

H

H

C

C

H

C CH H

H H

H H

H H

H

Gambar 6.1.1 Dua Isomer Butane

Silsilah keluarga biasa digambarkan dalam bentuk pohon. Sebagaimana pada Gambar 6.1.2

yang merupakan silsilah keluarga Bernoulli, suatu keluarga matematikawan yang terkenal dari

Swiss. Diagram seperti itu dinamakan pohon silsilah. Pohon silsilah merupakan suatu graf

dengan verteks menyatakan nama anggota keluarga dan edge menyatakan hubungan antara anak

dan orang tua. Kalau kita perhatikan pada pohon silsilah tersebut tidak memiliki sirkuit/cycle.

Nikolaus

1623-1708

Jacob I

1654-1705

Nikolaus

1662-1716

Johann I

1667-1748

Nikolaus I

1687-1759

Nikolaus II

1659-1726

Daniel

1700-1782

Johann II

1710-1790

Johann III

1746-1807

Jokob II

1759-1789

Gambar 6.1.2 Silsilah keluarga Bernoulli


Definisi 6.1.1 Pohon (tree) adalah graf tak-berarah terhubung yang tidak memuat sirkuit

sederhana.

Menurut definisi di atas, suatu pohon merupakan graf yang terhubung, tak berarah, dan tidak

memuat sirkuit, ini merupakan tiga kriteria utama untuk pohon. Pada Gambar 6.1.3, gambar (a),

(b), dan (c) merupakan pohon. Sedangkan Gambar 6.1.3 (d) bukan merupakan pohon karena

tidak terhubung. Jika kita perhatikan lagi pada definisi di atas bahwa suatu pohon tidak memuat

sirkuit sederhana, maka dalam suatu pohon pasti tidak memuat multiple edge (dua edge yang

mempunyai verteks awal dan akhir sama) dan loop. Oleh karena itu suatu tree harus merupakan

graf sederhana.

a

a b

a

b

c

d

e

a

b

c

d

e

f

g

(a) (b) (c) (d)

Gambar 6.1.3

Contoh 6.1.1:

Ada empat pasang suami istri yang suka gosip. Si a beristri A, si b beristri B, si c beristri C, dan

si d beristri D. Si a menelpon istrinya dan menceritakan gosip baru, yang kemudian istri a

menelepon para istri untuk menyebarkan gosip itu. Setiap istri itu menelpon dan menceritakan

gosip kepada suami masing-masing. Jika setiap orang kita nyatakan dalam verteks/node, maka

edge menyatakan hubungan orang menelpon orang. Oleh karena itu, tersebarnya gosip ini dapat

dimodelkan dalam bentuk pohon seperti Gambar 6.1.4.

a Ac

B

dD

b

C

Gambar 6.1.4.

Dari definisi dan penjelasan pada contoh di atas, suatu pohon merupakan graf terhubung dan

tidak memuat sirkuit sederhana. Bagaimana kalau ada suatu graf yang tidak memuat sirkuit

sederhana, akan tetapi tidak terhubung?. Seperti Gambar 6.1.5 merupakan sebuah graf yang


tidak memuat sirkuit sederhana akan tetapi tidak terhubung. Graf pada Gambar 6.1.5 tersebut

terdiri dari tiga buah komponen (subgraf yang terhubung) masing-masing merupakan pohon.

Gambar 6.1.5. Sebuah hutan

Definisi 6.1.2 Hutan (Forest) adalah graf tak-berarah tak terhubung yang terdiri dari dua atau

lebih komponen berupa pohon.

Berdasarkan definisi di atas, sebuah hutan merupakan suatu graf yang tak berarah dan tak

terhubung, terdiri dari komponen (subgraf) yang berupa pohon. Jadi suatu hutan terdiri dari

banyak pohon.

Teorema 6.1.1 Suatu graf tak berarah merupakan pohon jika dan hanya jika setiap dua pasang

verteks hanya ada sebuah lintasan sederhana.

Bukti:

Pertama kita tunjukkan bahwa jika suatu graf tak berarah merupakan pohon maka setiap dua

pasang verteks hanya ada sebuah lintasan sederhana.

Anggap bahwa grafnya adalah T yang berupa pohon. Karena T berupa pohon, maka T

merupakan graf terhubung yang tidak memuat sirkuit sederhana. Ambil dua verteks u dan v di

T. Karena T terhubung, maka ada lintasan sederhana dari verteks u ke verteks v. Selanjutnya

akan ditunjukkan bahwa lintasan ini hanya satu-satunya. Misal ada dua lintasan sederhana dari

u ke v, katakan lintasan tersebut adalah:

Lintasan pertama : u-x1-x2-...-xr-v.

Lintasan kedua : u-y1-y2-...-ys-v.

Jika lintasan pertama dan lintasan kedua berbeda, maka deretan x1-x2-...-xr dan y1-y2-...-ys tidak

sama. Karena deretan x1-x2-...-xr dan y1-y2-...-ys tidak sama dan keduanya berawal dari verteks u

dan berakhir pada verteks v, maka kalau dua lintasan ini kita gabung akan membentuk sirkuit.


Hal bertentangan dengan graf T yang berupa pohon, dalam pohon tidak ada sirkuit. Oleh karena

itu, kedua lintasan tersebut harus sama.

Kedua kita tunjukkan bahwa jika setiap dua pasang verteks dalam suatu graf tak berarah hanya

ada sebuah lintasan sederhana maka graf tersebut merupakan pohon.

Anggaplah dalam suatu graf tak berarah T hanya ada sebuah lintasan sederhana diantara setiap

pasang verteks u dan v. Dengan demikian T merupakan graf yang terhubung. Karena lintasan

dari verteks u ke verteks v hanya ada satu, kita tidak bisa menemukan sirkuit sederhana dari

verteks u kembali ke verteks u. Karena graf T terhubung dan tidak mempunyai sirkuit

sederhana, maka graf T berupa pohon.

Contoh 6.1.2:

Perhatikan dengan teliti setiap graf pada Gambar 6.1.6. Graf G1 dan G2 merupakan pohon

karena setiap pasan node pada graf tersebut hanya ada satu lintasan yang menghubungkannya.

Untuk graf G3 bukan merupakan pohon karena ada sepasang node a dan node c yang memiliki

lebih dari satu lintasan, yaitu: a-b-f-e-c dan a-d-c. Untuk graf G4 bukan merupakan pohon

karena tak terhubung, akan tetapi graf tersebut membentuk dua komponen berupa pohon, oleh

karena itu G4 merupakan hutan.

a b c

d e f

a b c

d e f

a b c

d e f

a b c

d e f G1 G2 G3 G4

Gambar 6.1.6

Dalam penerapan pohon, salah satu dari node pada pohon sering dibuat sebagai akar (root).

Dari sebuah akar ini pasti ada lintasan tunggal menuju ke setiap node yang ada. Begitu kita

menentukan sebuah node pada pohon sebagai akar, kita berikan arah pada setiap edge dengan

asal/awal arah adalah dari akar. Sebagai gambaran, perhatikan graf pada Gambar 6.1.7.

a b c

d e f

a b c

d e f

Atau

a

b

c

d e f

Atau

a

b c

d

e

f

a b c

d e f

T T1 T2

Gambar 6.1.7

Graf T pada Gambar 6.1.7 merupakan pohon tak berakar. Dari pohon T, jika kita buat node b

sebagai akar maka didapat pohon berakar T1. Pada pohon berakar T1, dapat dibuat lintasan


tunggal yang berawal dari akar b ke setiap node lain a, c, d, e, atau f. Jika dari pohon T kita

buat node e sebagai akar maka didapat pohon berakar T2. Pada pohon berakar T2, dapat dibuat

lintasan tunggal yang berawal dari akar e ke setiap node lain a, b, c, d, atau f. Untuk pohon

berakar, penggambaran arah edge dapat dihilangkan, dengan perjanjian bahwa akar berada pada

paling atas, sedangkan arah edge adalah dari atas ke bawah.

Definisi 6.1.3 Pohon Berakar (Rooted Tree) T adalah suatu pohon yang salah satu nodenya

didefinisikan sebagai akar (root) r dan edgenya berarah sesuai arah lintasan dari node r melalui

edge tersebut.

Definisi 6.1.4 Untuk pohon T dengan akar r, didefinisikan:

i. Level (depth) dari node v di T adalah panjang lintasan dari node r ke node v.

ii. Kedalaman pohon T adalah maksimum dari semua level node yang ada di T.

iii. Daun (leaf) dari T adalah node berderajat satu selain node akar.

iv. Sebuah cabang (branch) dari T adalah sebuah lintasan dari node v ke node daun.

v. Orang tua (Parent) dari node v di T adalah sebuah node u sedemikian sehingga ada edge

(u,v) di T, dan node v dinamakan anak (child) dari u. Node-node yang mempunyai orang

tua sama dinamakan bersaudara (sibling).

vi. Pendahulu (Ancestor) dari node v yang bukan akar adalah semua node yang pada lintasan

dari akar ke v.

vii. Keturunan (Descendant) dari node v adalah semua node yang mempunyai pendahulu v.

viii. Node Internal dari T adalah node-node yang mempunyai anak

Definisi 6.1.4 Subpohon (Subtree) dari pohon T dengan node a sebagai akar adalah suatu

subgraf dari pohon T yang terdiri dari node a dan semua node keturunan a dan edge-edge yang

incident dengan semua node-node tersebut.


Contoh 6.1.3:

Perhatikan pohon T dengan 11 node yang berakar r seperti pada Gambar 6.1.8.

d

r

f

a b c

e

h i j

g

d

a

e

h

f

c

i j

g

i j

g

T T1 T2 T3 T4

Gambar 6.1.8 Sebuah pohon berakar r.

Akar dari pohon T adalah r.

Node internal dari pohon T adalah r, a, b, c, e, dan g.

Node daun dari pohon T adalah d, h, f, i, dan j.

Level(r) = 0, level(a) = level(b) = level(c) =1, level(d) = level(e) = level(f) = level(g) =2,

level(h) = level(i) = level(j) =3.

Kedalaman dari pohon T adalah 3.

T1, T2, T3, dan T4 masing-masing merupakan subpohon dari pohon T.

Contoh 6.1.4:

Perhatikan pohon T dengan akar a pada Gambar 6.1.9. Dapatkan orang tua dari c, anak dari g,

saudara dari h, semua pendahulu e, semua keturunan dari b, semua node internal, semua daun,

kedalaman T, subpohon dengan akar g.

c

a

i

b f g

d e l m

jh

k

T

Gambar 6.1.9.


Penyelesaian:

Orang tua dari c adalah b.

Anak dari g adalah h,i, dan j.

Saudara dari h adalah i, dan j.

Pendahulu dari e adalah c, b, dan a.

Keturunan dari b adalah c, d, dan e.

Node internal adalah a, b, c, g, h, dan j.

Node daun adalah d, e, f, i, k, l, dan m.

Kedalaman dari T adalah 3.

Subpohon dari T yang berakar g adalah pohon pada Gambar 6.1.10.

i

g

l m

jh

k

Gambar 6.1.10.

Pohon berakar yang mempunyai sifat bahwa semua node internal mempunyai banyak anak

sama sering dipakai dalam aplikasi. Misalnya dalam permasalahan pencarian, pengurutan,

pengkodean, dan sebagainya.

Definisi 6.1.5 Pohon m-ary (m-ary Tree) adalah pohon berakar yang setiap node internal

mempunyai anak tidak lebih dari m. Jika semua node internal pada pohon m-ary mempunyai

anak tepat m buah maka pohon tersebut dikatakan pohon m-ary penuh. Dan jika m=2 maka

dikatakan sebagai pohon biner (binary tree).

Contoh 6.1.5:

Perhatikan pohon – pohon pada Gambar 6.1.11. Apakah T1, T2, T3, dan T4 merupakan pohon m-

ary penuh?.

T1 T2


T3 T4

Gambar 6.1.11

Penyelesaian:

T1 merupakan pohon 2-ary penuh atau pohon biner.

T2 merupakan pohon 3-ary penuh atau pohon terner.

T3 merupakan pohon 5-ary penuh.

T4 bukan merupakan pohon m-ary penuh karena ada node internal yang beranak tiga dan ada

yang beranak 2.

Definisi 6.1.6 Pohon Berakar Terurut (Ordered Rooted Tree) adalah pohon berakar yang

setiap node internal mempunyai anak terurut dari kiri ke kanan.

Dalam pohon biner T, jika node internal v di T mempunyai dua anak, maka anak pertama

dinamakan anak kiri (left child) dan anak kedua dinamakan anak kanan (right child).

Subpohon yang berakar anak kiri dari v dinamakan subpohon kiri (left subtree) dan Subpohon

yang berakar anak kanan dari v dinamakan subpohon kanan (right subtree).

Contoh 6.1.6:

Perhatikan pohon binari pada Gambar 6.1.12. Manakah anak kiri dan kanan dari node d pada

pohon binari T? Dapatkan subphon kiri dan sub pohon kanan dari node c?

d

a

b c

e f j k

hg

i

Gambar 6.1.12

Penyelesaian:

Anak kiri dari node d pada pohon binari T adalah e dan anak kanan dari node d pada pohon

binari T adalah f.


Subpohon kiri dari dari node c adalah

g

Subpohon kanan dari dari node c adalah

j k

h

Contoh 6.1.7:

Sistem file dalam komputer dapat digambarkan dalam bentuk pohon berakar. File-file dalam

komputer dapat diorganisasikan dalam direktori-diretori. Sebuah direktori dapat memuat

banyak file dan subdirektori-subdirektori. Gambar 6.1.13 menyatakan sistem organisasi file

didalam salah satu hardisk komputer.

Apache

bin lib conf mysql

Documents

and Settings

Program Files Windows

C:\

Gambar 6.1.13 Sistem File Komputer.

Teorema 6.1.2 Sebuah pohon dengan n node mempunyai n-1 edge.

Bukti:

Misal node akar dari pohon adalah r. Kita buat korespondensi satu-satu antara node-node selain

r dan edge-edge, dengan cara mengawankan antara sebuag edge dengan sebuah node ujung dari

edge terebut. Sebagai gambaran lihat Gambar 6.1.14. Karena banyaknya node selain r ada n-1

buah dan terjadi korespondensi satu-satu dengan node-node selain r, maka banyaknya edge ada

n-1. [Terbukti]


d

r

f

a b c

e

h h i

g

Gambar 6.1.14 Korespondensi antara edge dan node selain r pada pohon.

Teorema 6.1.3 Sebuah pohon m-ary penuh dengan i buah node internal, mempunyai node

n=mi+1.

Bukti:

Pada pohon m-ary penuh, setiap node selian akar r merupakan anak dari node internal. Setiap

node internal mempunyai anak sebanyak m node. Sebagai gambaran lihat Gambar 6.1.15.

...

......

...

m node

m node

m nodem node

Merupakan node internal

selain akar, ada i node.

Gambar 6.1.15 Sebuah Pohon m-ary penuh

Karena node internal sebanyak i, maka ada node selain akar r sebanyak mi. Sehingga jumlah

total semua node yang ada pada pohon tersebut ada sebanyak mi+1. [Terbukti]

Teorema 6.1.4 Misal T merupakan sebuah pohon m-ary penuh dengan n node, i node internal,

dan l node daun. Jika salah satu dari n, i, dan l diketahui, maka dua lainnya dapat ditentukkan

sebagai berikut:

i. Jika diketahui n, maka m

ni

1 dan

m

nml

1)1(

ii. Jika diketahui i, maka n=mi+1 dan l=(m-1)i+1

iii. Jika diketahui l, maka 1

1

m

mln dan

1

)1(

m

li

Bukti:


Bukti teorema ini dipakai untuk latihan diskusi.

Contoh 6.1.8:

Misal operator seluler mengirim pesan pendek (SMS) ke 5 pelanggan. Bagi yang meneruskan

pesan tersebut ke 5 temannya akan mendapatkan bonus pulsa 100.000. Ada beberapa pelanggan

yang meneruskan pesan ini ke 5 temannya (anggap setiap pelanggan hanya menerima 1 pesan).

Ada juga yang tidak meneruskan pesa ini. Jika diketahui ada 201 orang yang hanya membaca

pesan, akan tetapi tidak meneruskan ke temannya, maka:

i. Berapa banyak orang yang sudah membaca pesan tersebut (termasuk operator yang

pertama mengirim pesan)?

ii. Berapa banyak bonus pulsa yang harus diberikan oleh operator seluler tersebut?

Penyelesaian:

Kita asumsikan bahwa, setiap orang yang mau meneruskan pesan ke temannya, pasti

meneruskan SMS sebanyak 5 kali ke teman yang berbeda, tidak ada seorangpun yag menerima

pesan lebih dari satu kali.

Permasalahan distribusi pesan ini dapat digambarkan dengan menggunakan pohon 5-ary

lengkap sebagai berikut.

Gambar 6.1.15 Sebuah pohon distribusi SMS, Pohon 5-ary penuh

Orang yang membaca pesan saja tanpa meneruskan pesan digambarkan dalam pohon sebagai

node daun, sehingga banyaknya node daun ada 201. Berdasarkan teorema di atas dapat

dihitung:


i. Banyaknya orang yang membaca pesan (termasuk operator) ada

25115

1201.5

1

1

m

mln

ii. Banyaknya orang yang menerusan pesan ada 504

1201

1

)1(

m

li , banyak bonus pulsa

yang harus diberikan oleh operator seluler = (50-1) . 100.000 = 4.900.000


6.2 Kegiatan Belajar II:

Pohon Perentang Minimal

Anggap graf pada Gambar 6.2.1 merupakan sistem jalan raya yang menghubungkan antar kota

besar di pulau Jawa. Dari perawatan jalan menginginkan bahwa dari setiap kota harus selalu

dapat menuju kota lain dengan melewati jalan yang baik, tanpa ada lubang maupun kerusakan.

Gambar 6.2.1 Sistem jalan raya yang menghubungkan kota besar di pulau Jawa

Jika semua jalan dirawat dalam kondisi baik semua, maka keinginan terpenuhi. Akan tetapi

untuk selalu mejaga jalan dalam keadaan baik semua membutuhkan biaya yang mahal.

Bagaimana kita selalu bisa berpindah dari kota satu ke kota lain tanpa melewati jalan rusak,

akan tetapi biaya perawatan sekecil mungkin. Hal bisa diselesaikan/dipenuhi dengan mencari

subgraf dengan banyaknya edge(jalan) minimal dan memuat semua verteks (kota). Dan graf

tersebut berupa pohon.

Definisi 6.2.1 Pohon Pembentang (Spanning Tree)

Misal G merupakan graf terhubung, Pohon pembentang (Spanning tree) dari graf G adalah

suatu subgraf dari G yang berupa pohon dan memuat semua verteks dari G.

Contoh 6.2.1:

Dapatkan tiga pohon pembentang pada graf sistem jalan raya Gambar 6.2.1.

Penyelesaian:

Tiga pohon pembentang dari graf Gambar 6.2.1 adalah T1, T2, dan T3 seperti yang terlihat pada

Gambar 6.2.2. Dan masih ada lagir pohon pembentang yang lainnya.

SbySmg

JgyBdg

Jkt

SbySmg

JgyBdg

Jkt

SbySmg

JgyBdg

Jkt

T1 T2 T3


Gambar 6.2.2.

Teorema 6.2.1 Graf sederhana G=(V,E) merupakan graf terhubung jika dan hanya jika graf G

mempunyai pohon pembentang.

Bukti:

Jika graf sederhana G=(V,E) terhubung maka graf G mempunyai pohon pembentang.

Anggap graf G=(V,E) terhubung. Jika graf G bukan merupakan pohon, maka graf G

mempunyai beberapa sirkuit sederhana. Kita hapus sebuah edge dari salah satu sirkuit

sederhana tersebut, menghasilkan graf terhubung G’ =(V’,E’) dengan V’=V dan |E’|=|E|-1.

Jika graf G’ bukan merupakan pohon, maka graf G’ mempunyai beberapa sirkuit sederhana.

Kita hapus sebuah edge dari salah satu sirkuit sederhana tersebut, menghasilkan graf

terhubung G” =(V”,E”) dengan V”=V dan |E”|=|E|-2.

Jika graf G” belum merupakan pohon, maka kita ulang terus langkah seperti di atas

sedemikian sehingga didapatkan graf terhubung G(k)

=(V(k)

,E(k)

) yang merupakan pohon,

dengan V(k)

=V dan |E(k)

|=|E|-k. Jadi graf G mempunyai pohon pembentang T= G(k)

=(V,E(k)

).

Jika graf sederhana G=(V,E) mempunyai pohon pembentang, maka graf G terhubung.

Anggap graf sederhana G=(V,E) mempunyai pohon pembentang T=(V,E’). Karena semua

verteks yang ada di graf G juga ada di pohon T , setiap pasan verteks ada lintasan yang

menghubungkannya. Jadi graf G merupakan graf terhubung.

[Terbukti]

Untuk suatu graf, ada banyak pohon pembentang untuk graf tersebut. Jika graf G merupakan

graf berbobot maka setiap pohon pembentang mempunyai total bobot yang berbeda-beda.

Sudah barang tentu, ada pohon pembentang yang total bobot edgenya paling kecil. Pohon

pembentang dengan total bobot edge terkecil ini yang dinamakan dengan pohon pembentang

minimal, secara formal didefinisikan berikut ini.

Definisi 6.2.2 Pohon Pembentang Minimal (minimal spanning tree)


Untuk suatu graf terhubung berbobot G=(V,E,W), pohon pembentang minimal T (minimal

spanning tree) dari graf G adalah suatu pohon pembentang untuk G yang mempunyai total

bobot paling kecil.

Contoh 6.2.2:

Perhatikan dengan seksama graf berbobot terhubung G pada Gambar 6.2.3 (a). Pohon T pada

Gambar 6.2.3 (b) merupakan pohon pembentang untuk graf G dan diantara pohon pembentang

lainnya untuk G, total bobot edge yang ada di T adalah terkecil. Oleh karena itu T merupakan

pohon pembentang minimal untuk G.

SbySmg

Jgy

Bdg

Jkt300

350

400

500

600

200170

SbySmg

Jgy

Bdg

Jkt300

350500

170

G T

(a) (b)

Gambar 6.2.3 Suatu Graf G dan pohon pembentang minimal untuk G.

Banyak permasalahan yang dapat diformulasikan dalam bentuk graf berbobot G dan

mempunyai penyelesaian dalam bentuk pohon pembentang minimal untuk G. Oleh karena itu,

bagaimana proses mencari pohon pembentang minimal merupakan hal yang dipandang penting.

Selanjutnya kita akan membahas langkah-langkah pencarian pohon pembentang minimal atau

algoritma pencarian pohon pembentang minimal.

Algoritma Prim

Algoritma ini dikembangkan oleh Robert Prim di tahun 1957. Robert Prim lahir di Texas tahun

1921. Dia menerima gelar BS. di bidang teknik Elektro dan gelar PhD. Di bidang matematika

dari Princeton Unversity. Saat mengembangkan algoritma ini dia bekerja sebagai direktur riset

Matematika dan Mekanika di Bell Telephone Laboratories. Algoritma yang dikembangkan oleh

Robert Prim ini digunakan untuk mencari pohon pembentang minimal pada suatu graf berbobot

terhubung G=(V,E,W) dan algoritmanya diberi nama algoritma Prim.

Strategi dari algoritma ini memanfaatkan konsep greedy. Pertama memilih edge (u,v) dengan

bobot terkecil, edge (u,v) beserta dengan verteks u dan v dimasukkan ke dalam pohon

pembentang T. Secara berulang-ulang, dicari edge dengan bobot terkecil yang bukan anggota T


dan yang terhubung dengan semua verteks di T dan tidak membentuk sirkuit di T. Edge tersebut

dimasukkan ke T. Langkah ini diulang-ulang hingga didapat n-1 edge di T.

Input algoritma Prim adalah graf berbobot terhubung G=(V,E,W) dengan |V|=n dan outputnya

adalah pohon T=(V,E’,W) yang merupakan pohon pembentang untuk graf G. Langkah-langkah

global dari algoritma Prim di atas dapat diperjelas sebagai berikut.

1. Ambil edge (u,v) dari G dengan bobot terkecil, edge (u,v) beserta dengan verteks u dan v

dimasukkan ke T.

2. Untuk i=1 sampai dengan n-2 lakukan:

a. Pilih edge e dari {(u,v) | u di T dan v tidak di T} yang mempunyai bobot terkecil dan

tidak membentuk sirkuit di T.

b. Masukkan edge e=(u,v) beserta verteks v ke pohon pembentang T.

3. Pohon pembentang minimal untuk G adalah T .

Untuk lebih memperjelas cara kerja lagoritma Prim, kita perlihatkan dua contoh berikut ini.

Contoh 6.2.3:

Dengan menggunakan algoritma Prim, dapatkan pohon pembentang minimal dari graf G pada

Gambar 6.2.4.

a

b

c

d

e

300

350

400

500

600

200170

Gambar 6.2.4.

Penyelesaian:

Langkah 1:

Ambil edge yang mempunyai bobot paling kecil, yaitu (a,b) berbobot 170, edge (a,b)

berserta dengan verteks a dan b dimasukkan ke pohon pembentang T. Secara gambar

didapat pohon T seperti berikut ini.

a

b

170

T


Langkah 2:

Untuk i = 1, lakukan:

a. Pilih edge e dari {(a,c), (b,d)} yang berbobot terkecil dan tidak membentuk sirkuit di

T. Didapat e = (b,d) dan

b. Tambahkan edge (b,d) beserta verteks d ke T. Secara gambar didapat pohon T

seperti berikut ini.

a

b

d500

170

T


a. Pilih edge e dari {(a,c), (d,e)} yang berbobot terkecil dan tidak membentuk sirkuit di

T. Didapat e = (d,e) dan

b. Tambahkan edge (d,e) beserta verteks e ke T. Secara gambar didapat pohon T

seperti berikut ini.

a

b

d

e

350

500

170

T


a. Pilih edge e dari {(a,c), (e,c), (e,c)} yang berbobot terkecil dan tidak membentuk

sirkuit di T. Didapat e = (e,c) yang berbobot 300, dan

b. Tambahkan edge (e,c) yang berbobot 300 beserta verteks c ke T. Secara gambar

didapat pohon T seperti berikut ini.

a

b

c

d

e

300

350

500

170

T

Langkah 3:

Pohon pembentang minimal untuk G adalah T seperti pada gambar di atas ini.


Contoh 6.2.4:

Dengan menggunakan algoritma Prim, dapatkan jaringan komunikasi dengan biaya minimal,

bila diketahui biaya dari masing-masing kota seperti pada graf G Gambar 6.2.5. [4]

$1000

$1600

$1300

$2000

$2200

$900 $800

$1400

$1200

$700

Denver

Chicago

Atlanta

New YorkSan

Francisco

Gambar 6.2.5 Biaya jaringan komunikasi antar kota.

Penyelesaian:

Langkah 1:

Ambil edge yang mempunyai bobot paling kecil, yaitu (Chicago,Atlanta) berbobot $700,

edge (Chicago,Atlanta) berserta dengan verteks Chicago dan Atlanta dimasukkan ke pohon

pembentang T. Secara gambar didapat pohon T seperti berikut ini.

$700

Chicago

Atlanta T

Langkah 2:


c. Pilih edge e dari {(Chicago, San Francisco), (Chicago, New York), (Chicago,

Denver), (Antlanta, New York) , (Antlanta, Denver) , (Antlanta, San Francisco)}

yang berbobot terkecil dan tidak membentuk sirkuit di T. Didapat e = (Antlanta,

New York) dengan bobot $800 dan

d. Tambahkan edge (Antlanta, New York) beserta verteks New York ke T. Secara

gambar didapat pohon T seperti berikut ini.


$800

$700

Chicago

Atlanta

New York

T


c. Pilih edge e dari {(Chicago, San Francisco), (Chicago, Denver), (Antlanta, Denver)

, (Antlanta, San Francisco), (New York, San Francisco) , (New York, Denver)} yang

berbobot terkecil dan tidak membentuk sirkuit di T. Didapat e = (Chicago, San

Francisco) dengan bobot $1200 dan

d. Tambahkan edge e= (Chicago, San Francisco) beserta verteks San Francisco ke T.

Secara gambar didapat pohon T seperti berikut ini.

$800

$1200

$700

Chicago

Atlanta

New YorkSan

Francisco

T


c. Pilih edge e dari {Chicago, Denver), (Antlanta, Denver), (New York, Denver), (San

Francisco, Denver)} yang berbobot terkecil dan tidak membentuk sirkuit di T.

Didapat e = (San Francisco, Denver) yang berbobot $900, dan

d. Tambahkan edge (San Francisco, Denver) yang berbobot $900 beserta verteks

Denver ke T. Secara gambar didapat pohon T seperti berikut ini.

$800

$1200

$700

Denver

Chicago

Atlanta

New YorkSan

Francisco

$900

T

Langkah 3:

Pohon pembentang minimal untuk G adalah T seperti pada gambar di atas ini.


6.3 Kegiatan Belajar III:

Penelusuran Pohon

Dalam pohon berakar terurut diperlukan suatu langkah-langkah pengunjung ke stiap node yang

ada, pengunjungan ke setiap node pada pohon ini dinamakan penelusuran (traversal) pohon.

Prosedur atau langkah-langkah dalam penelusuran pohon ini dinamakan algoritma penelusuran.

Dalam sub bab ini akan dibahas tiga buah penelusuran yang umum dipakai, yaitu : penelusuran

preorder, penelusuran inorder, dan penelusuran postorder.

Definisi 6.3.1 Penelusuran Preorder

Misal T merupakan suatu pohon berakar terurut dengan akar r dan T1, T2, ..., Tn masing-masing

merupakan subpohon dari T dengan akar masing-masing adalah anak pertama dari r, anak ke

dua dari r, ..., anak ke n dari r.

Penelusuran preorder pada pohon T adalah suatu penelusuran pohon yang berawal dari akar

r, dan dilanjutkan penelusuran preorder pada subpohon T1, kemudian penelusuran preorder

pada subpohon T2, dan seterusnya sampai terakhir penelusuran preorder pada subpohon Tn.

Untuk memperjelas definisi penelusuran preorder di atas, kita lihat Gambar 6.3.1. Arah garis

merupakan urutan penelusuran preorder, yaitu: r-a-d-e-h-b-f-c-g-i-j.

r

T1

T

T2

Tn

Langkah 1:

Kunjungi r

Langkah 2:

Kunjungi T1

secara preorder

Langkah 3:

Kunjungi T2

secara preorder

Langkah n+1:

Kunjungi Tn

secara preorder

d

r

f

a b c

e

h i j

g

T

(a) (b)

Gambar 6.3.1 Arah penelusuran preorder.

Contoh 6.3.1:

Tuliskan urutan pengunjungan node-node pada pohon Gambar 6.3.2 dengan penelusuran

preorder?.


d

a

b c

e f j k

hg

i Gambar 6.3.2.

Penyelesaian:

Langkah 1: Kita kunjungi akar a.

Langkah 2: Kita kunjungi secara preorder pada subpohon T1 yang berakar b.

d

b

e f

T1

Dalam penelusuran subpohon T1, dilakukan secara preorder, yaitu dengan

mengunjungi akar dari T1, yaitu b, dan dilanjutkan mengunjungi subpohon dari T1

yaitu subpohon T11 berikut ini.

d

e f

T11

Subpohon T11 dikunjungi secara preorder: mengunjungi akar d dan dilanjutkan

mengunjungi secara preorder subpohon yang berakar e dan subpohon yang berakar f.

Penelusuran subpohon T11 didapat: d-e-f.

Penelusuran subpohon T1 didapat: b-d-e-f.

Langkah 3: Kita kunjungi secara preorder pada subpohon T2 yang berakar c.

c

j k

hg

i

T2

Dalam penelusuran subpohon T2, dilakukan secara preorder, yaitu dengan

mengunjungi akar dari T2, yaitu c, dan dilanjutkan mengunjungi subpohon dari T2

yaitu subpohon T21 yang berakar g dan subpohon T22 .

Mirip pada penelusuran subpohon T1 , maka penelusuran subpohon T2 didapatkan

hasil: c-g-i-h-j-k.

Penelusuran preorder pohon T didapat: a-b-d-e-f- c-g-i-h-j-k.


Definisi 6.3.2 Penelusuran Inorder




Penelusuran inorder pada pohon T adalah suatu penelusuran pohon yang berawal dari

penelusuran inorder pada subpohon T1, dan dilanjutkan mengunjungi akar r, kemudian

dilanjutkan penelusuran inorder pada subpohon T2, dan seterusnya sampai terakhir penelusuran

inorder pada subpohon Tn.

Untuk memperjelas definisi penelusuran preorder di atas, kita lihat Gambar 6.3.3. Arah garis

merupakan urutan penelusuran preorder, yaitu: d-a-h-e-r-f-b-i-g-j-c.

r

T1

T

T2

Tn

Langkah 2:

Kunjungi r

Langkah 1:

Kunjungi T1

secara inorder

Langkah 3:

Kunjungi T2

secara inorder

Langkah n+1:

Kunjungi Tn

secara inorder

d

r

f

a b c

e

h i j

g

T

(a) (b)

Gambar 6.3.3 Arah penelusuran inorder.

Contoh 6.3.2:


inorder?.

Penyelesaian:

Langkah 1: Kita kunjungi secara inorder pada subpohon T1 yang berakar b.

d

b

e f

T1

Dalam penelusuran subpohon T1, dilakukan secara inorder, yaitu dengan

mengunjungi subpohon dari T1 yaitu subpohon T11 berikut ini.


d

e f

T11

Subpohon T11 dikunjungi secara inorder: mengunjungi secara inorder subpohon yang

berakar e, didapat e. dilanjutkan mengunjungi akar d dan kemudian subpohon yang

berakar f. Penelusuran inorder pada subpohon T11 didapat: e-d-f.

Setelah penelusuran inorder T11 dilanjutkan mengunjungi akar dari T1, yaitu b, dan

penelusuran T1 berhenti karena sudah tidak ada lagi subpohon untuk T1.

Penelusuran subpohon T1 didapat: d-e-f-b.

Langkah 2: Kita kunjungi akar dari pohon T, yaitu: a.

Langkah 3: Kita kunjungi secara inorder pada subpohon T2 yang berakar c.

c

j k

hg

i

T2

Dalam penelusuran subpohon T2, dilakukan secara inorder, yaitu dengan

mengunjungi subpohon dari T2 yaitu subpohon T21 yang berakar g dan didapat hasil

penelusuran: i-g, kemudian mengunjungi akar dari T2 (yaitu c), dan dilanjutkan

penelusuran inorder subpohon T22 yang berakar h dan didapat hasil penelusuran: j-h-

k.

Hasil penelusuran subpohon T2 adalah: i-g-c-j-h-k.

Penelusuran preorder pohon T didapat: d-e-f-b-a-i-g-c-j-h-k.

Definisi 6.3.3 Penelusuran Postorder




Penelusuran postrder pada pohon T adalah suatu penelusuran pohon yang berawal dari

penelusuran postorder pada subpohon T1, kemudian dilanjutkan penelusuran postorder pada

subpohon T2, dan seterusnya sampai penelusuran postorder pada subpohon Tn, dan dilanjutkan

mengunjungi akar r.


Untuk memperjelas definisi penelusuran postorder di atas, kita lihat Gambar 6.3.4. Arah garis

merupakan urutan penelusuran preorder, yaitu: d-h-e-a-f-b-i-j-g-c-r.

r

T1

T

T2

Tn

Langkah (n+1):

Kunjungi r

Langkah 1:

Kunjungi T1

secara

postorder

Langkah 2:

Kunjungi T2

secara

postorder

Langkah n:

Kunjungi Tn

secara

postorder

d

r

f

a b c

e

h i j

g

T

(a) (b)

Gambar 6.3.4 Arah penelusuran inorder.

Contoh 6.3.3:


postorder?.

Penyelesaian:

Langkah 1: Kita kunjungi secara postorder pada subpohon T1 yang berakar b.

d

b

e f

T1

Dalam penelusuran subpohon T1, dilakukan secara postorder, yaitu dengan

mengunjungi subpohon dari T1 yaitu subpohon T11 berikut ini.

d

e f

T11

Subpohon T11 dikunjungi secara postorder: mengunjungi secara postorder subpohon

yang berakar e, didapat e. dilanjutkan dengan mengunjungi subpohon yang

berakar f, didapat f. dan kemudian mengunjungi akar dari T11, yaitu r.

Penelusuran postorder pada subpohon T11 didapat: e-f-d.

Setelah penelusuran inorder T11 dilanjutkan mengunjungi akar dari T1, yaitu b, dan

penelusuran T1 berhenti karena sudah tidak ada lagi subpohon untuk T1.

Penelusuran subpohon T1 didapat: e-f-d-b.


Langkah 2: Kita kunjungi secara postorder pada subpohon T2 yang berakar c.

c

j k

hg

i

T2

Dalam penelusuran subpohon T2, dilakukan secara postorder, yaitu dengan

mengunjungi subpohon dari T2 yaitu subpohon T21 yang berakar g dan didapat hasil

penelusuran: i-g, kemudian penelusuran postorder subpohon T22 yang berakar h dan

didapat hasil penelusuran: j-k-h.

Hasil penelusuran subpohon T2 adalah: i-g-j-k-h-c.

Langkah 3: Kita kunjungi akar dari pohon T, yaitu: a.

Penelusuran preorder pohon T didapat: e-f-d-b-i-g-j-k-h-c-a.

Definisi 6.3.4 Pohon Ekpresi

Pohon ekspresi dari suatu ekspresi aritmatika E adalah suatu pohon yang merepresentasi

ekspresi aritmatika E dengan ketentuan:

i. Jika ekspresi E terdiri dari sebuah variabel atau konstanta, maka pohon ekspresinya adalah

sebuah node berlabel variabel atau konstanta tersebut.

ii. Jika ekspresi E=E1 op E2 memuat operasi biner (op: *,/,+,-,^), maka ekspresi E

digambarkan dengan pohon berakar op yang mempunyai anak kiri subpohon untuk E1 dan

anak kanan subpohon untuk E2.

iii. Jika ekspresi E= op E1 memuat operasi uner (op: -), maka ekspresi E digambarkan dengan

pohon berakar op yang mempunyai sebuah anak subpohon untuk E1.

Dari definisi di atas, suatu variabel atau konstanta digambarkan dalam node daun. Sedangkan

sebuah oprator digambarkan dalam node internal yang memiliki anak berupa sub ekspresi. Akar

dari pohon merupakan operator yang terakhir kali dioperasikan (presedensi operator paling

rendah) dalam ekspresi tersebut.


Contoh 6.3.4:

Ekspresi aritmatika (x+2)*(y-10)/2 direpresentasikan dalam bentuk pohon ekspresi seperti yang

terlihat pada Gambar 6.3.5 (a) dan (b).

x 2 y 10

+ -

/

2*

x 2 y 10

+

/

2

*

-

(a) (b)

Gambar 6.3.5 Pohon ekspresi untuk (x+2)*(y-10)/2.

Definisi 6.3.5 Notasi Prefix dan Postfix

Jika ekspresi infix aritmatika E mempunyai representasi pohon ekspresi T, maka:

i. Notasi Prefix untuk ekspresi E adalah suatu ekspresi yang dibentuk dari sederetan node-

node hasil penelusuran preorder pada pohon ekspresi T.

ii. Notasi Postfix untuk ekspresi E adalah suatu ekspresi yang dibentuk dari sederetan node-

node hasil penelusuran postorder pada pohon ekspresi T.

Contoh 6.3.5:

Dapatkan notasi prefix dan postfix dari ekspresi aritmatika E: (x+2)*(y-10)/2 yang

direpresentasikan dalam bentuk pohon ekspresi seperti yang terlihat pada Gambar 6.3.5 (a).

Penyelesaian:

Notasi prefix dari E : Kita telusuri pohon T pada Gambar 6.3.5 (a) secara preorder dan

menghasilkan / * + x 2 - y 10 2.


Notasi postfix dari E : Kita telusuri pohon T pada Gambar 6.3.5 (a) secara postorder dan

menghasilkan x 2 + y 10 - * 2 / .


Soal Latihan

Pohon

1. Manakah graf tak berarah G=(V, E) berikut ini yang merupakan pohon.

a. Himpunan V = {a, b, c, d} dan E adalah himpunan kosong.

b. Himpunan V = {a, b, c, d} dan E ={{a,b}, {b,c}, {c,d}}.

c. Himpunan V = {a, b, c, d, e} dan E ={{a,b}, {a,c}, {b,d}, {b,e}}.

2. Manakah graf tak berarah G=(V, E) berikut ini yang merupakan pohon.

a. Himpunan V hanya mempunyai 1 elemen dan E adalah himpunan kosong.

b. G merupakan graf lengkap dengan 4 buah verteks.

c. G merupakan graf terhubung dengan setiap verteksnya berderajat 2.

d. G merupakan graf terhubung dengan setiap verteksnya berderajat ganjil.

e. G merupakan graf terhubung dengan setiap pasang verteks pada G hanya ada sebuah

lintasan dengan panjang ganjil.

f. G merupakan graf terhubung dengan setiap pasang verteks pada G hanya ada sebuah

lintasan dengan panjang genap.

g. G merupakan graf terhubung dengan setiap pasang verteks pada G hanya ada duah

lintasan.

h. G merupakan graf terhubung yang tidak memuat cycle.

3. Dalam suatu topologi jaringan komputer dikenal topologi star, token ring, dan bus

(ethernet), lihat gambar topologi jaringan dibawah ini.

Token ring Star

SDCoreBuilder 3500

Com3

Ethernet

Periksalah topologi jaringan yang manakah yang merupakan pohon !.

4. Perhatikan pohon T berakar r seperti pada gambar berikut ini.

d

r

b c

e f

hg

i

T

Dapatkan:

a. Akar dari pohon T .

b. Node internal dari pohon T.


c. Node daun dari pohon T.

d. Kedalaman dari setiap node daun.

e. Orang tua dari node g dan h, apakah g dan h bersaudara ?.

f. Keturunan dari node b dan c.

g. Subpohon yang berakar node b dan c.

5. Periksalah apakah pohon – pohon berikut ini merupakan subpohon dari pohon T pada soal

sebelumnya ?.

d

b

e f

d

b

e

c

hg

i

c

j k

hg

i

T1

T2 T

3T

4

6. Periksalah apakah pohon – pohon berikut ini merupakan pohon m-ary penuh ?.

Penelusuran Pohon

7. Gambarkan graf tak berarah G=(V, E) dengan himpunan V dan E adalah:

a.

8. Ga


DAFTAR PUSTAKA:

1. GRIMALDI, R.P., “Discrete and Combinatorial Mathematics - An Applied

Introduction”, Addison-Wesley Publishing Co., 1989.

2. Liu, C.L., “Elements Of Discrete Mathemathics”, McGraw-Hill, 1986.

3. ROBERT, F.S., “Applied Combinatorics”, Prentice-Hall Inc., 1984.

4. ROSEN, K.H., “Discrete Mathematics and Its Applications”, McGraw-Hill, 2003.

5. Seymour L., Marc L.L., “Schaum’s Outline of Theory and Problems of Discrete

Mathematics”, Second Edition. McGraw-Hill, 1997.