TI Politala Matdis 1C

1.    Matriks Ketetanggaan (adjacency matrix)

 A = [aij], 1, jika simpul i dan j bertetangga

aij = { 0, jika simpul i dan j tidak bertetangga

Derajat tiap simpul i :

(a)   Untuk graf tak-berarah

d(vi) = Σ=njija1

(b)   Untuk graf berarah,

 din (vj) = jumlah nilai pada kolom j = Σ=niija1

 d_out (vi) = jumlah nilai pada baris i = Σ=njija1

2.      Matriks Bersisian (incidency matrix)

 A = [aij],

 1, jika simpul i bersisian dengan sisi j

 aij = {

 0, jika simpul i tidak bersisian dengan sisi j

3.    Senarai Ketetanggaan (adjacency list)

Teorema Kuratoswki

Berguna untuk menentukan dengan tegas keplanaran suat graf.

(a) Graf Kuratowski pertama (K5)

 (b) Graf Kuratowski kedua (K3, 3)

(c) Graf yang isomorfik dengan graf Kuratowski kedua

TEOREMA Kuratowski. Graf G bersifat planar jika dan hanya jika ia tidak mengandung upagraf yang isomorfik dengan salah satu graf Kuratowski atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.

Sifat graf Kuratowski adalah:

 1.Kedua graf Kuratowski adalah graf teratur.

 2.Kedua graf Kuratowski adalah graf tidak-planar

 3. Penghapusan sisi atau simpul dari graf Kuratowski menyebabkannya menjadi graf planar. 4.Graf Kuratowski pertama adalah graf tidak-planar dengan jumlah simpul minimum, dan
    graf Kuratowski kedua adalah graf tidak-planar dengan jumlah sisi minimum.