Graph Problems

" Graph Problems "

       Graf adalah kumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).

G = (V, E)

Dimana

G = Graph

V = Simpul atau Vertex, atau Node, atau Titik

E = Busur atau Edge, atau arc

Graf merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan tersebut.

Graph dapat digunakan sebagai cara yang sangat sederhana untuk memodelkan

banyak jaringan. Secara luas, sebuah jaringan adalah sebuah sistem yang melibatkan

aliran atau perpindahan komoditas. Sebuah jaringan komunikasi misalnya, dapat

dimodelkan ke dalam bentuk graph, dimana simpul menyatakan pusat komunikasi

(contohnya, saluran telepon) dan busur atau arc menyatakan jaringan komunikasi

(contohnya, saluran telegraf). Dalam memodelkan sebuah jaringan dengan graph,

simpul dalam graph umumnya dinyatakan dalam bentuk titik yang menyatakan asal

aliran serta tempat berakhir (contohnya, stasiun kereta api, terminal, pabrik dan lainlain).

Busur atau arc dalam graph secara umum menyatakan saluran dimana

komoditas berakhir (contohnya, trayek kereta api, rute penerbangan, aluran pipa dan

lain-lain). Sebuah graph juga memberikan model struktural dari jaringan. Dalam

kebanyakan jaringan, metode konstruksi biasanya dinyatakan oleh harga, efisiensi,

kehandalan dan kapasitas.

Jenis Graph

Berdasarkan arah dan bobot

1. Graph berarah dan berbobot (directed graph)

Graph yang setiap sisinya diberikan orientasi arah merupakan graph berarah, yang

disebut dengan busur (arc). Dalam graph berarah, (u,v) dan (v,u) menyatakan dua

buah busur yang berbeda, dengan kata lain bahwa (u,v) ¹ (v,u) . Pada busur (u,v),

simpul u dinamakan simpul asal dan simpul v merupakan simpul tujuan.

Graph berarah dan berbobot sering digunakan untuk menggambarkan aliran proses,

peta lintas kota dan lain sebagainya. Sehingga, pada graph gelang atau loop

diperbolehkan tetapi sisi ganda tidak diperbolehkan. Berikut contoh graph berarah dan

berbobot pada Gambar 2.1 dengan lima buah simpul dan delapan buah sisi.

Gambar 2.1 Graph Berarah dan Berbobot

2. Graph berarah dan tidak berbobot

Merupakan graph yang mempunyai orientasi arah namun tidak mempunyai bobot

apapun. Berikut contoh graph berarah dan tidak berbobot pada Gambar 2.2 dengan

lima buah simpul dan delapan buah sisi.

Gambar 2.2 Graph Berarah dan Tidak Berbobot

3. Graph tidak berarah dan berbobot (undirected graph)

Merupakan graph yang tidak mempunyai orientasi arah namun memiliki suatu bobot

pada sisinya. Sehingga, (u,v) = (v,u)merupakan sisi yang sama. Graph tidak berarah

dan berbobot ini sering digunakan dalam menggambarkan jaringan saluran telepon,

karena saluran telepon dapat beroperasi pada dua arah. Berikut contoh graph tidak

berarah dan berbobot pada Gambar 2.3 dengan lima buah simpul dan delapan buah

sisi.

Gambar 2.3 Graph Tidak Berarah dan Berbobot

4. Graph tidak berarah dan tidak berbobot

Graph yang setiap sisinya tidak mempunyai baik orientasi arah maupun bobot apapun.

Berikut contoh graph tidak berarah dan tidak berbobot pada Gambar 2.4 dengan lima

buah simpul dan delapan buah sisi.

Gambar 2.4 Graph Tidak Berarah dan Tidak Berbobot

Berdasarkan sifat keterhubungan

1. Perjalanan (Walk)

Perjalanan atau walk pada suatu graph G adalah barisan vertex dan edge secara

berganti-ganti 1 1 2 2 1 , , , ,..., , n n v e v e e v - dimana edge e1 menghubungkan vi dan i 1 v + dan

dapat hanya ditulis barisan edge atau barisan vertex saja ( 1 2 1 , ,..., n e e e - atau

1 2 1 , ,... , n n v v v v - ), dalam hal ini 1 v disebut vertex awal, dan n v disebut vertex akhir.

Vertex awal dan vertex 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 edge-nya berlainan

atau dengan kata lain tidak boleh berulang.

3. Jalur (Path)

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

kecuali untuk vertex awal dan vertex akhir.

4. Terhubung (Connected)

Suatu graph G dikatakan connected jika untuk setiap pasangan vertex didalam G

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

pasangan vertex yang tidak mempunyai path penghubung, graph yang demikian

disebut disconnected graph.

5. Sirkuit (Cycle)

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

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

Representasi Graph

Suatu graph dapat direpresentasikan ke beberapa bentuk. Representasi graph dapat

digunakan untuk mengimplementasikan graph tersebut ke dalam bentuk tertentu,

sehingga dapat digunakan pada berbagai kasus yang berbeda. Matriks dapat digunakan

untuk menyatakan suatu graph. Hal ini sangat membantu program komputer yang

berhubungan dengan graph. 

Ada dua cara standard dalam representasikan suatu graph,

yaitu dengan matriks ketetanggaan (adjacency matrix) dan senarai ketetanggaan

(adjacency list).

1. Matriks ketetanggaan (adjacency matrix)

Matriks ketetanggaan dari suatu graph G dengan nxn matriks A = [aij] menunjukkan

jumlah edge yang menghubungkan vi dan vj. aij bernilai 1 jika edge (i, j)ÎE

mempunyai arah dari vertex iÎV ke vertex jÎV , dan bernilai 0 jika tidak ada

orientasi arah sama sekali. Jika orientasi arah adalah loop, maka diberi nilai 2. Jika

graph G merupakan graph tidak berarah, setiap edge (i,j). Dalam hal ini, matriks

ketetanggaan E merupakan matriks simetris. Berikut tabel matriks ketetanggaan

(adjacency matrix) untuk graph berarah dan berbobot pada Gambar 2.1

Matriks Ketetanggaan Graph Gambar 2.1

Adapun bentuk matriks ketetanggaan untuk graph tidak berarah dan tidak berbobot

pada Gambar 2.4 dapat dilihat pada Tabel 2.2.

Matriks Ketetanggaan Graph Gambar 2.2

2. Senarai Ketetanggaan (adjacency list)

Pada representasi adjacency list dari suatu graph, n baris dari suatu matriks

ketetanggaan direpresentasikan sebagai n link list. Setiap vertex G memiliki sebuah

list. Vertex pada list i mempresentasikan vertex terhubung dari vertex i. Setiap vertex

setidaknya memiliki dua field: vertex dan link. Berikut bentuk senarai ketetanggaan

untuk graph berarah dan berbobot pada Gambar 2.1

Gambar 2.5 Senarai Ketetanggaan Graph Gambar 2.1

Adapun bentuk senarai ketetanggaan untuk graph tidak berarah dan tidak berbobot

pada Gambar 2.4 dapat dilihat pada Gambar 2.6.

Gambar 2.6 Senarai Ketetanggaan Graph Gambar 2.4

Permasalahan Optimasi

Persoalan optimasi (optimization problem) adalah persoalan yang menuntut

pencarian solusi optimum. Persoalan optimasi dibagi menjadi dua macam, yaitu

maksimasi (maximization) dan minimasi (minimization). Penentuan jalur terpanjang

merupakan salah satu contoh persoalan optimasi dimana termasuk ke dalam persoalan

optimasi maksimasi (maximization). Secara umum, penentuan jalur terpanjang dibagi

menjadi dua metode, yaitu metode konvensional, yang menggunakan perhitungan

matematika secara biasa dan metode heuristik, metode yang menggunakan

perhitungan matematika secara komputasi.

1. Metode Konvensional

Metode konvensional adalah metode yang diterapkan dengan menggunakan

perhitungan matematika murni atau secara biasa. Ada beberapa metode konvensional

yang sering digunakan untuk menyelesaikan masalah optimasi, diantaranya: algoritma

Djikstra, algoritma Floyd-Warshall, dan algoritma Bellman-Ford.

2. Metode Heuristik

Metode heuristik adalah salah satu dari bidang kecerdasan buatan yang digunakan

untuk menyelesaikan masalah optimasi. Terdapat beberapa algoritma dari metode

heuristik yang sering digunakan dalam permasalahan optimasi, diantaranya adalah

algoritma genetika, algoritma pencarian tabu, jaringan saraf tiruan, algoritma semut

dan lain-lain.

Persoalan Lintasan Terpanjang (Longest Path Problem)

Menurut Cormen dkk (1992), persoalan lintasan terpanjang pada graph merupakan

salah satu permasalahan optimasi. Graph yang digunakan merupakan graph tidak

berarah berbobot (undirected weighted graph), yaitu graph yang diberi bobot dan

tidak memiliki arah. Bobot antar vertex dinyatakan sebagai jarak antar kota, waktu,

pengiriman pesan dan lain-lain. Lintasan terpanjang merupakan suatu jaringan atau

kerangka jalur petunjuk perjalanan dari suatu vertex ke vertex lainnya atau yang

menjadi tujuan perjalanan dengan beberapa pilihan jalur yang mungkin untuk di

jalani.

Hamiltonian cycle merupakan contoh penggunaan lintasan terpanjang, karena

prinsip pada Hamiltonian cycle dimana setiap vertex hanya dikunjungi tepat satu kali.

Sehingga diperoleh bahwa Hamiltonian Cycle ≤ Longest Path.

Persoalan lintasan terpanjang (longest path problem) mempunyai beberapa

manfaat, diantaranya, yaitu kasus perhitungan worst-delay pada paket Ethernet.

Penggunaan real-time Ethernet protocol menjadi lebih relevan untuk aplikasi waktukritis

jaringan industri. Dalam konteks ini, disajikan suatu metode untuk menghitung

worst-delay paket Ethernet yang diaktifkan (Schmidt dkk, A Longest-Path Problem

for Evaluating The Worst-Case Packet Delay of Switched Ethernet).

Persoalan lintasan terpanjang juga digunakan dalam penjadwalan rute dan mesin bor

untuk mengebor lubang pada sebuah PCB dengan vertex sebagai bagian dari mesin

atau kakas untuk dibor dan edge sebagai waktu yang dibutuhkan dalam melakukan

retooling pada robot, manufaktur printed circuit dan sebagainya (Nugrahadi, 2007).

NP - Complete

NP – Problem adalah himpunan persoalan keputusan yang dapat diselesaikan oleh

algoritma non-deterministik dalam waktu polinomial. Menurut Munir (2005), NP –

Problem termasuk persoalan NP – Complete yang merupakan persoalan NP yang

paling sulit. Kebutuhan waktu suatu algoritma sangat bervariasi, mulai dari

O(1),O(log n),O(n),O(n2 ) dan sebagainya. Seluruh algoritma yang ada sejauh ini

merupakan algoritma polynomial-time: dimana input dengan ukuran n, worst-case

running time adalah ( ) k O n (dibaca ‘Big-O’) untuk beberapa nilai konstan k. Semua

algoritma digolongkan kedalam jenis algoritma yang ‘baik’ yang disebut sebagai

solusi polinomial. Hal ini dikarenakan oleh kebutuhan waktunya secara asimptotik

yang dibatasi oleh fungsi polinomial.

Adapun teknik-teknik yang dapat diterapkan pada algoritma dalam

permasalahan NP – Complete untuk menyelesaikan masalah komputasi pada

umumnya, yaitu:

a. Approximation: mencari solusi yang ‘hampir’ optimal solusi yang layak

(feasible solution).

b. Randomization: digunakan untuk mendapatkan running time yang diharapkan

lebih cepat dari rata-rata dan resiko kesalahan pada algoritma lebih kecil.

c. Restriction: algoritma diharapkan mempunyai running time yang lebih cepat

dengan membatasi input.

d. Parameterization: algoritma akan berjalan lebih cepat jika input parameter

tetap.

e. Heuristic: suatu algoritma diharapkan akan bekerja ‘cukup baik’.

Persoalan lintasan terpanjang yang juga merupakan permasalahan Hamiltonian cycle

merupakan persoalan dimana tidak terdapat solusi waktu polinomial untuk

menyelesaikannya. Contohnya Persoalan Pedagang Keliling (Traveling Salesman

Problem) yang merupakan implementasi pada persoalan Hamiltonian cycle yang juga

merupakan lintasan terpanjang, memiliki kompleksitas O(n!) .

Bukti. Diberikan suatu contoh graph G, salah satu algoritma keputusan yang mungkin

melampirkan seluruh permutasi dari vertex-vertex G lalu memeriksa hasil seluruh

permutasi untuk melihat apakah termasuk kedalam Hamiltonian cycle. Termasuk jenis

apakah running time pada algoritma tersebut? Kita gunakan representasi graph dalam

matriks adjacency, maka jumlah m pada vertex-vertex dalam graph adalah W( n) ,

dimana n = G merupakan panjang dari representasi G. Sehingga terdapat m!

permutasi yang mungkin pada vertex-vertex tersebut dan karena itu running time

algoritma adalah ( !) ( !) (2 ) n W m =W n =W .

Algoritma DFS (Depth-First Search)

Dalam pencarian suatu solusi optimum pada suatu graph, ada dua algoritma pencarian

yang dapat dilakukan, yaitu dengan algoritma DFS (Depth-First Search) dan

algoritma BFS (Breadth-First Search). Desiani dkk (2006) menggambarkan

ilustrasinya algoritma DFS yang dapat dilihat pada gambar berikut ini.

Gambar 2.7 Teknik pencarian algoritma Depth-First Search (DFS)

Berdasarkan gambar tersebut, proses pencarian dilakukan dengan mengunjungi

cabang terlebih dahulu hingga tiba di vertex terakhir. Jika tujuan yang diinginkan

belum tercapai, maka pencarian dilanjutkan ke cabang sebelumnya, turun ke bawah

jika memang masih ada cabangnya. Begitu seterusnya hingga diperoleh tujuan

akhirnya (goal). Operasi semacam ini dikenal dengan proses backtracking.

Algoritma DFS menggunakan metode pendekatan yang diimplementasikan dengan

menggunakan Tumpukan (Stack). Dalam algoritma DFS, ada aturan-aturan tertentu

yaitu:

1. Jika mungkin, lakukanlah kunjungan pada vertex-vertex yang belum

dikunjungi, lalu tandai (mark) dan masukkan ke Stack.

2. Jika terdapat kesulitan pada langkah 1, keluarkan vertex dari Stack. Lalu

kembali mencari vertex di bawahnya, sampai diperoleh vertex-vertex yang

belum dikunjungi agar keluar dari Stack.

3. Jika langkah 1 dan 2 telah selesai, maka algoritma DFS sudah mendapatkan

solusi optimum dari graph tersebut.

Isi dari Stack merupakan jalur yang diambil dari vertex awal, lalu vertex tersebut

akan disimpan (push). Saat algoritma kembali ke vertex awal, vertex-vertex yang

sudah dikunjungi akan dikeluarkan (pop) dari Stack.

Dengan demikian, pada Gambar 2.4 Graph Tidak Berarah dan Tidak Berbobot

algoritma secara otomatis akan mencari kunjungan yang memiliki lintasan dengan

bobot yang lebih besar , yaitu , a – b – d – e – c – a. Sehingga diperoleh solusi

optimum pada persoalan lintasan terpanjang.

Algoritma DFS secara garis besar dapat ditulis sebagai berikut :

public int getAdjUnvisitedVertex(int v)

{

for(int j=0; j<nVertex; j++)

if(adjMat[v][j] == 1 && VertexList[j].wasVisited == false)

//Mengembalikan simpul sesuai persyaratan.

return j;

//Simpul sesuai persyaratan tidak ada.

return -1;

}

Contoh penyelesaian pada kasus Traveling Salesman Problem (TSP) dengan

menggunakan algoritma DFS: Misalkan jalur yang ditetapkan pada kasus ini dimulai

dari kota ke-a dan berakhir di kota ke-e. Perhatikan Gambar 2.7 Graph Tidak Berarah

dan Tidak Berbobot abcde dan Tabel 2.3 Matriks Jarak antar vertex

Gambar 2.8 Graph Tidak Berarah dan Tidak Berbobot abcde

Matriks Jarak pada Graph Tidak Berarah abcde

Sehingga diperoleh suatu lintasan terpanjang, yaitu jalur a – c – d – b – e dengan

masing-masing bobot yang tersimpan dalam Stack adalah 25 – 20 – 25 – 10.

Algoritma Depth-First Search (DFS) memiliki kelebihan-kelebihan sebagai berikut:

a. Cepat dalam mencapai kedalaman pada ruang pencarian.

b. Jauh lebih efisien untuk ruang pencarian dengan banyak cabang karena tidak

perlu mengevaluasi semua simpul pada suatu level tertentu dalam daftar open.

c. Menggunakan memori yang relatif kecil karena hanya node-node pada lintasan

yang aktif saja yang disimpan.

Namun, Algoritma Depth-First Search (DFS) juga memiliki kelemahan, yaitu:

a. Memungkinkan tidak ditemukannya tujuan yang diharapkan.

b. Kemungkinan hanya akan mendapatkan satu solusi pada setiap pencarian.

Kompleksitas Algoritma

Algoritma adalah suatu prosedur secara komputasi dengan mengambil beberapa nilai,

atau kumpulan dari nilai, sebagai input atau masukan, dan menghasilkan nilai atau

kumpulan nilai sebagai output atau keluaran (Cormen dkk, 1992). Efisiensi algoritma

dinilai berdasarkan kecepatan waktu eksekusi dan penggunaan struktur data yang.

Efisiensi Algoritma

Algorima yang terbaik adalah bukan hanya berdasarkan karena algoritma itu harus

benar, akan tetapi juga harus dipandang dari segi efisiensinya. Jadi algoritma yang

terbaik adalah algoritma

Daftar Pustaka

http://repository.usu.ac.id/bitstream/123456789/26701/3/Chapter%20II.pdf