28
2.2.3
Representasi Graph
Bila
graph
akan
diproses
dengan
program
komputer,
maka graph
harus
direpresentasikan di dalam
memori. Terdapat beberapa representasi
yang
mungkin
untuk
graph, tapi di sini hanya diberikan dua macam representasi
yang sering digunakan, yaitu
matriks incidence dan matriks adjacency.
?
Matriks Bersisian (Incidence matrix)
Matriks
incidence
menyatakan
hubungan antara vertex
dan edge.
Misalkan
G
=
(V,E)
adalah
graph
dengan
n
vertex
dan
m
buah
edge.
Matriks
incidence
G
adalah
matriks
dwimatra
berukuran n
x
m.
Baris
menunjukkan
label
vertex,
sedangkan
kolom
menunjukkan
label edge-nya. Bila
matriks tersebut dinamakan
A
= [a
ij
],
maka a
ij
= 1 jika
vertex i bersisian/incidence dengan edge j,
sebaliknya a
ij
=
0
jika vertex i tidak bersisian
dengan
edge
j.
Matriks
bersisian
dapat
digunakan
untuk
merepresentasikan graph
yang
mengandung edge ganda/gelang.
Gambar 2.14. Contoh Undirected Graph
Sumber: www.hotlinkfiles.com/files/333140_d3mwg/Graph Theory Lecture Note
Part1.pdf
Apabila
graph
pada
Gambar
2.14.
direpresentasikan
dalam
matriks
incidence
maka akan didapat suatu bentuk
matriks incidence seperti
yang terdapat pada
Gambar
2.15.
 |