MATRIKS PENYAJIAN GRAPH

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 graf 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 :

klik untuk memperbesar gambar

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.