Halo semua kali
ini bagian saya untuk menjelaskan apa itu Graph Problems atau Permasalahan Graf.
Sejarah awal Graf atau Teori Graf mulai dikenal saat matematikawan kebangsaan
Swiss bernama Leonhard Euler, yang berhasil mengungkapkan Misteri
Jembatan Koningsberg pada tahun1736.
Di kota Koningsberg mengalir sungai yang diberinama Pregel, disungai ini
mengalir dua pulau dan diantaranya terdapat jembatan yang menghubungkan
keduanya, jumlah jembatan tersebut sebanyak 7 buah. Jadi Leonhard Euler ini
berhasil memecahkan misteri jembatan ini dengan menggunakan Teori Graf
gambarannya seperti dibawah ini.
Graf
merupakan salah satu dari beberapa struktur data yang paling sering
diaplikasikan, dalam pemrograman komputer. Jika kita memutuskan untuk
menggunakan penyimpanan data yang bersifat external, kita mungkin tidak terlalu
membutuhkn graf, tetapi untuk beberapa permasalahan dimana kita memerlukan
referesentasi internal dalam memori komputer untuk suatu struktur data, graf
tidak bisa dihindari penggunaannya.
Graf adalah salah satu jenis struktur data
yang terdiri dari titik (vertex) dan garis (edge), dimana dalam graf tersebut,
vertex - vertex yang ada dihubungkan oleh edge, hingga menjadi suatu kesatuan
yang disebut graf. Sebagai contoh dari pemodelan graf adalah peta kota, dimana
kota disini sebagai vertex dan jalur yang menghubungkannya berlaku sebagai
edge. (Mulai Pusing T_T)
(Lanjut ^_^)
Suatu
graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). Verteks
menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara
verteks. Biasanya untuk suatu graph G digunakan notasi matematis.
G = (V. E)
Dimana: G = Graph
V = Simpul
atau Vertex, atau Node, atau Titil
E = Busur
atau Edge, atau Arc;
Ada beberapa tentang jenis graf sendiri, yaitu:
·
Graf Berarah : adalah graf yang edge-nya
memiliki arah, sebagai contoh edge AB menghubungkan vertex A ke B, dimana
hubungan vertex B ke A, harus diperoleh 2.
·
dari edge lain,
yaitu edge BA, dan jika edge BA tidak ada, maka vertex B ke A tidak memiliki
hubungan, meski vertex A ke B memiliki hubungan
·
Graf Tak Berarah
: adalah graf yang edge-nya tidak memiliki arah, sehingga jika edge AB
menghubungkan vertex A ke B, maka secara otomatis juga menghubungkan vertex B
ke A.
·
Graf Berbobot :
adalah suatu graf dimana edge dari graf tersebut memiliki bobot atau nilai
tertentu.
·
Graf Tidak
Berbobot : adalah suatu graf dimana edge dari graf tersebut tidak memiliki
bobot atau nilai. Untuk merepresentasikannya dalam pemrograman komputer, graf
dapat disusun dari LinkedList yang berada dalam LinkedList.
Ok mungkin pengenalan tentang Graf saya rasa cukup,
dan sekarang kita akan mengenal istilah-istilah yang berkaitan tentang Graf. Dalam
Graf ada tiga istilah yang sering disebut yaitu:
a. Vertex
Vertex adalah himpunan node / titik pada sebuah Graf.
b. Edge
Edge adalah himpunan garis yang menghubungkan tiap
node / vertex/
c. Adjacent
Adjacent adalah dua buah titik yang dikatakan
berdekatan (adjacent) jika titik tersebut tersebut terhubung dengan sebuah
sisi. Untuk contohnya bias perhatikan gambar berikut:
Penjelsannya
adalah Sisi e3 = v2v3 insident dengan titik v2 dan titik v3, tetapi sisi
e3 = v2v3 tidak insident dengan titik v1 dan titik v4.
Titik v1 adjacent dengan titik v2 dan titik v3, tetapi
titik v1 tidak adjacent dengan titik v4. Maaf kurang jika
kurang jelas T_T)
d.
Weight
Weight
adalah Sebuah graf G = (V, E) disebut sebuah Graf Berbobot (weight
graph), apabila terdapat sebuah fungsi bobot bernilai real W pada himpunan
E,
W : E ® R,
nilai W(e) disebut
bobot untuk sisi e, " e Î E. Graf berbobot tersebut dinyatakan pula
sebagai G = (V, E, W).
Graf berbobot G =
(V, E, W) dapat menyatakan
* suatu sistem
perhubungan udara, di mana
· V = himpunan
kota-kota
· E = himpunan
penerbangan langsung dari satu kota ke kota lain
· W = fungsi
bernilai real pada E yang menyatakan jarak atau ongkos atau waktu
* suatu sistem
jaringan komputer, di mana
· V = himpunan
komputer
· E = himpunan
jalur komunikasi langsung antar dua komputer
· W = fungsi
bernilai real pada E yang menyatakan jarak atau ongkos atau waktu
e.
Path
Path
adalah Walk dengan setiap vertex berbeda. Contoj, P = D5B4C2A Sebuah Walk (W) didefinisikan sebagai
urutan (tdk nol) vertex & edge. Diawali origin vertex dan diakhiri terminus
vertex. Dan setiap 2 edge berurutan adalah series. Contoh, W = A1B3C4B1A2.
f.
Cycle
Cycle
adalah Siklus ( Cycle ) atau Sirkuit ( Circuit ) Lintasan yang
berawal dan berakhir pada simpul yang sama
Mungkin cukup
seperti itu tentang pengenalan Graf
karena saya juga belum terlalu paham (^_^) kalua terlalu dipaksain nanti
malah Sakit Kepala, sekarang kita lanjut ke bagaimana merepresentasikan Graf
kedalam sebuah program.
Agar data yang ada
dalam graph dapat diolah, maka graph harus dinyatakan dalam suatu struktur data
yang dapat mewakili graph tersebut. Dalam hal ini graph perlu direpresentasikan
kedalam bentuk array dan dimensi yang sering disebut matrix atau direpresentasikan
dalam bentuk linked list. Bentuk mana yang dipilih biasanya tergantung kepada
efisiensi dan kemudahan dalam membuat program. Berikut ini beberapa bentuk
representasi graph:
1.
Represenatasi Graf dalam bentuk Matrix:
a.
Ajacency Matrix Graf Tak Berarah
Matrix yang
digambarkan pada gambar 1b merupakan representasi dalam bentuk Adjacency Matrik
dari graf yang digambarkan pada gambar 1a. Beberapa hal yang dapat dilihat atau
dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai berikut :
·
Matrik yang terbentuk adalah matrik bujur
sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik
ini menyatakan hubungan antara simpul satu dengan simpul lainnya.
·
Matrik yang terbentuk adalah matrik simetris
dengan sumbu simetris adalah diagonal dari titik kiri atas ke titik kanan
bawah.
·
Data yang tedapat baik dalam baris maupun kolom,
dapat menyatakan degree sebuah simpul. Contoh : baik pada baris D maupun kolom
D jumlah angka 1 nya adalah 3 buah, dimana jumlah ini menyatakan degree simpul
D.
b.
Ajacency Matrix Graf Berarah
(perhatikan tanda panahnya)
Matrik yang
digambarkan pada gambar 2b merupakan representasi dalam bentuk Adjacency Matrik
dari graf yang digambarkan pada gambar 2a. Beberapa hal yang dapat dilihat atau
dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai berikut :
·
Matrik yang terbentuk adalah matrik bujur
sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik
ini menyatakan hubungan antara simpul satu dengan simpul lainnya.
·
Matrik yang terbentuk mungkin simetris mungkin
juga tidak simetris. Menjadi Simetris bila hubungan antara dua buah simpul (v1
dan v2) terdapat busur dari v1 ke v2 dan juga sebaliknya.
·
Hal pokok yang dinyatakan oleh matrik ini adalah
: busur yang ’keluar’ dari suatu simpul. Dengan demikian, data yang terdapat
dalam suatu baris, dapat menyatakan outdegree simpul yang bersangkutan.
Contoh : Jumlah
elemen yang nilainya = 1 pada baris B ada 3 elemen,ini menyatakan jumlah
outdegree simpul B adalah 3 buah.
·
Data yang terdapat dalam suatu kolom, dapat
menyatakan indegree simpul bersangkutan.
Contoh : Jumlah
elemen yang nilainya 1 pada kolom B ada 2 elemen, ini menyatakan indegree
simpul B adalah 2 buah.
c.
Adjacency Matrix Graf Berbobot Tak Berarah
Nilai yang ada
dalam tiap elemen matrik, menyatakan bobot busur yang menghubungkan dua buah
simpul yang bersangkutan. Untuk dua buah simpul yang tidak berhubungan langsung
oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang nilai
bobotnya tidak terhingga. Dalam pemograman, karena keperluan algoritma, maka
dari total bobot seluruh busur yang ada atau yang mungkin ada.
Contoh: pada
gambar 3a simpul A dan C tidak berhubungan langsung melalui sebuah busur, maka
untuk elemen matrik yang bersangkutan diisi dengan nilai 999 karena nilai 999
dalam kasus ini cukup mewakili nilai tidak terhingga.
2.
Representasi Graf dalam bentuk Linked List
a.
Adjacency List
Bila ingin
direpresentasikan dalam bentuk linked list, dapat diilustrasikan secara
sederhana seperti gamabar 4b. Dari ilustrasi sederhana tersebut terlihat ada 5
buah simpul A,B,C,D,dan E yang dibariskan dari atas kebawah seperti pada gambar
4a. Kemudian dari masing-masing simpul ’keluar’ pointer kearah kanan yang
menunjuk simpul-simpul lain. Salah satu contoh, yang dapat dilihat pada gambar
4b dimana A menunjuk simpul B dan simpul D.
Dalam Adjacency
List, kita perlu membedakan antara simpul-vertex dan simpul-edge. Simpul-vertex
untuk menyatakan simpul atau vertex, dan simpul-edge untuk menyatakan hubungan
antar simpul yang biasa disebut busur. Struktur keduanya bisa sama, bisa juga
tidak sama,tergantung kebutuhan.Untuk memudahkan pembuatan program, struktur
kedua macam simpul dibuat sama seperti yang digambarkan pada gambar 5c. Yang
membedakan antara simpul-vertex dan simpul-edge, adalah anggapan terhadap
simpul tersebut. Dalam contoh ini, terlihat struktur simpul dibuat terdiri dari
3 elemen. Satu elemen untuk INFO, dua elemen untuk pointer.pointer kiri (left)
dan pointer kanan (right).
Struct tipes {
Struct types *Left;
Int INFO;
Struct tipes *Right;
};
Struct
tipes *First, *Pvertex, *Pedge;
- Bila simpul dianggap sebagai simpul Vertex,
maka:
Pointer left
digunakan untuk menunjuk simpul berikutnya dalam untaian simpul-simpul yang
ada, atau diisi NULL bila sudah tidak ada simpul yang pelu ditunjuk.Sedangkan
pointer Right digunakan untuk menunjuk simpul edge yang pertama.
- Bila Simpul dianggap sebagai simpul Edge, maka:
Pointer left
digunakan untuk menunjuk simpul-vertex ‘tujuan’ yang berhubungan dengan
simpul-vertex ‘asal’ dan pointer right digunakan untuk menunjuk simpul-edge
berkiutnya bila masih ada, atau diisi NULL bila tak ada lagi simpul-busur yang
ditunjuk.
Dan terakhir ini
adalah contoh implementasi Graf dalam pemerogramman C++:
#include
<iostream>
#include
<conio.h>
using namespace
std;
int main(void)
{
double
matriks[10][10],matriksb[10][10],hasil[10][10];
int
CC,i,j,k,l,edge,vertex,asal,tujuan,panjang;
cout<<"Jumlah
Vertex \t : ";
cin>>vertex;
//jumlah vertex/simpul graph
cout<<"Jumlah
Edge \t : ";
cin>>edge;
//jumlah sisi pada graph
for
(i=1;i<=vertex;i++)
{
for
(j=1;j<=vertex;j++)
{
matriks[i][j]=0;
//penginisialisasian awal matriks
}
}
for
(i=1;i<=edge;i++) //pembentukkan matriks berdasarkan graph
{
cout<<"~Edge
ke-"<<i<<"~\n";
cout<<"Vertex
asal \t : ";cin>>asal;
cout<<"Vertex
tujuan \t : ";cin>>tujuan;
matriks[asal][tujuan]+=1;
matriks[tujuan][asal]+=1;
}
for (i=1;i<=vertex;i++)
{
for
(j=1;j<=vertex;j++)
{
hasil[i][j]=0;
for (k=1;k<=vertex;k++)
{
CC=matriks[i][k]*matriks[k][j];
hasil[i][j]=hasil[i][j]+CC;
}
}
}
/*cout<<"
Element matriks C [hasil] : "<<endl;
for
(i=1;i<=vertex;i++) //menampilkan matriks hasil perkalian
{
for
(j=1;j<=vertex;j++)
{
cout<<" "<<hasil[i][j];
}
cout<<endl;
}*/
cout<<"~Menentukan
Banyak Walk yang mungkin~\nMasukkan vertex awal \t : ";cin>>i;
cout<<"Masukkan
vertex Tujuan \t : ";cin>>j;
cout<<"Jumlah
Walk dari vertex "<<i<<" ke vertex
"<<j<<" dengan panjang "<<panjang<<
" sebanyak "<<hasil[i][j]<<" Walks";
getch();
}
Kesimpulan :
Saya
sendiri masih bingung dengan Graf Problems tapi mungkin bisalah sedikit
menyimpulkan jadi suatu graph didefinisikan oleh himpunan verteks dan
himpunan sisi (edge). Verteks menyatakan entitas-entitas data dan sisi
menyatakan keterhubungan antara verteks. Graph dalam kehidupan sehari-hari
dapat dianalogikan sebagai suatu jaringan satu dengan jaringan lainnya yang
saling terhubung. Missal seperti Negara Indonesia yang memiliki banyak kota
seperti : Jakarta, Bandung, Surabay, Yogyakarta, Gowa. Kota-kota itulah yang
tergabung dalam Negara Indonesia dan kota-kota itulah yang saling berhubungan.
Tidak ada komentar:
Posting Komentar