1

1. Pengantar Teori Graph Oleh : Ade Nurhopipah

Pokok Bahasan :

1. Graph, Digraph dan Network

2. Klasifikasi Masalah

3. Pencarian Solusi

Sumber :

Aldous, Joan M. ,Wilson, Robin J. 2004. Graph and Applications. Springer: UK.

Pencarian Rute

Untuk memperkenalkan konsep graph, kita akan meninjau beberapa permasalahan dan

representasinya dalam sebuah diagram. Pertama kita akan meninjau permasalahan pencarian rute.

Gambar 1.1 menunjukan peta stasiun di London. Peta tersebut tidak menunjukan semua fitur dari

area tersebut, seperti lokasi geografis stasiun, atau informasi jarak antar dua stasiun. Peta tersebut

hanya menunjukan fitur yang sesuai dengan kebutuhan orang yang memakainya yaitu menunjukan

keterhubungan antar stasiun, sehingga penumpang dapat melihat rute dari satu stasiun ke stasiun

lainnya.

Gambar 1.1 Contoh peta stasiun kereta api

Pada peta tersebut, jika kita mencari suatu rute terbaik antar dua stasiun, maka interpretasi

atas “rute terbaik” mungkin tidak selalu sama. Bisa saja rute terbaik merupakan rute dengan minimal

stasiun yang dilewati, atau karena pergantian kereta memakan waktu, maka rute terbaik merupakan

rute dengan pergantian kereta yang minimal.

Pada kasus yang lain, misalnya ketika kita menggunakan peta jalan, hal yang penting bukan

hanya keterhubungan antara dua kota, namun juga jarak atau waktu tempuh antar kota tersebut.

Misalnya pada Gambar 1.2 menunjukan beberapa rute utama antara beberapa kota di USA, yang

dilengkapi dengan waktu tempuh antar kota (dalam satuan jam).

2

Gambar 1.2 Contoh peta jalan antar kota dan waktu tempuhnya

Latihan 1.1 Berdasarkan peta pada Gambar 1.2 carilah waktu terpendek ketika kita ingin pergi dari Los Angeles ke Oklahoma City.

Bidang Kimia

Sebuah molekul adalah kumpulan sejumlah atom yang terhubung dengan ikatan kimia.

Suatu alkana (paraffin) adalah suatu molekul dengan rumus CnH2n+2, di mana setiap atom karbon (C)

diikat oleh tepat empat atom, dan masing-masing atom hidrogen (H) diikat oleh tepat sebuah atom.

Suatu molekul methana (CH4) mengandung satu atam karbon yang berikatan dengan empat atom

hidrogen. Begitu juga molekul ethana (C2H6) memiliki dua atom karbon yang berikatan dengan enam

atom hidrogen. Gambar 1.3 menunjukan ikatan atom pada molekul methana dan ethana.

Gambar 1.3 Molekul methana dan ethana

Molekul ini dapat direpresentasikan sebagai suatu diagram, di mana atom diindikasikan

dengan simbol kimianya, dan ikatan kimia ditunjukan dengan garis yang menghubungkan simbol

tersebut. Diagram ini tidak menunjukan secara tepat bagaimana posisi atom tersebut. Misalnya,

atom hidrogen dari methana tidak semuanya terletak dalam satu bidang, tetapi terletak pada sudut-

sudut seperti dalam regular tetrahedron, dengan atom karbon berada ditengahnya seperti

ditunjukan pada Gambar 1.4.

3

Gambar 1.4 Letak atom dalam molekul methana

Walaupun demikian, diagram yang kita buat bermanfaat untuk mengilustrasikan hubungan

antar atom, dan kita dapat memperoleh banyak informasi tentang perilaku kimia dari sebuah

molekul dengan mempelajari diagram tersebut. Alkana yang memiliki rumus CnH2n+2 graph-nya

memiliki cabang seperti struktur tree. Jika ada empat atau lebih atom karbon, maka akan terdapat

molekul berbeda yang terbangun dengan rumus kimia yang sama (dikenal sebagai isomer). Sebagai

contoh untuk rumus kimia C5H12 kita dapat membuat dua diagram yang berbeda seperti ditunjukan

pada Gambar 1.5.

Gambar 1.5 Dua molekul yang terbentuk dengan rumus kimia C5H12

Latihan 1.2 Tunjukan bahwa hanya ada satu alkana dengan rumus C3H8, namun ada dua alkana dengan rumus C4H10.

Masalah Utilitas

Pada masalah ini terdapat beberapa tetangga yang ingin menghubungkan rumah mereka

dengan tiga utilitas yaitu gas, air dan listrik sedemikian rupa sehingga sembilan koneksi antar tiga

rumah dan tiga utilitas tersebut tidak saling berpotongan. Pada Gambar 1.6, delapan koneksi sudah

terpasang, namun rumah B tidak terhubung dengan air. Pertanyaannya adalah dapatkah kita

menambahkan suatu jalur yang menghubungkan air dengan rumah B tanpa memotong jalur lain

yang telah terpasang.

4

Gambar 1.6 Ilustrasi masalah utilitas

Masalah utilitas juga berhubungan dengan masalah praktis yang timbul dalam kajian tentang

sirkuit cetak. Dalam masalah ini, komponen elektronik dibangun dengan cara mencetak jalur-jalur

pada sebuah papan. Jalur-jalur tersebut tidak berpotongan karena dapat menimbulkan kontak

elektrik yang tidak diinginkan pada titik perpotongannya.

Latihan 1.3 Sirkuit mana pada diagram berikut yang dapat anda gambar kembali tanpa ada titik yang saling berpotongan.

Pada beberapa masalah yang telah kita pelajari, kita perhatikan bahwa semua permasalahan

memiliki pola yang sama, yaitu suatu kumpulan objek yang memiliki relasi dengan berbagai cara.

Stasiun saling terhubung dengan rel, atom-atom saling terhubung dengan ikatan, dan rumah saling

terhubung dengan utilitas. Pada setiap kasus, kita dapat menggambar sebuah diagram di mana kita

merepresentasikan objek dengan titik, dan interkoneksi antara pasangan objek dengan garis (tidak

harus garis lurus). Diagram seperti inilah yang disebut dengan graph. Perhatikan contoh sebuah

graph pada Gambar 1.7. Pada suatu graph, titik yang mewakili objek disebut vertex dan garis yang

mewakili interkoneksinya tersebut disebut edge (sisi).

Gambar 1.7 Contoh sebuah graph

5

Secara umum, kita menyatakan ide tentang graph, sebagai berikut.

Graph adalah sebuah diagram yang terdiri dari titik-titik (disebut vertex) yang dihubungkan dengan garis-garis (disebut edge). Setiap edge menghubungkan tepat dua vertex.

Sebagai catatan, istilah ini tidak sepenuhnya standar, ada yang menyebut vertex dengan

node atau point, dan ada pula yang menyebut edge dengan line.

Pada problem utilitas, masalah tersebut dapat direpresentasikan oleh sebuah graph dengan

enam vertex yang mewakili tiga rumah dan tiga utilitas, dan sembilan edge yang mewakili sembilan

kemungkinan koneksi. Masalah utilitas adalah masalah bagaimana membentuk suatu diagram,

sehingga tidak ada edge yang berpotongan. Catat bahwa ketiga rumah tersebut tidak saling

terhubung, begitu juga ketiga utilitas. Graph seperti ini, di mana vertex terbagi ke dalam dua

himpunan (himpunan rumah dan himpunan utilitas), dan edge pada graph tersebut hanya

menghubungkan dua vertex pada himpunan yang berbeda, disebut graph bipartit. Gambar 1.8

menunjukan dua kemungkinan cara menggambar graph tersebut.

Gambar 1.8 Graph untuk masalah utilitas

Contoh lain untuk menunjukan konsep graph dalam menggambarkan hubungan antar objek

adalah representasi graph untuk permainan sepak bola. Gambar 1.9 menggambarkan graph

permainan sepak bola, di mana Arsenal bermain dengan Chelsea dan Everton, tetapi tidak melawan

Liverpool. Chelsea melawan Everton dua kali, dan Liverpool bermain dengan Everton satu kali.

Gambar 1.9 Graph untuk permainan sepak bola

6

Graph pada Gambar 1.9 memiliki empat vertex yang mewakili klub sepak bola dan lima edge

yang mewakili pertandingan antara kedua klub. Gambar 1.9 juga menunjukan bahwa kita dapat

menggambar sebuah graph dengan berbagai cara, selama ia mewakili keterhubungan yang sama

sehingga mewakili permasalahan yang disajikan.

Latihan 1.4 1. Gambar sebuah graph yang mewakili pertemanan antara empat orang berikut.

Andi berteman dengan Oki dan Ika, tapi tidak dengan Jaka Jaka berteman dengan Ika, tapi tidak dengan Oki. Oki berteman dengan Ika.

2. Sebuah labirin dapat direpresentasikan dengan sebuah graph. Pada labirin tersebut terdapat pilihan yang mungkin pada masing-masing persimpangan. Sebagai contoh, pada persimpangan B ada dua pilihan, yaitu pergi ke C atau ke D. Berikut adalah representasi labirin ke dalam bentuk graph.

Gunakanlah graph tersebut untuk mendaftar semua rute dari titik A ke titik L tanpa melibatkan titik yang sudah dilalui.

Masalah Jembatan Kὂnigsberg

Pada awal abad ke delapan belas, kota Kὂnigsberg di Prussia Timur memuat sebuah pulau

yang disebut Kneiphof yang dikelilingi oleh sungai Pregel. Empat bagian kota (A,B,C,D) terhubung

dengan tujuh buah jembatan (a,b,c,d,e,f,g) seperti ditunjukan pada Gambar 1.10.

Gambar 1.10 Kota Kὂnigsberg di Prussia Timur

7

Diceritakan bahwa warga Kὂnigsberg menghibur diri dengan mencoba mencari rute dengan

menyebrangi setiap jembatan tepat satu kali, dan kembali ke posisi awal. Mereka mencoba

sebisanya, namun tidak menemukan rute tersebut dan mulai yakin bahwa hal tersebut mustahil

dilakukan. Pada masalah ini, terdapat empat area yang terhubung dengan tujuh jembatan. Kita

dapat merepresentasikan hubungan ini dengan menggambar graph dengan empat vertex yang

mewakili area, dan tujuh edge yang mewakili tujuh jembatan seperti ditunjukan pada Gambar 1.11.

Gambar 1.11 Representasi graph dari masalah jembatan Kὂnigsberg

Masalah menyebrangi setiap jembatan tepat satu kali kini dapat ditransformasikan ke dalam

masalah graph. Masalah tersebut adalah dapatkah kita menggambar graph pada Gambar 1.11 dari

suatu titik awal dan kembali ke titik tersebut tanpa mengangkat pensil dari kertas dan tanpa

menggambar atau melalui edge manapun dua kali.

Masalah Kerangka Segiempat Yang Diperkuat

Banyak bangunan yang disokong dengan kerangka segiempat yang terbuat dari baja. Sangat

penting bagi kita untuk memastikan bahwa kerangka tersebut tetap kaku (rigid) dibawah beban

berat. Sebagai contoh Gambar 1.12 menunjukan bagaimana kerangka segiempat dapat terdistorsi.

Gambar 1.12 Kerangka segiempat yang dapat terdistorsi (non-rigid)

Suatu cara agar kerangka tetap rigid adalah dengan menambahkan penahan (brace) untuk

mencegah distorsi. Pada kasus kerangka dengan empat buah segiempat seperti ditunjukan pada

Gambar 1.13, penambahan dua buah penahan pada kerangka (diindikasikan dengan bayangan pada

segiempat), tidak dapat membuat kerangka ini menjadi rigid. Jumlah minimal penahan yang harus

ditambahkan agar kerangka tetap rigid adalah tiga buah.

8

Gambar 1.13 Jumlah penahan pada kerangka segiempat

Kita dapat merepresentasikan kerangka yang diberi penahan ini dengan membuat sebuah

graph. Perhatikan kerangka pada Gambar 1.14. Setiap penahan kerangka, muncul pada sebuah baris

dan sebuah kolom, sehingga kita dapat mengetahui posisi penahan tersebut dengan menggambar

graph. Vertex pada graph tersebut berkoresponden dengan baris dan kolom pada kerangka dan

edge berkoresponden dengan penahannya. Dua vertex dihubungkan jika pada pada posisi tersebut

terdapat penahan. Catat bahwa dalam kasus ini, kita memperoleh sebuah graph bipartit dengan

dua buah himpunan yaitu himpunan baris dan himpunan kolom.

Gambar 1.14 Representasi graph untuk kerangka yang diperkuat

Graph Berbobot

Sebelumnya pada Gambar 1.2 kita diberikan peta jalan antar kota di USA. Pada peta tersebut

edge mewakili jalan yang menghubungkan kota. Setiap edge memiliki suatu nilai yang

merepresentasikan waktu tempuh (dalam satuan jam) antar pasangan kota. Nilai ini disebut bobot,

dan sebuah graph yang memiliki bobot yang berasosiasi dengan setiap edge disebut graph berbobot.

Bobot pada edge dapat mengacu pada banyak hal. Misalnya pada peta jalan, bobot dapat

mewakili jarak, waktu atau biaya yang diperlukan dalam perjalanan. Contoh-contoh lain untuk graph

berbobot muncul pada permasalahan berikut.

9

Masalah Perjalanan Pedagang

Seorang pedagang ingin mengunjungi sejumlah kota dan kembali ke tempat asalnya. Rute

yang diinginkan adalah rutedengan panjang total jarak terkecil. Gambar 1.15 menunjukan suatu

graph berbobot yang memiliki empat vertex, dan enam edge. Pada kasus ini, bobot mewakili jarak

antar kota (dalam mil). Bagaimanakah kita dapat memilih rute dengan bobot minimal untuk

mengunjungi semua vertex dan kembali ke titik awal? Sebagai contoh, misalnya kita memiliki titik

awal London. Dengan cara mencoba-coba, kita dapat menemukan solusi dari rute yang diinginkan

yaitu: London-Conventry-Preston-Leeds-London. Total jarak yang ditempuh adalah 100+125+68+194

= 487 mil. Jika kita perhatikan, rute yang lain memiliki jarak total lebih besar.

Gambar 1.15 Graph berbobot jarak antar kota

Sayangnya jika jumlah kota semakin banyak, kita akan kesulitan menemukan solusi dengan

cara mencoba-coba. Solusi yang menjanjikan untuk memecahkan masalah ini adalah dengan metode

exhaustion, yaitu dengan mencari semua kemungkinan rute dan memilih mana yang paling pendek.

Namun, metode ini bukanlah metode yang efisien untuk menyelesaikan masalah. Misalnya jika ada

sepuluh kota, maka kemungkinan rute yang ada adalah ½(9!)= ½(9x8x7x6x5x4x3x2x1) = 181440. Jika

ada dua puluh kota, maka kemungkinan rute yang ada adalah ½(19!)=6,08x1016. Peningkatan jumlah

rute yang cepat karena penambahan kota ini dikenal sebagai masalah combinatorial explotion.

Untuk masalah dengan skala lebih besar, kita memerlukan metode langkah demi langkah

yang sistematik dan efisien. Beberapa prosedur yang akan kita pelajari pada bab selanjutnya, dinilai

dapat menjadi metode yang efisien sekaligus memberi pendekatan nilai dari solusi yang diinginkan.

Latihan 1.5 Seorang penjaga kebun binatang akan mengunjungi lokasi hewan di titik A,B,C,D,E. Jarak antar tempat ditunjukan dalam diagram. Dengan cara mencoba-coba, temukan rute dengan jarak terpendek dari tempat A dan kembali ke A.

10

Digraph

Kita banyak menemui adanya sistem jalan satu arah di sebuah kota besar. Karena jalan

tersebut satu arah, kita tidak bisa merepresentasikan sistem ini dengan sebuah graph yang tidak

memiliki arah. Kita dapat merepresentasikan masalah ini dengan membuat diagram yang serupa

dengan graph, dan mengganti semua edge dengan anak panah, yang menandakan arah pada jalan

tersebut. Diagram seperti ini disebut digraph (directed graph). Contoh representasi digraph untuk

jalan satu arah ditunjukan pada Gambar 1.16.

Gambar 1.16 Representasi digraph untuk jalan satu arah

Konsep tentang digraph dapat dinyatakan sebagai berikut.

Digraph adalah sebuah diagram yang memuat titik-titik (disebut vertex) yang dihubungkan dengan garis-garis (disebut arc), setiap arc menghubungkan tepat dua vertex.

Latihan 1.6 Representasikan sistem jalan satu arah berikut dalam sebuah digraph.

11

Network (Jaringan)

Kita dapat menetapkan bobot terhadap edge pada graph untuk membentuk sebuah graph

berbobot, begitu juga kita dapat menetapkan bobot terhadap arc pada digraph untuk membentuk

digraph berbobot. Konsep ini menuntun kita kepada ide tentang network.

Kita memakai kata network, untuk graph dan digraph yang membawa suatu informasi

numerik. Informasi ini tergantung pada aplikasi yang sedang kita dipelajari. Bobot pada network

dapat berasosiasi dengan edge/arc, dan mungkin juga dengan vertex. Catat bahwa sebuah graph

atau digraph hanya mewakili keterhubungan dari sistem, dan tidak memberikan informasi lebih

lanjut tentang elemennya. Network, menyampaikan informaasi kuantitif tambahan yang diperlukan

tersebut.

Jaringan Jalan

Pada jaringan jalan raya, bobot dari setiap arc (jalan) mungkin berkorespenden dengan

panjangnya jalan, estimasi waktu tempuh, biaya perjalanan (bahan bakar, peralatan, dll). Bobot juga

mungkin diberikan berkaitan dengan daya tarik pemandangan, tingkat bahaya pada perjalanan

tersebut, atau kualitas permukaan jalan.

Sekarang misalkan kita ingin menemukan rute antar dua kota dan menetapkan jarak sebagai

bobot yang berkoresponden dengan edge pada graph. Masalah menentukan jarak terpendak antara

dua kota pada peta berarti mencari rute terpendek antara dua vertex pada graph, sehingga memiliki

total bobot yang paling kecil. Masalah jalur terpendek yang sederhana seperti ini dapat dipecahkan

dengan memeriksa semua jalur.

Latihan 1.7 Dengan cara memerikasa rute yang ada, carilah rute terpendek dari S ke T pada jaringan berikut.

Jaringan Pipa

Gambar 1.17 mewakili sebuah jaringan pipa untuk gas, minyak atau air yang mengalir dari

sumber S ke terminal T. Setiap titik A-I merepresentasikan persimpangan pipa di mana total aliran

yang masuk pada persimpangan harus sama dengan total aliran yang keluar. Setiap garis antara dua

persimpangan merepresentasikan pipa, dan nilainya mewakili kapasitas dari pipa tersebut. Aliran

pada pipa tidak boleh melebihi kapasitas, dan harus melalui arah yang telah ditentukan. Jika kita

memiliki gas dengan kapasitas kurang dari 7 unit, maka gas tersebut dapat dikirim melewati rute S-

A-D-G-T tanpa melebihi kapasitas pipa SA,AD,DG,GT.

12

Gambar 1.17 Contoh jaringan pipa dan kapasitasnya

Model Graph

Kita telah mempelajari bagaimana kita dapat memakai graph untuk mengorganisir

pengetahuan dari sifat stuktural pada berbagai situasi. Representasi graph dari suatu permasalahan

disebut sebagai model. Model yang kita kembangkan berdasarkan pada struktur formal dari

matematika kombinatorial, khususnya pada teori graph.

Sebelum merepresentasikan suatu situasi dalam bentuk graph, kita harus melakukan analisis

permasalahan dengan hati-hati dan mempelajari sifat graph yang mungkin muncul sesuai situasi

tersebut. Pada umumnya, representasi sifat yang dapat diwakili oleh graph dilakukan dengan salah

satu dari dua cara berikut.

1. Elemen pada struktur diwakili oleh vertex dan hubungannya diwakili oleh edge.

2. Elemen pada struktur diwakili oleh edge dan hubungannya diwakili oleh vertex.

Klasifikasi Masalah

Permasalahan yang akan kita temui dalam mempelajari graph, dapat dijelaskan sebagai satu

dari permasalahan pada Tabel 1.1 berikut.

Tabel 1.1 Klasifikasi Masalah

Jenis masalah Contoh pertanyaan Deskripsi

1. Masalah eksistensi

Apakah terdapat….? Apakah mungkin …?

Ada atau tidak adanya solusi untuk permasalahan.

2. Masalah konstruksi

Jika ada, bagaimana kita membangunnya?

Konstruksi terhadap solusi masalah tersebut.

3. Masalah enumerasi

Berapa banyak? Dapatkah kita mendaftarnya?

Menghitung berapa banyak solusi yang ada dan mendaftar apa saja solusi tersebut.

4. Masalah optimasi

JIka ada, mana yang paling baik?

Solusi terbaik atas masalah tersebut (memaksimalkan atau meminimalkan suatu parameter).

13

Pencarian Solusi

Untuk mencari solusi atas permasalahan yang ada, terdapat pendekatan pencarian solusi

sebagai berikut.

1. Teoritis

Dalam suatu permasalahan graph, kita dapat menentukan tipe graph tersebut, mempelajari

sifat-sifatnya, membuat dugaan, dan membuktikan suatu teori. Teorema graph yang sudah

ada, banyak menunjukan kita apakah pada graph yang kita miliki terdapat sifat-sifat

tertentu. Metode teoritis ini dapat menyelesaikan masalah eksistensi, namun biasanya tidak

menyelesaikan masalah konstruksi.

2. Metode Praktis

Pendekatan ini adalah pendekatan dengan menunjukan secara langsung sifat yang dapat

muncul pada suatu graph dengan membangun objek tersebut. Dalam melakukan konstruksi

solusi, banyak masalah yang dapat diselesaikan dengan cara coba-coba atau dengan cara

memeriksa semua penyelesaian yang mungkin. Namun cara ini bisa sangat kompleks dan

memerlukan banyak waktu, sehingga menjadi cara yang tidak praktis untuk diterapkan.

Untuk membangun solusi pada masalah yang kompleks, kita membutuhkan prosedur

sistematik langkah demi langkah yang dapat diaplikasikan terhadap sistem yang besar.

Prosedur ini disebut algoritma.

Algoritma adalah sebuah prosedur sistematik langkah demi langkah yang terdiri dari : Penjelasan data masukan yang tepat Sejumlah perintah yang terbatas, terurut, yang dapat dilakukan satu demi satu Perintah perhentian yang menunjukan kapan prosedur selesai Penjelasan dari data keluaran yang tepat.

3. Metode Heuristic

Pada banyak masalah optimasi, tidak sulit untuk menemukan algoritma yang sesuai yang

dapat diaplikasikan secara cepat dan efisien. Salah satu contohnya adalah masalah pencarian

rute terpendek. Sayangnya ada juga permasalahan yang tidak diketahui algoritma efisien

untuk menyelesaikannya. Untuk mengatasi masalah tersebut, banyak diterapkan metode

heuristic berdasarkan pengalaman dan intuisi. Metode ini cukup baik dan cepat

diaplikasikan, namun tidak selalu mengarahkan kita pada solusi yang benar. Keluaran

metode ini merupakan sebuah pendekatan terhadap nilai yang benar.