MATRIK PENYAJIAN GRAPH dalam Struktur Data

contoh bahwa G graf dengan N simpul dan M ruas. Untuk mempermudah komputasi, graf dapat disajikan dalam bentuk matriks, disebut Matriks Ruas, yang berukuran (2 x M) atau (M x 2) yang menyatakan ruas dari graf.

Matriks adjacency dari graf G tanpa ruas sejajar adalah matriks A
berukuran (N x N), yang bersifat :
1, bila ada ruas (vi, vj)a =
0, dalam hal lain


Matriks adjacency merupakan matriks simetri.
Untuk graph dengan ruas sejajar, matriks adjacency didefinisikan
sebagai berikut :

p, bila ada p buah ruas menghubungkan (vi, vj) (p > 0)
a =
0, dalam hal lain


Matriks Incidence dari graf G, tanpa self-loop didefinisikan sebagai
matriks M berukuran (N x M)
1, bila ruas ej berujung di simpul vi,
m =
0, dalam hal lain
contoh :

GRAF BERARAH (DIGRAF)

Suatu graf berarah (digraf) D terdiri atas 2 himpunan :
1. Himpunan V, anggotanya disebut simpul
2. Himpunan A, merupakan himpunan pasangan terurut, yang
disebut ruas berarah atau arkus.

Notasi : D(V, A)

Simpul, anggota v, digambarkan sebagai titik (atau lingkaran
kecil). Sedangkan arkus a=(u,v), digambarkan sebagai garis
dilengkapi dengan tanda panah mengarah dari simpul u ke simpul
v. Simpul u disebut titik pangkal, dan simpul v disebut titik terminal
dari arkus tersebut.