REPRESENTASI MATRIKS PADA GRAFOleh :

Sri Widaningsih,MT

Matrik dari graf sangat cocok dan berguna untuk merepresentasikan graf pada komputer

Pada materi ini akan dibahas mengenai Matriks Insidensi/bersisian

(Incidence Matrix) Matriks Ajasensi/bertetangga

(Adjacency Matrix)

MATRIKS INSIDENSI

Misalkan G adalah sebuah graph dengan n titik, e sisi, dan tidak memuat loop. Definisikan sebuah matriks A = [aij] berordo n x e dengan n menyatakan baris dan e menyatakan kolom sebagai berikut: Elemen matriks aij = 1 jika sisi ke-j ,ej insiden dengan titik vi dan

= 0 , jika lainnya

Contoh sebuah graph dengan matriks insidensinya disajikan pada gambar di samping ini. Matriks semacam ini disebut matriks insidensi.

4

3

2

1

Sebuah matriks insidensi hanya memuat dua kemungkinan elemen yaitu 0 dan 1. Matriks seperti ini disebut matriks biner atau matriks (0,1).

Beberapa hal mengenai matrik insidensi :1. Ketika tiap sisi hanya bersisian dengan tepat

dua simpul, maka tiap kolom dari matriks A hanya memuat tepat dua elemen 1.

2. Banyaknya elemen 1 pada tiap baris sama dengan derajat dari titik yang berpadanan.

3. Sebuah baris yang semua elemennya 0, menyatakan sebuah simpul terisolasi.

4. Sisi-sisi paralel dalam sebuah graph akan menghasilkan kolom-kolom yang sama pada matriks insidensinya.

5.Jika sebuah graph G tidak terhubung dan terdiri atas dua komponen g1 dan g2, maka matriks insidensi A (G) dari graph G tersebut dapat ditulis sebagai berikut:

Dimana A(g1) dan A(g2) masing-masing merupakan matriks insidensi dari 2 komponen g1 dan g2. Karena tidak ada satupun sisi di g1 yang bersisian dengan simpul di g2.

MATRIKS SIRKUIT

Jumlah sirkuit yang berbeda dalam graf G dinyatakan dengan q dan jumlah sisi pada G dinyatakan oleh e.Maka matrik sirkuit B = [bij] dari G adalah matrik berordo q x e, dimana q sebagai baris dan e sebagai kolom, matrik (0,1) dinyatakan sebagai berikut :bij = 1, jika sirkuit ke-i mengandung sisi

ke-j, dan = 0 ,jika lainnya

Graf di samping memiliki 4 sirkuit yang berbeda {a,b}, {c,e,g}, {d,f,g} dan {c,d,f,e}, maka ukuran matrik adalah 4 x 8, matriknya adalah sbb :

Beberapa hal mengenai matrik sirkuit :1. Kolom yang berisi semuanya nol

berkorespondensi pada sisi non sirkuit (tidak ada sisi yang membentuk sirkuit)

2. Setiap baris pada B(G) adalah vektor sirkuit3. Pada matrik sirkuit dapat merepresentasikan

adanya loop dimana baris akan memiliki sebuah angka 1.

4. Jumlah 1 pada baris sama dengan jumlah sisi pada sisi yang berkorespondensi

5. Jika graf G terpisah dan terdiri dari 2 komponen g1 dan g2 maka matrik sirkuit B(G) dapat dituliskan dalam bentuk blok diagonal seperti berikut :

Dimana B(g1) dan B(g2) adalah matrik sirkuit untuk g1 dan g2. Ini berarti sirkuit di g1 tidak memiliki sisi pada g2

MATRIK SIRKUIT FUNDAMENTAL

Matrik sirkuit fundamental (Bf) adalah matrik sirkuit dimana semua baris berkorespondensi pada sejumlah sirkuit fundamental.

Sebuah graf dan matrik sirkuit fundamentalnya berhubungan dengan spanning tree.

Sebuah matrik Bf dapat disusun sebagai berikut

Dimana Iμ adalah matrik identitas dari nullity /jumlah tali hubung μ = e – n + 1 dan Bf adalah matrik sebaynyak jumlah cabang yaitu n-1.

Gambar di atas menunjukkan graf dan matrik sirkuit fundamental (spanning tree ditunjukkan dengan garis tebal)

MATRIK CUT SET

Matrik cut set C = [cij], dimana baris menyatakan cut-sets dan kolom menyatakan sisi pada graf, sebagai berikut :cij = 1 jika cut set ke-i mengandung sisi ke-j

= 0 , sebaliknya Jika kolom berisi 0 semua maka sisi

membentuk loop

MATRIK LINTASAN Matrik lintasan didefinisikan sebagai

pasangan simpul pada graf, sebut saja (x,y) ditulis sebagai P(x,y). Baris menyatakan lintasan berbeda antara simpul x dan y, sedangkan kolom menyatakan sisi pada G. Matrik lintasan untuk simpul (x,y) adalah P(x,y) = [pij] dimana pij = 1 , jika sisi ke-j berada pada lintasan ke-i

= 0, sebaliknya Kolom yang berisi 0 semua berarti sisi tidak

terdapat pada lintasan antara x dan y Kolom yang berisi 1 semua berarti terdapat

sisi untuk setiap lintasan antara x dan y Tidak ada baris dengan isi 0 semua

Contoh pada graf di bawah, lihat semua lintasan antara v3 dan v4. Terdapat 3 lintasan berbeda : {h,e}, {h,g,c}, dan {h,f,d,c}. Akan terbentuk matrik lintasan ukuran 3x8 seperti di bawah ini

MATRIK BERTETANGGA (ADAJENSI)

Misalkan G = (V,E) adalah graf dengan n simpul, n≥1. Matrik ketetanggaan G adalah matrik dwimatra dengan ukuran n x n. Bila matrik tersebut dinyatakan sebagai X = [xij] dimana :

xij = 1, jika i dan j bertetangga , = 0 jika sebaliknya Karena matrik ketetanggan hanya berisi 0

dan 1 maka disebut juga matrik nol-satu (zero-one).

Beberapa hal mengenai matrik ketetanggaan :1. Diagonal dari X semuanya 0 jika dan

hanya jika graf tidak memiliki loop. Loop pada simpul ke-i dinyatakan oleh xii = 1

2. Matrik ketetanggaan tidak dapat digunakan untuk mempresentasikan sisi ganda

3. Jika graf tidak memiliki loop (dan sisi ganda) , derajat simpul sama dengan jumlah angka 1 pada baris atau kolom X.

4. Matrik ketetanggan untuk graf sederhana dan tidak berarah selalu simetri tetapi untuk graf berarah belum tentu simetri

Untuk merepresentasikan sisi ganda pada matrik ketetanggaan, maka elemen xij pada matrik ketetanggaan sama dengan jumlah sisi yang berasosiasi dengan (vi, vj). Matrik ketetanggaan bukan lagi matrik nol-satu.

Derajat tiap simpul i dapat dihitung dari matrik keteta Derajat tiap simpul i:

(a) Untuk graf tak-berarah,

d(vi) =

(b) Untuk graf berarah,

din (vj) = jumlah nilai pada kolom j =

dout (vi) = jumlah nilai pada baris i =

n

iijx

1

n

jijx

1

n

jijx

1

Matrik ketetanggaan untuk graf berbobota

b

cd

e

10 12

8

15 911

14

SENARAI KETETANGGAN (ADJACENCY LIST)

Kelemahan matrik ketetanggan adalah bila graf memiliki jumlah sisi relatif sedikit, karena matriknya jarang (sparse), yaitu banyak mengadung nol, sedangkan elemen bukan nol sedikit. Maka akan mengambil ruang memori pada komputer sehingga menjadi boros. Untuk itu digunakan senarai ketetanggaan.