BAB I

BEBERAPA KONSEP DAN SIFAT DASAR GRAPH

1.1. PENDAHULUAN

Pada bagian ini akan dipelajari sejarah singkat perkembangan teori graph

serta beberapa pengertian dasar teori graph mencakup definisi teori graph; graph

hingga dan graph tak hingga; insidensi dan ajasensi; titik (simpul) terisolasi, titik

anting, serta derajat suatu titik. Setelah mengenal beberapa pengertian teori graph,

selanjutnya akan disajikan materi graph sebagai model matematika dan aplikasinya

yang mencakup graph sebagai model matematika, graph berarah sebagai model

matematika, jaringan kerja, silsilah keluarga, sistem komunikasi, jaringan

transportasi, desain arsitektur, dan ikatan kimia.

Mengingat materi yang akan dpelajari ini merupakan landasan utama dalam

mempelajari modul-modul berikutnya, maka pemahaman yang baik tentang materi

yang disajikan merupakan langkah yang tepat dalam upaya memahami materi setiap

modul secara keseluruhan. Setelah mempelajari modul ini diharapkan mengenal

sejarah singkat munculnya teori graph, beberapa pengertian dasar teori graph, serta

aplikasi teori graph.

Setelah mempelajari modul ini, secara khusus Anda diharapkan mampu:

1. Menjelaskan sejarah perkembangan teori graph;

2. Menjelaskan beberapa pengertian dasar teori graph;

3. Menggambar graph sebagai model matematika.

1.1.1. SEJARAH SINGKAT TEORI GRAPH

Teori graph lahir pada Tahun 1736 melalui tulisan Euler yang berisi tentang

upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa.

Kurang lebih seratus tahun setelah lahirnya tulisan Euler tersebut tidak ada

perkembangan yang berarti berkenaan dengan teori graph. Tahun 1847, G.R.

Kirchoff (1824 – 1887) berhasil mengembangkan teori pohon (Theory of trees) yang

digunakan dalam persoalan jaringan listrik. Sepuluh tahun kemudian, A. Cayley

(1821 – 1895) juga menggunakan konsep pohon untuk menjelaskan permasalahan

kimia yaitu hidrokarbon. Pada masa Kirchoff dan Cayley juga telah lahir dua hal

penting dalam teori graph. Salah satunya berkenaan dengan konjektur empat warna,

yang menyatakan bahwa untuk mewarnai sebuah atlas cukup dengan menggunakan

empat macam warna sedemikian hingga tiap negara yang berbatasan akan memiliki

warna yang berbeda.

Para ahli teori graph berkeyakinan bahwa orang yang pertama kali

mengemukakan masalah empat warna adalah A.F. Mobius (1790 – 1868) dalam

salah satu kuliahnya di Tahun 1840. Sepuluh tahun kemudian, A. De Morgan (1806

– 1871) kembali membahas masalah ini bersama ahli-ahli matematika lainnya di kota

London. Dengan demikian tulisan De Morgan dianggap sebagai referensi pertama

berkenaan dengan masalah empat warna. Masalah empat warna ini menjadi sangat

terkenal setelah Cayley mempublikasikannya Tahun 1879 dalam Proceedings of the

Royal Geographic Society volume pertama.

Hal lain yang penting untuk dibicarakan sehubungan dengan perkembangan

teori graph adalah apa yang dikemukakan oleh Sir W.R. Hamilton (1805 – 1865).

Pada Tahun 1859 dia berhasil menemukan suatu permainan yang kemudian dijualnya

ke sebuah pabrik mainan di Dublin. Permainan tersebut terbuat dari kayu berbentuk

dodecahedron beraturan yakni berupa sebuah polihedron dengan 12 muka dan 20

pojok. Tiap muka berbentuk sebuah pentagon beraturan dan tiap pojoknya dibentuk

oleh tiga sisi berbeda. Tiap pojok dari dodecahedron tersebut dipasangkan dengan

sebuah kota terkenal seperti London, New York, Paris, dan lain-lain. Masalah dalam

permainan ini adalah, kita diminta untuk mencari suatu rute melalui sisi-sisi dari

dodecahedron sehingga tiap kota dari 20 kota yang ada dapat dilalui tepat satu kali.

Walaupun saat ini masalah tersebut dapat dikategorikan mudah, akan tetapi pada saat

itu tidak ada seorang pun yang bisa menemukan syarat perlu dan cukup dari

eksistensi rute yang dicari. Kurang lebih setengah abad setelah masa Hamilton,

aktivitas dalam bidang teori graph dapat dikatakan relatif kecil. Pada Tahun 1920-an

kegiatan tersebut muncul kembali yang dipelopori oleh D. Konig. Konig berupaya

mengumpulkan hasil-hasil pemikiran para ahli matematika tentang teori graph

termasuk hasil pemikirannya sendiri, kemudian dikemasnya dalam bentuk buku yang

diterbitkan pada Tahun 1936. Buku tersebut dianggap sebagai buku pertama tentang

teori graph.

Tiga puluh tahun terakhir ini merupakan periode yang sangat intensif dalam

aktivitas pengembangan teori graph baik murni maupun terapan. Sejumlah besar

penelitian telah dilakukan, ribuan artikel telah diterbitkan dan lusinan buku telah

banyak ditulis. Di antara orang terkenal yang banyak berkecimpung dalam bidang ini

adalah Claude Berge, Oysten Ore, Paul Erdos, William Tutte, dan Frank Harary.

1.2. Konsep Dasar Pada Graph

1.2.1.Pengertian Dasar Graph

Sebuah graph linier (atau secara sederhana disebut graph) G = (V, E) terdiri

atas sekumpulan objek V = {v1, v2, ...} yang disebut himpunan titik, dan sebuah

himpunan lain

E = {e1, e2, ...} yang merupakan himpunan sisi sedemikian hingga tiap sisi ek

dikaitkan dengan suatu pasangan tak terurut (vi, vj ). Titik vi, vj yang berkaitan

dengan ek disebut titik-titik ujung sisi ek. Cara merepresentasikan sebuah graph yang

paling umum adalah berupa diagram. Dalam diagram tersebut, titik-titik dinyatakan

sebagai noktah dan tiap sisi dinyatakan sebagai segmen garis yang menghubungkan

tiap dua titik. Untuk lebih jelasnya perhatikan contoh graph pada Gambar 1.1 di

bawah ini.

Gambar 1.1.

Graph dengan lima titik dan tujuh sisi

Dalam sebuah graph, seperti terlihat pada contoh di atas, dimungkinkan

adanya suatu sisi yang dikaitkan dengan pasangan (v1, v2). Sisi yang dua titik

ujungnya sama disebut loop. Dalam graph pada Gambar 1.1, e1 merupakan sebuah

loop. Dari contoh di atas juga perlu dicatat bahwa dalam sebuah graph dimungkinkan

adanya lebih dari satu sisi yang dikaitkan dengan sepasang titik. Sebagai contoh, e4

dan e5 pada graph di atas dikaitkan dengan pasangan titik (v1, v3). Pasangan sisi

semacam ini disebut sisi-sisi paralel atau sejajar.

Sebuah graph yang tidak memiliki loop dan sisi paralel disebut graph

sederhana. Dalam beberapa literatur teori graph, pembahasan hanya dibatasi pada

graph sederhana, akan tetapi dalam banyak aplikasi teknik, penggunaan loop dan sisi

paralel sangat diperlukan. Untuk membedakan antara graph yang memuat loop dan

sisi paralel dengan graph yang tidak memuat kedua hal tersebut, sebagian penulis

menggunakan istilah graph sederhana untuk graph yang tidak memuat loop dan sisi

paralel, serta graph umum untuk yang lainnya.

Dalam sebuah graph mungkin terdapat dua sisi atau lebih yang

menghubungkan dua titik yang berlainan. Kedua sisi tersebut dinamakan sisi rangkap

atau sisi ganda. Graph yang mengandung loop atau sisi rangkap dinamakan graph

ganda.

Contoh:

Gambar 1.2

(a) (b)

Gambar 1.2. (a).Graph Sederhana

(b). Graph Tak Sederhana

Dalam menggambar sebuah graph, bentuk sisi dapat berupa garis lurus atau

garis lengkung. Demikian pula ukurannya, dalam penggambaran sebuah graph

tidaklah diperhatikan. Hal yang penting untuk diperhatikan dalam sebuah graph

adalah insidensi antara titik-titik dengan sisi-sisinya. Sebagai contoh, dua graph yang

disajikan pada Gambar 1.3 di bawah ini menggambarkan graph yang sama, karena

insidensi antara sisi-sisi dan titik-titik pada graph tersebut adalah sama.

Gambar 1.3.

Graph yang sama

Sekarang perhatikan Gambar 1.4 di bawah ini. Pada gambar tersebut sisi e

dan f nampaknya seperti berpotongan, akan tetapi perpotongannya tidak berupa titik.

Kedua sisi seperti itu harus dipandang sebagai dua ruas garis yang terletak pada dua

bidang berbeda, sehingga kedua sisi itu tidak berpotongan.

Gambar 1.4.

Sisi e dan f tidak berpotongan

1.2.2. Beberapa Jenis Graph

Walaupun dalam definisi graph tidak disebutkan secara eksplisit bahwa

himpunan titik V dan himpunan sisi E tidak perlu merupakan sebuah himpunan

hingga, akan tetapi dalam kebanyakan aplikasi teori graph kedua himpunannya

tersebut kebanyakan merupakan himpunan hingga. Sebuah graph G = (V, E) dengan

V dan E hingga disebut graph hingga atau graph terhingga dan jika sebaliknya yakni

jika V dan E tak hingga, maka G disebut graph tak hingga. Contoh graph hingga

dapat dilihat pada Gambar 1.1, Gambar 1.2, Gambar 1.3 dan Gambar 1.4. Sedangkan

Gambar 1.5 di bawah ini merupakan contoh dari bagian graph tak hingga.

Gambar 1.5.

Bagian dari graph tak hingga

Untuk pembahasan selanjutnya, yang dimaksud dengan graph dalam modul ini

adalah graph hingga.

Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan

menjadi 2 jenis

1. Graph tak berarah (undirected graph): graph yang sisinya tidak mempunyai

orientasi arah

2. Graph berarah (directed graph atau digraph): graph yang setiap sisinya

diberikan orientasi arah.

Graph Lengkap (complete graph) Kn adalah graph dengan n simpul dan setiap

pasang simpulnya terhubung oleh satu ruas. Derajat setiap titik sama.

Gambar 1.7

Graph Lengkap

Berdasarkan sifat keterhubungan

1. Perjalanan (Walk)

Perjalanan atau walk pada suatu graph G adalah barisan titik dan sisi secara

berganti-ganti v1 , e1 , v2 , e2⋯ vn en−1dimana sisi e1 menghubungkan vidan vi+1dan

dapat ditulis barisan sisi atau barisan titik saja (e1 ,e2⋯ en−1atauv1 , v2⋯ vn), dalam hal

ini v1disebut titik awal, dan vndisebut titik akhir. Titik awal dan titik akhir dari suatu

walk mungkin saja sama, dengan demikian disebut closed walk.

2. Lintasan (Trail)

Lintasan dari suatu graph G merupakan suatu walk dimana setiap sisi-nya

berlainanatau dengan kata lain tidak boleh berulang.

3. Jalur (Path)

Path dari suatu graph G adalah suatu walk dimana semua unsur titik-nya

berbedakecuali untuk titik awal dan titik akhir.

4. Terhubung (Connected)

Suatu graph G dikatakan connected jika untuk setiap pasangan titik didalam

Gterdapat paling sedikit satu path. Sebaliknya, jika didalam suatu graph G terdapat

pasangan titik yang tidak mempunyai path penghubung, graph yang demikian

disebut disconnected graph.

5. Sirkuit (Cycle)

Sirkuit atau cycle adalah path dengan titik awal sama dengan titik akhir.

Banyaknya sisi yang terdapat dalam suatu walk disebut length dari path tersebut.

1.3. Matriks Graph

1. Matriks Kedekatan (Adjacency Matrix)

2.

1.4. GRAPH BAGIAN (SUBGRAPH)

Sebuah graph g disebut graph bagian atau subgraph dari G jika semua titik dan

sisi dari g termuat dalam G, dan tiap sisi dari g memiliki titik-titik ujung yang sama

baik dalam g maupun dalam G. Sebagai contoh, graph dalam Gambar 1.8 bagian (b)

merupakan sebuah graph bagian dari graph gambar (a). Karena konsep subgraph

dapat dianalogikan dengan konsep himpunan bagian dalam teori himpunan, maka

sebuah subgraph dapat dipandang sebagai bagian dari graph yang lain. Untuk

menyatakan bahwa “g merupakan bagian dari graph G” dapat ditulis g ⊂ G. Jika kita

telaah lebih jauh, maka akan diperoleh beberapa sifat berikut ini.

1. Setiap graph merupakan subgraph dari dirinya sendiri.

2. Subgraph dari suatu subgraph dari G adalah subgraph dari G.

3. Sebuah titik dalam graph G merupakan subgraph dari G.

4. Sebuah sisi dari G bersamaan dengan kedua titik ujungnya jugamerupakan

subgraph dari G.

Gambar 1.8.

Subgraph atau Graph Bagian

Subgraph Disjoin Sisi: Dua (atau lebih) subgraph g1 dan g2 dari graph

Gdisebut disjoin sisi jika g1 dan g2 tidak memiliki sisi sekutu. Sebagai contoh,

perhatikan Gambar 1.9 dan Gambar 1.10 berikut ini.

Gambar 1.9.

Gambar 1.10

Gambar 1.10 (a) dan (b) merupakan dua subgraph dari Graph pada Gambar

1.9 yang disjoin sisi. Walaupun dua graph disjoin sisi tidak memiliki sisi yang

bersekutu, akan tetapi kedua graph tersebut bisa memuat titik-titik yang sama. Dua

subgraph yang tidak memiliki titik-titik persekutuan disebut disjoin titik.

1.5. Derajat Titik Graph

Jika sebuah titik v1 merupakan titik ujung dari suatu sisi ej , maka v1 dan ej

disebut saling berinsidensi atau titik v1 insiden dengan sisi ej. Sebagai contoh, pada

Gambar 1.1 di atas sisi e2, e6, dan e7 adalah sisi-sisi yang insiden dengan titik v4. Dua

sisi yang tidak paralel disebut ajasen, bila kedua sisi tersebut insiden dengan titik

yang sama. Sebagai contoh, e2 dan e7 dalam Gambar 1.1 merupakan dua sisi yang

ajasen. Selain itu, dua buah titik disebut ajasen jika kedua titik tersebut merupakan

titik-titik ujung dari sisi yang sama. Dalam Gambar 1.1, v4 dan v5 adalah dua titik

yang saling ajasen, sedangkan titik v1 dan v4 merupakan dua titik yang tidak saling

ajasen.

Jumlah atau banyaknya sisi yang insiden dengan suatu titik vi (loop dihitung

dua kali), disebut derajat (degree) dari titik tersebut, dinotasikan d(vi ). Sebagai

contoh, dalam Gambar 1.1, d (v1 ) = d (v4 ) = 3, d (v2 ) = 4, dan d (v5 ) = 1. Derajat

suatu titik sering juga disebut valensi dari titik tersebut.

Selanjutnya pandang sebuah graph G dengan e sisi dan n titik v1, v2, ..., vn.

Karena tiap sisi menyumbangkan dua derajat, maka jumlah derajat dari semua titik

dalam G sama dengan dua kali jumlah sisi dalam G.

Dengan demikian,

∑ d ( v )=2|E| (1)

Sebagai contoh, pada Gambar 1.1

d (v1 ) + d (v2 ) + d (v3 ) + d (v4 ) + d (v5 ) = 3 + 4 + 3 + 3 + 1 = 14 = dua kali jumlah

sisi

Berdasarkan persamaan (1) kita peroleh teorema berikut.

Teorema 1

Banyaknya titik berderajat ganjil dalam sebuah graph selalu genap.

Bukti

Jika titik-titik berderajat ganjil dan genap kita pandang secara terpisah, maka jumlah

ruas kiri persamaan (1) dapat dinyatakan sebagai jumlah dari dua bilangan. Pertama

diperoleh dari titik-titik berderajat ganjil, dan kedua dari titik-titik berderajat genap.

Jadi,

∑i=1

n

d (v¿¿ i¿)=∑ d (v¿¿ j)+∑ d (v¿¿k )¿¿¿¿ (2)

dengan ∑ d (v¿¿ j)¿dari titik-titik genap dan ∑ d (v¿¿k )¿dari titik-titik ganjil.

Karena ruas kiri persamaan (2) genap, dan suku pertama dari Ruas kanan

adalah genap, maka suku kedua ruas kanan juga pasti genap.

∑ d (vk¿)¿= sebuah bilangan genap. (3)

Karena dalam persamaan (3) tiap d(vk) adalah bilangan ganjil, maka jumlah

keseluruhannya pastilah genap. (terbukti)

Sebuah graph dengan semua titiknya berderajat sama disebut graph reguler.

Selanjutnya akan dibahas bagaimana graph dapat digunakan untuk menunjukkan

hubungan tertentu antara objek-objek sembarang. Untuk mempelajari keterhubungan

objek-objek itu secara lebih mendalam, maka kita perlu mempelajari teori graph

secara lebih mendetil. Kita memerlukan istilah tertentu untuk menunjukkan

bagaimana kedudukan titik dan garis dalam graph itu. Istilah ini berlaku untuk semua

graph.

Sebuah titik yang tidak memiliki sisi insiden disebut titik terisolasi. Dengan

kata lain, titik terisolasi adalah titik yang berderajat nol. Titik v4 dan v7 dalam

Gambar 1.11 di bawah ini adalah dua contoh titik terisolasi. Sebuah titik berderajat

satu disebut titik anting/ujung. Titik v3 dalam Gambar 1.11 merupakan contoh titik

anting. Dua sisi yang saling berajasensi atau berbatasan disebut seri jika titik

sekutunya berderajat satu. Dalam Gambar 1.11, dua sisi yang insiden dengan v1

adalah seri.

Gambar 1.7.

Graph yang memuat titik terisolasi, sisi seri, dan titik anting

LATIHAN

Untuk memperdalam pemahaman Anda mengenai materi di atas, kerjakanlah

latihan berikut!

1) Teori graph lahir pada Tahun 1736 melalui tulisan Euler yang mengupas

masalah?

2) G.R. Kirchoff berhasil mengembangkan salah satu cabang/bagian teori graph

yang disebut teori?

3) Pada Gambar 1.1, sebutkan sebuah sisi yang dua titik ujungnya sama!

4) Perhatikan kembali graph pada Gambar 1.1. Apakah graph tersebut memiliki

sisi sejajar?

5) Apa yang dimaksud dengan graph sederhana!

6) Perhatikan kembali graph pada Gambar 1.1. Sebutkan sisi-sisi yang insiden

dengan titik v3!

7) Jika dua buah sisi yang tidak paralel insiden di sebuah titik yang sama, maka

kedua sisi itu disebut .....

8) Banyaknya titik berderajat ganjil dalam sebuah graph selalu ....

BAB II

GRAPH POHON (TREE)

2.1. Definisi Pohon

Diantara graph tersambung, bentuk terpenting dan paling sederhana adalah

pohon. Lebih lanjut, pohon pembentang (spanning trees) terlihat pada semua graph

tersambung. Pohon sangat banyak dijumpai dalam berbagai penerapan, terutama

dalam ilmu komputer. Contoh yang sudah dikenal adalah silsilah keluarga dan bagan

organisasi. Pohon dapat digunakan untuk menunjukkan, mengorganisasikan dan

menganalisis jaringan listrik, hubungan produsen-konsumen dan relasi bisnis dan

lain sebagainya.

Kirchoff (1824-1887) mengembangkan teori pohon untuk diterapkan dalam

jaringan listrik. Selanjutnya Arthur Cayle (1821-1895) mengembangkan graph jenis

ini sewaktu mencacah isomer hidrokarbon jenuh Cn H2 n+2. Sekarang pohon

digunakan secara luas dalam linguistik dan ilmu komputer.

Definisi 1:

pohon adalah sebuah graph tersambung yang tidak memiliki sikel.

Contoh 1

Hierarki administrasi organisasi OSIS suatu SMA berbentuk seperti pada Gambar 1.1

Gambar 2.1

Contoh 2

Pada Tahun 1857, Arthur Cayley mempelajari hidrokarbon, ikatan kimia

yang terbentuk dari atom hidrogen dan karbon. Dia mengetahui bahwa atom

hidrogen terikat (secara kimia) dengan satu atom yang lainnya, dan setiap atom

karbon terikat dengan empat atom lainnya. Perhatikan Gambar 1.2 berikut.

Gambar 2.2

Diagram kimia di atas dapat digambar kembali sebagai graph yang diilustrasikan

pada Gambar 2.3.

Gambar 2.3

Contoh 3

Gambar 2.4

Gambar 2.4 (a) dan 2.4 (b) merupakan pohon, sedangkan Gambar 2.4 (c) dan

2.4 (d) bukan pohon, karena Gambar 2.4 (c) graphnya tidak terhubung, sedangkan

Gambar 2.4 (d) graphnya memiliki sikel.

Beberapa sifat dasar dari sebuah pohon, akan diuraikan dalam teorema-teorema

berikut.

Teorema 1

Jika T pohon, maka untuk setiap dua titik u dan v yang berbeda di T terdapat

tepat satu lintasan (path) yang menghubungkan kedua titik tersebut.

Bukti

Misalkan ada lintasan (path) berbeda yang menghubungkan titik u dan titik v

di T, katakanlah e1 dan e2, dengan e1≠e2. Maka e1 dan e2 akan menghubungkan titik u

dan titik v, sehingga ada dua lintasan yang terhubung pada kedua titik tersebut dan

membentuk sikel. Berdasarkan definisi, T tidak memiliki sikel. Dengan demikian,

haruslah e1=e2. Hal ini bertentangan dengan pemisalan bahwa e1≠e2. Jadi, terbukti

bahwa setiap dua titik yang berbeda di T memiliki tepat satu lintasan yang

menghubungkan kedua titik tersebut.

Teorema 2

Banyaknya titik dari sebuah pohon T sama dengan banyaknya sisi ditambah

satu atau ditulis:

Jika T pohon, maka |V (T)| = |E (T)| +1

Bukti

Kita buktikan teorema di atas dengan induksi pada |V(T)|. Jika pohon T

mempunyai satu titik, jelas banyak sisi T adalah nol. Jadi teorema benar untuk pohon

T dengan satu titik. Asumsikan bahwa pernyataan dalam teorema benar untuk pohon

dengan k titik, artinya jika pohon T mempunyai paling banyak k titik, maka |V(T)| = |

E(T)| + 1.

Akan ditunjukkan bahwa jika pohon T mempunyai k + 1 titik maka |V(T)| = |

E(T)| + 1. Misalkan T adalah pohon dengan k + 1 titik dan e adalah sebuah sisi T.

Maka T - e memiliki tepat dua komponen T1 dan T2, dan masing-masing komponen

adalah pohon dengan titik kurang dari k + 1. Sehingga menurut asumsi, |V(T i)| = |

E(Ti)| + 1 ; i = 1,2.

Selanjutnya |E(T)| = |E(T1)| + |E(T2)| + 1, sehingga

|V(T)| = |V(T1)| + |V(T2)|

= |E(T1)| + 1 + |E(T2)| + 1

= (|E(T1)| + |E(T2)| + 1) + 1

= |E (T)| + 1

Dengan demikian teorema terbukti.

Contoh 4

Dinas rahasia Amerika Serikat (CIA) telah membentuk jaringan kerja antara

10 agen rahasia yang bekerja di bidang teknologi industri tingkat tinggi. Penting bagi

setiap agen untuk dapat berkomunikasi dengan agen lain secara langsung atau tidak

langsung (salah satu) melalui suatu mata rantai. Penentuan lokasi rahasia sulit

dilakukan, dan CIA ingin agar ada sesedikit mungkin tempat-tempat pertemuan

rahasia itu.

Untuk menjaga kerahasiaan, tidak lebih dari dua agen yang boleh mengetahui

tempat pertemuan. Jaringan komunikasi ini dapat disajikan dengan graph yang

titiknya menunjukkan agen rahasia dan sisinya menghubungkan dua titik jika agen

itu mengetahui tempat pertemuan yang sama. Ternyata graph ini merupakan pohon

dengan 10 titik, sehingga semuanya diperlukan sembilan tempat pertemuan rahasia.

Teorema 3

a. Bila suatu sisi dihapus dari pohon (dan titiknya tetap), maka diperoleh graph

yang tidak terhubung, dan karenanya graph itu bukan pohon.

b. Bila sebuah sisi ditambahkan pada pohon (tanpa menambah titik baru),

diperoleh graph yang memiliki sikel, dan karena itu graph tersebut bukan

pohon.

Bukti

Jika sebuah sisi ditambahkan atau dihapuskan dari pohon, graph baru yang

diperoleh tidak lagi merupakan pohon, berdasarkan teorema 2. Karena penghapusan

sebuah sisi menjadikan graph itu tidak terhubung, dan penambahan sisi membentuk

sikel, maka teorema terbukti.

Teorema berikut memberikan cara-cara tertentu untuk mengkarakterisasikan

pohon. Pembuktiannya dikerjakan sebagai latihan.

Teorema 4

Pernyataan berikut ini ekuivalen untuk pohon T.

a. T adalah pohon.

b. T terhubung dan banyak titiknya lebih satu dari banyak sisinya.

c. T tidak memiliki sikel dan banyak titiknya lebih satu dari banyak sisinya.

d. Ada tepat satu lintasan (path) sederhana antara setiap dua titik di T.

e. T terhubung dan penghapusan sembarang sisi pada T menghasilkan graph yang

tidak terhubung.

f. T tidak memiliki sikel dan penambahan sembarang sisi menghasilkan sikel pada

graph itu.

Definisi 2

Hutan adalah graph tanpa sikel.

Contoh 5

Gambar 2.5

Gambar 2.5 adalah suatu hutan yang terdiri atas 3 komponen.

POHON PUSAT DAN BIPUSAT

Pada pembuktian hasil berkenaan dengan pohon, sering dijumpai pembuktian

yang memudahkan apabila dimulai dari titik tengah pohon dan kemudian bergerak ke

titik yang lebih luar, untuk membangun pohon sebagaimana yang kita kehendaki.

Untuk memperoleh titik tengah suatu pohon dilakukan penyelidikan sebagai berikut.

Misalkan G suatu pohon. Hapuslah semua titik yang berderajad satu, bersama

dengan sisi yang berinsidensi dengannya. Ulangi cara itu hingga tinggal sebuah titik

atau dua buah titik yang dihubungkan oleh sebuah sisi. Jika pohon itu tinggal sebuah

titik, maka titik itu disebut pusat (center) dan jika tinggal dua buah titik, maka dua

titik itu disebut dwipusat (bicenter).

Pohon yang mempunyai pusat disebut pohon pusat, dan pohon yang memuat

dwipusat disebut pohon dwipusat. Setiap pohon adalah salah satu dari pusat atau

dwipusat, tetapi tidak dua-duanya.

Contoh 6

Perhatikan

●

(a)

efecgfe

d

c

b

a

(b)

Gambar 1.6 (a) merupakan pohon pusat karena tinggal satu titik, sedangkan

gambar 1.6 (b) pohon bipusat karena tinggal dua titik.

Teorema Cayle Pada Pohon Berlabel

Salah satu sifat dasar pohon (p, q) adalah terdapat hubungan yang sederhana

antara jumlah titik (order) dengan banyaknya sisi yaitu p=q+1. Dengan demikian

apabila diketahui suatu pohon dengan n titik maka banyaknya sisi adalah n−1.

Permasalahannya adalah ada berapa banyak pohon yang tak identik yang bisa

digambar apabila pohon berorder n.

Order (n) 1 2 3 4 5 6 7 8 9 10

berlabel 1 1 3 16 125 1296 16807 262144 27 28

Dengan melihat tabel di atas mudah diduga ada tepat

nn−2 pohon berlabel order n. Kenyataan ini dikenal sebagai teorema Cayle. Kerangka

pembuktian teorema Cayle ini merujuk kepada cara yang digunakan oleh H. Prufer

yang mengkonstruksikan korespondensi satu-satu antara pohon berlabel yang

berorder n dengan barisan (disebut barisan prufer).

Konstruksi Barisan Prufer

Kita konstruksikan korespondensi satu-satu antara himpunan pohon berlabel

berorder n dengan himpunan semua barisan yang berbentuk (a1 ,a2 ,⋯ an−2 ) dengan

masing-masing a i adalah satu dari bilangan bulat 1, 2, …, n (boleh berulang). Untuk

mendapatkan korespondensi satu-satu yang dikehendaki, kita ambil pohon berlabel

berorder n dengan label 1, 2, …, n kemudian terapkan tiga langkah berikut.

Langkah 1: perhatikan semua titik berderajad 1 dan pilih titik berlabel terkecil

d

cb

f

d

c

f

hg

e

dc

b

a

Langkah 2: perhatikan titik yang berdekatan dengan titik yang telah kita pilih di

langkah 1,

dan letakkan label ini pada posisi pertama dari barisan yang akan

dibentuk.

Langkah 3: hapuslah titik yang dipilih pada langkah 1 beserta sisi yang berinsidensi,

hingga

tinggal pohon yang lebih kecil. Ulangi langkah 1-3 untuk pohon yang

tertinggal. Lanjutkan hingga tinggal dua titik. Jika peristiwa ini telah

terjadi maka barisan prufer yang dikehendaki telah terbentuk.

Contoh 7

Perhatikan pohon berlabel T pada gambar 1.7 berikut. Tentukan barisan prufer dari

pohon T

Langkah 1: titik yang berderajad 1 adalah 2, 3, 6, 7; titik yang berlabel paling kecil

adalah 2

Langkah 2: titik yang berdekatan dengan 2 adalah titik 4, sehingga barisan dimulai

dengan

titik 4.

Langkah 3: hapus titik 2 dan sisi (2, 4), sehingga sisa pohon menjadi

Langkah 1: titik yang berderajad 1 adalah 3, 6, 7; titik yang berlabel paling kecil

adalah 3

Langkah 2: titik yang berdekatan dengan 3 adalah titik 4, sehingga barisan dimulai

dengan

titik 4.

Langkah 3: hapus titik 3 dan sisi (3, 4), sehingga sisa pohon menjadi

716

5

4

3

2

716

5

4

3

Langkah 1: titik yang berderajad 1 adalah 4, 6, 7; titik yang berlabel paling kecil

adalah 4

Langkah 2: titik yang berdekatan dengan 4 adalah titik 5, sehingga barisan dimulai

dengan

titik 5.

Langkah 3: hapus titik 4 dan sisi (4, 5), sehingga sisa pohon menjadi

Langkah 1: titik yang berderajad 1 adalah 6, 7; titik yang berlabel paling kecil

adalah 6

Langkah 2: titik yang berdekatan dengan 6 adalah titik 5, sehingga barisan dimulai

dengan

titik 5.

Langkah 3: hapus titik 6 dan sisi (6, 5), sehingga sisa pohon menjadi

Langkah 1: titik yang berderajad 1 adalah 5, 7; titik yang berlabel paling kecil

adalah 5

Langkah 2: titik yang berdekatan dengan 5 adalah titik 1, sehingga barisan dimulai

dengan

titik 1.

Langkah 3: hapus titik 5 dan sisi (5,1), sehingga sisa pohon menjadi

Selesai.

Sehingga barisan prufer dapat disusun yaitu (4, 4, 5, 5, 1).

Konstruksi pohon dari barisan prufer

716

5

4

716

5

71

5

71

Untuk memperoleh korespondensi balikan. Kita ambil barisan prufer dan

terapkan tiga langkah berikut:

Langkah 1: gambarlah n titik dan berilah label 1 sampai n, buat daftar bilangan 1

sampai n.

Langkah 2: tentukan bilangan terkecil yang berada pada daftar tetapi tidak berada

pada

barisan prufer, tentukan bilangan pertama dari barisan, kemudian buatlah

buatlah sisi yang menghubungkan kedua titik.

Langkah 3: hapuslah bilangan yang dipilih pada langkah 2 dari daftar dan bilangan

pertama

dari barisan pada langkah 2, hingga tersisa daftar bilangan dan barisan

yang lebih kecil.

Ulangi langkah 2 dan 3 pada daftar bilangan dan barisan yang tersisa, lanjutkan

hingga tinggal dua label yang tersisa dalam daftar. Terakhir buatlah sisi yang

menghubungkan kedua titik tersisa.

Contoh 8

Tentukan pohon yang mempunyai barisan prufer (4, 4, 5, 5, 1)

barisanprufer daftarbilangan (sebanyak n+2) sisi yang terbentuk4, 4, 5, 5, 1 1, 2, 3, 4, 5, 6, 7 (4, 2)4, 5, 5, 1 1, 3, 4, 5, 6, 7 (4, 3)5, 5, 1 1, 4, 5, 6, 7 (5, 4)5, 1 1, 5, 6, 7 (5, 6)1 1, 5, 7 (1, 5)

1, 7 (1,7)Jadi pohon yang terbentuk dari barisan prufer (4, 4, 5, 5, 1) adalah

Gambar 1.8

Definisi 3

7●

6●5●

4●

3●2●

1●

Misalkan G adalah sebuah graph. Sebuah pohon di G yang memuat semua

titik G disebut pohon rentang (spanning tree) dari G.

Jika Graph G merupakan pohon, maka pohon rentang satu-satunya adalah G

sendiri. Suatu graph dapat memiliki lebih dari satu pohon rentang. Ada beberapa cara

untuk memperoleh pohon rentang suatu graph. Salah satunya dengan menghapuskan

sebuah sisi dari setiap sikel. Metode ini digunakan untuk menentukan sistem

fundamental sirkuit dalam jaringan kerja listrik. Proses ini diilustrasikan dalam

contoh berikut.

Contoh 9

Graph pada Gambar 1.9 (a) bukan pohon karena graph itu memuat sikel a, b,

c. Prosedur untuk memperoleh pohon adalah dengan menghapus sebuah sisi di setiap

sikelnya. Dengan menghapus b dari sikel a, b, e, d akan diperoleh graph pada

Gambar 1.9 (b) yang tetap bukan pohon, karena masih ada sikel c, e, d. Sehingga

dihapus lagi sebuah sisi pada sikel ini, misal e.

Graph hasilnya terlihat pada Gambar 1.9 (c) dan sekarang merupakan pohon.

Pohon ini adalah pohon rentang untuk graph aslinya.

Gambar 1.9

Jika suatu graph terhubung memiliki n titik dan e sisi, dengan e ≥ n, maka

harus dilakukan proses penghapus e - n + 1 kali dengan tujuan mendapatkan pohon.

Karena dengan melakukan penghapusan ini, banyak sisi yang semula e berubah

menjadi n - 1, yang merupakan banyak sisi dalam pohon dengan n titik.

Akibat Teorema Cayle

Jumlah pohon pembentang (perentang) untuk graph Kn ada nn-2 buah.

Bukti:

Kn adalah graph yang terdiri dari n titik dimana setiap pasang titiknya

dihubungkan dengan tepat satu sisi. Buktinya dengan menggunakan korespondensi

1-1 seperti di atas. Korespondensi itu dilakukan antara semua pohon bentangan Kn

yang terdiri titik - titik { v1 , v2, v3, …, vn } dengan himpunan barisan (a1, a2, a3, …,

an-2 ) , dimana ai adalah bilangan bulat yang memenuhi 1 ≤ ai≤ n. Jumlah semua

kemungkinan yang diperoleh dari korespondensi itu adalah nn-2 , karena ada n cara

untuk memilih setiap ai.

Contoh 10

Misalkan kita mempunyai graph G seperti pada gambar 1.10 di bawah ini.

Terdapat 3 pohon rentang dari graph G, yaitu graph A, B, dan C. Tampak jelas

bahwa graph A, B, dan C masing-masing memuat semua simpul dari graph G serta

mengandung sisi-sisi dari G demikian sehingga tidak terbentuk sikel.

Gambar 1.10

Definisi 4

Pohon berakar adalah graph berarah (digraph) T yang mempunyai dua syarat:

1. Bila arah sisi-sisi pada T diabaikan, hasil graph tidak berarahnya merupakan

sebuah pohon, dan

2. Ada titik tunggal R sedemikian hingga derajat masuk R adalah 0 dan derajat

masuk

sembarang titik lainnya adalah 1. Titik R disebut akar dari pohon berakar itu.

Contoh 11

Graph pada Gambar 1.11 (a) adalah pohon berakar dengan akar A karena (1)

bila arah pada sisinya diabaikan, graph hasilnya merupakan pohon, dan (2) A

berderajat masuk 0, dan semua titik lainnya berderajat masuk 1. Cara biasa untuk

menggambarkan graph itu ditunjukkan pada Gambar 1.11 (b).

Gambar 1.11

Titik-titik D, H, E, dan B disebut titik terminal, yaitu titik dengan derajat

keluar 0. Sedangkan titik-titik A, C, F, dan G disebut titik internal, yaitu titik yang

memiliki derajat keluar yang tidak nol.

Istilah-istilah yang berkaitan dengan tree:

1. Parent (orang tua): yaitu vertex yang terletak lebih di atas dibanding vertex yang

bertetangga di bawahnya, vertex ini harus mempunyai child yang merupakan

vertex bertetangga di bawahnya.

2. Child (anak): vertex yang bertetangga dengan parent, terletak lebih di bawah

dibanding parent

3. Right child (anak kanan): child yang terletak di kanan

4. Left child (anak kiri): child yang terletak di sebelah kiri

5. Right Subtree (sub tree kanan): sub tree yang terletak di kanan

6. Left Subtree (sub tree kiri): sub tree yang terletak di kiri

7. Sibling (Saudara Kandung): vertex yang sejajar dengan vertex bersangkutan

dengan parent yang sama

8. Ancestor (nenek moyang): dari suatu vertex adalah vertex yang dilewati path

dari vertex tersebut ke root, tidak termasuk vertex itu sendiri, tetapi root

termasuk

9. Descendant (anak cucu): semua vertex yang berasal dari vertex tersebut dan

berakhir pada daun

10. Leaf (daun): vertex yang tidak mempunyai child

11. Internal vertex (vertex dalam): vertex yang bukan root dan bukan daun

(berdasarkan teorema ttg tree full m-ary “semua vertex harus mempunyai child

sebanyak m”, ternyata root termasuk internal vertex).

Contoh 12

Dalam gambar di bawah ini konsep pohon berakar digunakan untuk

menggambarkan hubungan antara pasal-pasal dan bab-bab dalam sebuah buku.

Gambar 1.12

LATIHAN.

1. Klasifikasikan semua pohon yang berorder 5, 6, 7. Apakah termasuk pohon

pusat atau dwipusat dan tentukan pusat tau dwipusatnya.

2. Tentukan barisan prufer dari pohon berikut

3. Tentukan pohon berlabel yang berkorespondensi dengan masing-masing

barisan prufer berikut

a. (2, 1, 1, 3, 5, 5)

b. (1, 3, 7, 3, 1)

7

8

53

64

21

4. Perhatikan pohon berakar berikut.

5. Sebuah pohon mempunyai dua titik berderajat 2, sebuah titik berderajat 3,

dan tiga titik berderajat 4. Banyaknya titik berderajat satu adalah?

6. Suatu kompetisi sepak bola melibatkan 16 kesebelasan. Apabila kompetisi

tersebut dilakukan dengan cara sistem gugur (kesebelasan yang kalah tidak

bertanding lagi), berapa banyak pertandingan untuk menentukan juara

pertama?

7. Banyaknya path (lintasan) sederhana yang panjangnya bukan nol pada pohon

yang memiliki n titik dengan n ≥ 2 adalah?

8. Graph lengkap dengan 4 titik mempunyai pohon rentang sebanyak?

9. Perhatikan graph pada gambar di bawah ini.

Yang bukan merupakan pohon adalah graph pada gambar?

10. Banyaknya sisi pada pohon dengan 21 titik adalah?

2. Pohon Pembentang Minimum ( Minimum Spanning Trees “MST”)

Ada beberapa aplikasi berkenaan dengan pohon pembentangdari suatu graph

tersambung. Andaikan kita ingin membangun saluran yang menghubungkan tempat-

tempat penyimpanan minyak, biaya pembangunan setiap saluran itu tidak sama

besarnya. Karena kemiringan tanah, jarak, dan faktor-faktor lainnya maka biaya

pembangunan salah satu saluran itu dapat lebih tinggi daripada saluran lainnya.

Masalah ini dapat digambarkan sebagai graph berbobot, dengan bobot setiap

sisinya menunjukkan biaya pembangunan saluran itu (lihat Gambar 2.1). Masalahnya

adalah bagaimana dapat membangun jaringan-jaringan pipa yang biayanya serendah

mungkin.

Gambar 2.1

Jalur kereta api yang menghubungkan sejumlah kota (titik) dapat

digambarkan dalam bentuk sebuah pohon pembentang, panjang rel (sisi) menyatakan

biaya pembangunan dan kita ingin meminimumkan biaya pembangunan totalnya.

Begitu pula untuk rute bis antar kota, dengan panjang sisi menyatakan biaya operasi

rata-rata setiap tahun atau untuk lalu lintas perjalanan kapal laut, panjang panjang

mungkin menyatakan keuntungan dan kita ingin memaksimumkan keuntungan total,

atau pada jaringan telepon antara beberapa kota, pohon pembentang minimum

mungkin menyatakan pemilihan jalur yang mengubungkan semua kota dengan biaya

minimum.

Definisi 1:

Bobot dari suatu pohon pembentang T dalam suatu graph tersambung

berbobot G adalah jumlah bobot sisi T.

Pohon pembentang minimum adalah pohon pembentang dari G dengan bobot

minimum.

Contoh 1

Graph berbobot pada Gambar 2.1, sisi-sisi b, c, e, g, dan h membentuk pohon

rentang dengan bobot 3 + 4 + 3 + 4 + 3 = 17. Sisi a, b, c, d, dan e membentuk pohon

rentang yang lain dengan bobot 2 + 3 + 4 + 2 + 3 = 14. Sisi-sisi a, d, f, i, dan j

membentuk pohon rentang yang lain lagi, dengan bobot 8. Karena pohon rentang ini

menggunakan kelima sisi dengan bobot terkecil, maka tidak ada pohon rentang lain

dengan bobot yang lebih kecil. Jadi, sisi a, d, f, i, dan j membentuk pohon rentang

minimal untuk graph berbobot itu.

Pada contoh 1 di atas, dapat ditemukan pohon rentang minimal dengan cara

mencoba-coba. Untuk graph berbobot dengan titik dan sisi yang banyak sekali,

pendekatan ini tidak praktis. Salah satu pendekatan sistematis yang dapat dilakukan

adalah dengan menemukan semua pohon rentang graph berbobot terhubung, dan

menghitung bobotnya, serta kemudian memilih pohon rentang dengan bobot terkecil.

Pemeriksaan semua kemungkinan itu sangat memakan waktu, meskipun dikerjakan

dengan komputer. Biasanya pohon rentang minimal ini dicoba disusun dengan

membangun pohon rentang menggunakan sisi berbobot terkecil. Pendekatan ini

diilustrasikan pada Contoh 2.

Contoh 2

Untuk graph berbobot pada Gambar 2.2 (a), kita mulai pada titik A dan

memilih sisi yang berbobot terkecil pada A, yaitu b. Untuk melanjutkan penyusunan

pohon, dilihat sisi a, c, e, dan f yang menyinggung sisi b. Dipilih satu sisi dengan

bobot terkecil, yaitu f. Sisi berikutnya yang perlu dilihat adalah a, c, e, dan g yang

menyinggung sisi yang telah dipilih. Ada dua sisi dengan bobot terkecil, yaitu e dan

g, kemudian dipilih satu secara sembarang, katakan e. Sisi berikut yang diperhatikan

adalah a, c, dan d (sisi g tidak diperhatikan lagi, karena apabila diambil sisi g akan

membentuk sikel dengan e dan f). Sisi dengan bobot terkecil adalah a, dan dengan

demikian a ditambahkan ke pohon rentang. Keempat sisi a, b, e, f ini membentuk

pohon rentang, yang juga merupakan pohon rentang minimal (lihat Gambar 2.2 b).

Gambar 2.2

Metode yang digunakan pada contoh 2 akan selalu menghasilkan pohon

rentang minimal. Metode ini ditemukan oleh Prim. Algoritma Prim menyusun pohon

dengan memilih sembarang titik dan kemudian suatu sisi dengan bobot terkecil pada

titik itu. Berikutnya, pohon itu dikembangkan dengan memilih suatu sisi berbobot

terkecil. Pohon itu masih dikembangkan lagi dengan memilih suatu sisi berbobot

terkecil yang membentuk pohon dengan dua sisi terpilih sebelumnya. Proses ini

dilanjutkan sampai diperoleh sebuah pohon rentang, yang juga merupakan pohon

rentang minimal. Prosedur ini dapat diformalisasikan sebagai berikut.

1. Algoritma Prim untuk Pohon rentang Minimal

Dengan algoritma ini akan ditemukan pohon rentang minimal (jika ada)

untuk sebuah graph berbobot G dengan n titik. Dalam algoritma ini S adalah

himpunan titik dan T adalah himpunan sisi.

Langkah 1:(mulai). Pilih titik U, dan misalkan S = {U} serta T = { }.

Langkah 2:(pemeriksaan untuk menyelesaikan). Jika S memuat semua titik G,

kemudian

berhenti; sisi di T dan titik di S membentuk pohon rentang minimal untuk

G.

Langkah 3:(pilih sisi berikutnya). Jika S tidak memuat semua titik G, tentukan sisi-

sisi yang

memiliki satu titik di S dan titik lainnya tidak di S. Jika tidak ada sisi seperti

itu, G tidak terhubung dan tidak memiliki pohon rentang minimal. Jika tidak

demikian, pilih satu sisi seperti itu yang berbobot terkecil (rangkaian dapat

diputuskan secara sembarang), dan tempatkan di T serta titiknya di S (salah

satunya sudah di S).

Kembalilah ke langkah 2.

Pada langkah 3 algoritma Prim pemilihan suatu sisi dengan satu titik di S dan

titik lain tidak di S menjamin tidak adanya sikel yang terbentuk dengan pengumpulan

sisi-sisi di T, jadi pada akhir setiap iterasi langkah 3, sisi di T dan titik di S

membentuk pohon.

Contoh 3

Algoritma Prim akan diaplikasikan pada graph berbobot G pada Gambar 2.3.

Mulai di titik U, sehingga S = {U} dan T = { }.

Gambar 2.3

Karena S tidak memuat semua titik G, diperhatikan sisi pada U, yaitu a, b, c,

dan f, dan ambil satu yang berbobot terkecil. Sisi itu adalah a, sehingga a

ditempatkan di T dan titiknya ditambahkan di S. Jadi S = {U, C} dan T = {a}.

Terlihat S tidak memuat semua titik G, sehingga di lihat sisi-sisi yang memiliki satu

titik di S dan satu titik tidak di S. Sisi-sisi ini adalah b, c, d, e, dan f.

Di antara sisi-sisi ini, e memiliki bobot terkecil, sehingga sisi itu ditambahkan

di himpunan T dan titik E ditambahkan pada himpunan S. Sekarang S = {U, C, E}

dan T = {a, e}. Karena S belum memuat semua titik di G, diperhatikan lagi sisi-sisi

dengan satu titik di S dan titik lain tidak di S. Sisi-sisi ini adalah b, c, d, dan j.

Perhatikan bahwa sisi f tidak diperhatikan, karena dua titiknya ada di S. Dari sisi b, c,

d, dan j, ada dua yang memiliki bobot terkecil, yaitu b dan d.

Diambil salah satu secara sembarang, misalkan b dan tambahkan pada T serta

B pada S. Jadi, S = {U, C, E, B} dan T = {a, e, b}. Pada saat ini sisi-sisi dengan satu

titik di S dan yang lain tidak di S adalah c, g, i, dan j. Dari semua titik ini, sisi c dan g

memiliki bobot terkecil. Sehingga dipilih g secara sembarang, membuat S = {U, C,

E, B, A} dan T = {a, e, b, g}. Sekarang perhatikan sisi-sisi c, h, i, dan j. Sisi yang

memiliki bobot terkecil adalah h, sehingga dipilih sisi h ini. Maka S = {U, C, E, B,

A, D} dan T = {a, e, b, g, h}. karena S memuat semua titik dari G, maka pohon

rentang minimum dari graph tersebut terlihat pada Gambar 2.4 dengan bobot 28.

Gambar 2.4

Pada dua tempat berbeda pada contoh di atas, dapat dipilih lebih dari satu

titik dengan bobot terkecil. Algoritma itu menunjukkan bahwa setiap titik dengan

bobot terkecil dapat saja dipilih. Oleh karena itu dapat disusun pohon rentang

minimal yang berbeda, tergantung pada pilihan yang dilakukan. Misal: jika pada

contoh 3 dipilih sisi d dan bukan b, diikuti dengan c dan h, maka pohon rentang

minimalnya adalah seperti pada Gambar 2.5. Jadi, pohon rentang minimalnya

tidak tunggal.

Gambar 2.5

Perhatikan kembali Gambar 2.3. Andaikan sekarang bobot sisi-sisi itu

menunjukkan besarnya keuntungan yang dihasilkan bila minyak dipompakan melalui

saluran itu. Masalahnya sekarang adalah mendapatkan pohon rentang saluran yang

menghasilkan keuntungan terbesar. Jadi, sekarang diinginkan untuk mendapatkan

pohon rentang yang total bobot sisinya bukan paling kecil, melainkan paling besar.

Pohon rentang maksimal di dalam graph berbobot adalah pohon rentang yang

bobotnya sebesar mungkin. Dengan kata lain, bobot pohon rentang itu paling besar,

tidak ada pohon rentang lain yang bobotnya lebih besar. Untungnya, cara

mendapatkan pohon rentang maksimal amat mirip dengan cara menemukan pohon

rentang minimal. Yang diperlukan hanyalah menggantikan kata “terkecil” dengan

kata “terbesar” dalam algoritma Prim.

Contoh 4

Untuk graph berbobot pada Gambar 2.3, akan disusun pohon rentang

maksimal. Mulai dengan mengambil titik U. Maka S = {U} dan T = { }. Sekarang

dilihat sisi-sisi pada U dan ambil satu bobotnya yang terbesar yaitu sehingga S = {U,

D} dan T {c}. Karena S tidak memuat semua titik graph itu, diperhatikan sisi-sisi

lain dengan satu titik di S dan yang lain tidak di S. Sisi-sisi ini adalah a, b, f, h, i, dan

j. Di antaranya ada dua dengan bobot terbesar, i dan j. Dipilih satu secara sembarang

katakan i. Sehingga sekarang T = {c, i} dan S = {U, B, D}.

Proses ini diulang lagi dengan memilih sisi j yang berbobot terbesar dan

memilih satu titik di S dan yang lain tidak di S. Sekarang T = {c, i, j} dan S = {U, B,

D, E}. Dilihat lagi sisi-sisi dengan satu titik di S dan yang lain tidak di S. Di

antaranya, g adalah sisi yang berbobot terbesar, sehingga T = {c, g, i, j} dan S = {U,

A, B, D, E}. Pilih sisi d yang berbobot terbesar dan memilih satu titik di S dan yang

lain tidak di S, sehingga T = {c, d, g, i, j} dan S = {U, A, B, C, D, E} yang

merupakan himpunan semua titik. Oleh karena itu T adalah pohon rentang maksimal

dengan bobot 48 seperti terlihat pada Gambar 2.6

Gambar 2.6

Algoritma prim untuk Gambar 2.3 bisa menggunakan cara lain yaitu pertama

buatlah tabel yang menyatakan bobot sisi yang menghubungkan masing-masing titik.

Jika titik tidak berhubungan secara langsung, berilah nilai tak hingga.

titik A B C D E U

A - 9 ∞ 3 ∞ ∞

B 9 - 8 11 ∞ 8

C ∞ 8 - ∞ 3 5

D 3 11 ∞ - 11 9

E ∞ ∞ 3 11 - 6

U ∞ 8 5 9 6 -

Pertama:

Pilih sembarang titik dari G ke dalam T (Misalkan kita pilih titik D).

Hapuslah baris D dari daftar. Perhatikan elemen terkecil dari kolom D adalah 3 yaitu

bobot sisi yang menghubungkan A dengan D.

titik A B C D E UA - 9 ∞ 3 ∞ ∞

B 9 - 8 11 ∞ 8C ∞ 8 - ∞ 3 5E ∞ ∞ 3 11 - 6U ∞ 8 5 9 6 -

Kedua:

Letakkan sisi (A, D) dan titik A ke dalam T. Hapuslah baris A dari daftar.

Perhatikan elemen terkecil dari kolom A dan D adalah 9 yaitu bobot sisi yang

menghubungkan A dengan B.

titik A B C D E UB 9 - 8 11 ∞ 8C ∞ 8 - ∞ 3 5E ∞ ∞ 3 11 - 6U ∞ 8 5 9 6 -

Ketiga:

Letakkan sisi (A, B) dan titik B ke dalam T. Hapuslah baris B dari daftar.

Perhatikan elemen terkecil dari kolom A, D dan B adalah 8 yaitu bobot sisi yang

menghubungkan B dengan C.

titik A B C D E UC ∞ 8 - ∞ 3 5E ∞ ∞ 3 11 - 6U ∞ 8 5 9 6 -

Keempat:

Letakkan sisi (B, C) dan titik C ke dalam T. Hapuslah baris C dari daftar.

Perhatikan elemen terkecil dari kolom A, D, B dan C adalah 3 yaitu bobot sisi yang

menghubungkan C dengan E.

titik A B C D E U

E ∞ ∞ 3 11 - 6

U ∞ 8 5 9 6 -

Kelima:

Letakkan sisi (C, E) dan titik E ke dalam T. Hapuslah baris E dari daftar.

Perhatikan elemen terkecil dari kolom A, D, B, C dan E adalah 5 yaitu bobot sisi

yang menghubungkan C dengan U

titik A B C D E U

U ∞ 8 5 9 6 -

Keenam:

Dengan memasukkan sisi (E, U), maka pohon pembentang minimum telah

kita konstruksikan yaitu pohon dengan sisi (A, D), (A, B), (B, C), (C, E) dan (C, U)

dengan bobot 3 + 9 + 8 + 3 + 5 = 28

Algoritma lain yang dapat digunakan untuk mendapatkan pohon rentang

minimal ditemukan oleh Kruskal.

2. Algoritma Kruskal untuk pohon rentang minimal

Algoritma ini akan mendapatkan pohon rentang minimal, jika ada, untuk

graph berbobot G yang memiliki n titik, dengan n ≥ 2. Dalam algoritma ini, S adalah

himpunan titik dan T adalah himpunan sisi.

Langkah 1:(mulai). Jika tidak ada sisi, G tidak terhubung, dan karena itu tidak

memiliki

pohon rentang minimal. Jika tidak demikian, ambil sebuah sisi dengan

bobot terkecil (rangkaian dapat diputuskan secara sembarang).

Tempatkan sisi itu di T dan titiknya di S.

Langkah 2: (pemeriksaan untuk penyelesaian). Jika T memuat n - 1 sisi, maka

berhentilah;

sisi-sisi di T dan titik-titik di S membentuk pohon rentang minimal. Jika

tidak demikian lanjutkan ke langkah 3.

Langkah 3: (ambil sisi berikutnya). Tentukan sisi-sisi berbobot terkecil yang tidak

membentuk sikel dengan sembarang sisi yang ada di T. Jika tidak ada sisi

seperti itu, G tidak terhubung dan tidak memiliki pohon rentang minimal.

Jika tidak demikian, pilih satu sisi sejenis itu (rangkaian dapat diputus

secara sembarang), dan tempatkan sisi itu di T dan titiknya di S.

Kembalilah ke langkah 2.

Contoh 5

Gunakan algoritma Kruskal untuk menentukan pohon rentang dengan bobot

minimum dari graph berikut.

Gambar 2.7

Jawab

Ambil sebuah sisi dengan bobot terkecil, sisi itu adalah f, sehingga T = {f }

dan S = {A, F}. Tentukan sisi berbobot terkecil yang tidak membentuk sikel dengan

sembarang sisi yang ada di T, sisi itu adalah g, sehingga T = {f, g} dan S = {A, B,

F}. Pilih sisi berbobot terkecil yang tidak membentuk sikel.

Dengan sembarang sisi yang ada di T, sisi itu adalah i, sehingga T = {f, g, i}

dan S = {A, B, F, G}. Sisi dengan bobot terkecil yang tidak membentuk sikel dengan

sembarang sisi yang ada di T adalah j dan k, misalkan secara sembarang diambil k.

Jadi T = {f, g, i, k} dan S = {A, B, D, F, G}. Ambil sisi bobot terkecil yang tidak

membentuk sikel dengan sembarang sisi di T, yaitu c. Jadi T = {c, f, g, i, k} dan S =

{A, B, C, D, F, G}. Pilih sisi h, sehingga T = {c, f, g, h, i, k} dan S = {A, B, D, E, F,

G}. Karena S memuat semua titik dari graph tersebut, maka pohon rentang minimum

dari graph tersebut terlihat pada Gambar 2.8 dengan bobot 17.

Gambar 2.8

Contoh 6

Gunakan algoritma Kruskal untuk menentukan pohon rentang dengan bobot

minimum dari graph G berikut.

Gambar 2.9

Pertama-tama kita tentukan sisi dengan bobot terkecil. Sisi dengan bobot 1

terpilih sebagai sisi pertama yang kita pilih. Untuk itu kita hitamkan sisinya.

Langkah ini memberikan hasil sebagai berikut.

Gambar 2.10

Bobot terkecil berikutnya setelah 1 dan 2, namun terdapat 2 sisi yang

mempunyai bobot 2. Misalkan kita pilih sisi yang terlihat vertikal. Pilihan ini

memberikan gambar berikut.

Gambar 2.11

Sisi dengan bobot 2 lainnya sekarang kita masukkan sebagai bagian dari

pohon rentang yang sedang dikonstruksi. Ini menghasilkan gambar seperti di bawah

ini.

Gambar 2.12

Sisi berikutnya yang kita hitamkan adalah sisi dengan bobot 3

Gambar 2.13

Terdapat 2 sisi dengan bobot 4. Kita pilih sebuah sisi dengan bobot 4, sehingga kita

peroleh gambar berikut.

Gambar 2.14

Sekarang hanya tinggal sebuah titik lagi yang belum terambil. Dari 4 sisi

yang insiden dengan titik ini, yang mempunyai bobot terkecil adalah sisi dengan

bobot 5. Kita pilih sisi ini sehingga pohon optimalnya terlihat pada gambar brkut

dengan sisi yang dicetak lebih hitam.

Gambar 2.15

Pohon optimal ini total bobotnya adalah 1 + 3 + 2 + 4 + 2 + 5 = 17.

3. POHON BINER

Pohon biner adalah pohon berakar yang setiap titiknya memiliki paling

banyak dua anak dan setiap anak ditunjuk sebagai anak kiri atau anak kanan. Jadi,

pada pohon biner setiap titik mungkin memiliki 0, 1, atau 2 anak. Anak kiri

digambarkan di sebelah kiri dan di bawah orang tuanya, serta anak kanan di sebelah

kanan di bawah orang tuanya.

Contoh 1

Untuk pohon biner pada Gambar 3.1 (a), A adalah akarnya. Titik A memiliki dua

anak, anak kiri B dan anak kanan C. Titik B memiliki satu anak, anak kiri D.

Demikian pula titik C memiliki anak kanan E, tetapi tidak memiliki anak kiri. Pada

pohon biner Gambar 3.1 (b), titik A memiliki anak kiri B. Berbeda dengan pohon

biner pada Gambar 3.1 (c), di sini B merupakan anak kanan.

Gambar 3.1

Pohon biner digunakan dalam ilmu komputer untuk mengolah data.

Contoh 2

Pernyataan a * b (dengan * menunjukkan perkalian) disajikan dengan pohon biner

pada Gambar 3.2

Gambar 3.2

Contoh 3

Pernyataan a + b * c berarti a + (b * c). Operasi terakhir yang dijalankan

adalah penjumlahan. Mula-mula pernyataan ini disajikan dengan pohon biner pada

Gambar 3.3 (a). Proses ini diulangi dan menghasilkan pohon biner pada Gambar 3.3

(b).

Gambar 3.3

Contoh 4

Pohon pernyataan untuk a + d * (b - c) diciptakan dengan barisan pohon biner

pada Gambar 3.4.

Gambar 3.4

Contoh 5

Pernyataan (a + b * c) - (f - d/e) disajikan dengan pohon pernyataan pada Gambar 3.5

Gambar 3.5

LATIHAN

1. Lima komputer harus dipasang di sebuah kantor dan satu sama lain saling

terhubung (dapat secara langsung atau dengan melalui komputer lain, salah

satu). Panjang kabel yang diperlukan untuk menghubungkan unit-unit komputer

yang berdekatan diberikan dalam meter. Berapa panjang minimum kabel yang

diperlukan?

2. Kantor pusat suatu perusahaan akan membangun jaringan pos elektronik

(menggunakan satelit) dengan anak-anak perusahaannya yang terbesar di

tempat-tempat seperti pada gambar berikut. Biaya membangun hubungan itu

tergantung pada jaraknya dan dinyatakan dalam jutaan rupiah. Berapa biaya

maksimum untuk membangun jaringan itu?

3. Gambar berikut memberikan informasi tentang panjang kabel yang diperlukan

untuk menghubungkan lima lampu taman (panjang dalam meter). Berapa

panjang minimum kabel yang diperlukan?

4. Konstruksi pohon pernyataan dari operasi a * b + c adalah

5. Diagram pohon berikut menunjukkan pohon pernyataan dari operasi