BAB III

TEORI GRAF

Definisi : graf G didefinisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G =

(V,E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertices atau

node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul.

Simpul graf dapat dinomori dengan huruf, seperti a,b,c…v,w…..dengan bilangan asli

1,2,3….atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul u dengan v

dinyatakan dengan pasangan (u,v) atau dinyatakan dengan lambing e1,e2…..dengan kata lain, jika e

adalah sisi yang menghubungkan simpul u dengan simpul v, maka e dapat ditulis sebagai:

e = (v,v)

Contoh: sisi ganda (multiple/pararel edges)

1 1 e4 e1 1 e4

2 32

e1 e3 3 2 e2

e3 e8

e5 e6 e7 e5 e6 e7 loop

4 4 4

(a) G1 (b) G2 (c) G3

Graf sederhana graf ganda graf semu

# Jenis-jenis graf#

Berdasarkan ada tidaknya sisi ganda pada graf, maka secara umum graf dapat digolongkan

menjadi dua jenis:

Graf sederhana (simple graph)

Graf yang tidak mengandung loop maupun sisi ganda dinamakan graf sederhana. Pada

graf sederhana sisi adalah pasangan tak terurut (unordered pairs). Jadi menuliskan sisi

35

(u,v) sama dengan (v,u). Dapat didefinisikan garf sederhana G = (V,E) terdiri dari

himpunan tidak kosong simpul-simpul dan E adalah himpunan pasangan tak terurut yang

berbeda yang disebut sisi.

Graf tak sederhana (unsimple graph)

Graf yang mengandung loop dinamankan graf tak sederhana (unsimple graph). Ada

dua macam graf tak sederhana:

1. Graf ganda (multigraph) adalah graf yang mengandung sisi ganda. Sisi ganda

yang menghubungkan sepasang simpul lebih dari dua.

2. Graf semu (pseudograph) adalah graf yang mengandung loop.

Jumlah simpul pada graf disebut sebagai kardinalitas graf, dan dinyatakan dengan n = |V|, dan

jumlah sisi dinyatakan dengan m = |E|.

Sisi pada graf mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi maka secara

umum graf dibedakan atas dua jenis:

1. Graf tak berarah (undirected graph) adalah graf yang sisinya tidak mempunyai orientasi

arah. Pada graf tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak

diperhatikan.

2. Graf berarah (directed graph atau digraph) adalah graf yang setiap sisinya diberikan

orientasi arah. Pada graf berarah (u,v) ≠ (v,u), untuk simpul u dinamakan simpul asal

(initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex).

1 1

2 3 2 3

4 4

(a) G4 (b) G5

36

#Terminology Dasar#

1 1

1

e2 e1 e3

2 3 2

e42 3

4 3 e54

(a) (b) (c)

Adjacent (bertetangga)

Definisi : dua buah simpul pada graf tak berarah G dikatakan adjacent bila keduanya

terhubung langsung dengan sebuah sisi. Dengan kata lain, u adjacent v jika (u,v) adalah

sebuah sisi pada graf G.

Incident (bersisian)

Definisi : untuk sembarang sisi e = (u,v), sisi e dikatakan incident dengan simpul u dan

simpul v.

Isolated Vertex (simpul terisolasi)

Definisi : simpul yang tidak mempunyai sisi yang incident dengannya. Atau, dapat

dinyatakan bahwa simpul yang terisolated adalah simpul yang tidak satupun adjacent

dengan simpul-simpul lainnya.

Null Graph/Empty Graph (graf kosong)

Definisi : graf yang himpunan sisinya merupakan himpunan kosong disebut sebagai graf

kosong dan ditulis Nn, yang dalam hal ini n adalah jumlah simpul.

37

Degree (derajat)

Definisi : derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang incident

dengan simpul tersebut.

Untuk graf berarah derajat simpul V dinyatakan dengan din(v) dan dout(v) dalam hal ini:

din(V) = derajat masuk (in degree) = jumlah busur yang masuk ke simpul v.

dout(v) = derajat keluar (out degree) = jumlah busur yang keluar dari simpul v.

a b

c d

Path (lintasan)

Definisi : lintasan yang panjangnya n dari simpul awal vo ke simpul tujuan vn di dalam

graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk

vo,e1,v1,e2,v2,e3.....vn-1,en,vn sedemikian sehingga e1 = (v1,v2),…..,en = (vn-1,vn) adalah sisi-sisi

dari graf G.

Lintasan sederhana (simple path), jika semua simpulnya berbeda (setiap sisian yang

dilalui hanya satu kali).

Lintasan tertutup (closed path), lintasan yang berawal dan berakhir pada simpul yang

sama.

Lintasan terbuka (open path), lintasan yang tidak berawal dan berakhir pada simpul

yang sama.

38

Siklus (cycle) atau Sirkuit (circuit)

Definisi : lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau

siklus.

Connected (terhubung)

Definisi : graf berarah G dikatakan terhubung jika graf tak berarahnya terhubung (graf

tak berarah dari G diperoleh dengan menghilangkan arahnya).

Keterhubungan dua buah simpul pada graf berarah dibedakan menjadi terhubung kuat

dan terhubung lemah.

Dua simpul, u dan v pada graf berarah G disebut terhubung kuat (strongly connected)

jika terdapat lintasan berarah dari u ke v, dan juga sebaliknya lintasan berarah dari v ke

u.

Jika u dan v tidak terhubung kuat tapi tetap terhubung pada graf tak berarahnya, maka u

dan v dikatakan terhubung lemah (weakly connected).

1 1

5 2 5 2

4 3 4 3

(a) (b)

Graf berarah terhubung kuat Graf berarah terhubung lemah

39

2 5

6

4 7

1 8

3

Gb. Graf tak-berarah tidak terhubung

Subgraf (upagraph) dan Komplemen Upagraph

Definisi subgraf : misalkan G = (V,E) adalah sebuah graf. G1 = (V1,E1) adalah upagraf

(subgraf) dari G jika V1 ⊆ V dan E1 ⊆ E

Definisi komplemen : dari upgraf G1 terhadap graf G adalah graf G2 = (V2,E2)

sedemikian sehingga E2 = E – E1 dan V2 adalah himpunan simpul yang anggota-

anggotanya E2 bersisian dengannya.

2 2

1 3

1 3 1

3

6

6

2 5 5

4 5

(a) (b) (c)

Spanning Subgraph (upagraf merentang)

Definisi : upagraf G1 = (V1,E1) dari G (V,E) dikatakan spanning subgraph jika V1 = V

(yaitu G1 mengandung semua simpul dari G).

40

1 1 1

2 3 2 3 2 3

4 5 4 5

Cut –Set (bridge)

Definisi : cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G

menyebabkan G tidak terhubung. Jadi cut-set selalu menghasilkan dua buah komponen

terhubung.

1 2 1 2

5 6 5 6

3 4 3

4

Weighted Graph (graf berbobot)

Definisi : graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).

A

10 12

E 8 B

15 1111 9

D C

# Beberapa Graf Sederhana Khusus#

41

8

11

14

Ada beberapa graf sederhana khusus yang dijumpai pada banyak aplikasi. Beberapa di antaranya

diperkenalkan di bawah ini:

Complete Graph (graf lengkap)

Adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.

Complete graph dengan n buah simpul di lambangkan dengan Kn. setiap simpul pada Kn

berderajat n – 1

K1 K2 K3 K4 K5 K6

Graf Lingkaran

Ialah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan

simpul n simpul dilambangkan dengan Cn. jika simpul-simpul pada Cn adalah v1,v2…vn,

maka sisi-sisinya adalah (v1,v2),(v2,v3),….,(vn,vn), dan (vn,v1). Dengan kata lain, ada sisi

dari simpul terakhir, vn, ke simpul pertama, v1.

Regular Graphs (graf teratur)

Graf yangsetiap simpulnya mempunyai derajat yang sama disebut graf teratur, apabila

derajat setiap simpul adalah r, maka graf disebut sebagai graf teratur derajat r.

42

Derajat 2

derajat 0 derajat 1

Bipartite Graph (graf bipartit)

Graf G yang himpunan simpulnya dapat dikelompokan menjadi dua himpunan bagian V1

dan V2, sedemikian sehingga setiap sisi di dalam G menghubungkan sebuah simpul di V1

ke sebuah simpul di V2 disebut graf bipartite dan dinyatakan sebagai G (V1,V2). Dengan

kata lain, setiap simpul di V1 (demikian pula dengan simpul-simpul di V2) tidak adjacent.

A B

G C

F

E D

REPRESENTASI GRAF

1. Adjacency Matrix (matriks bertetangga)

Adjacency matrix adalah representasi graf yang paling umum. Misalkan G = (V,E)

adalah graf dengan n simpul, n ≥ 1. Matriks adjacency G adalah matriks yang berukuran

n x n. Bila matriks tersebut dinamakan A = [aij], maka aij = 1 jika simpul i dan j

adjacency, sebaliknya aij = 0 jika simpul i dan j tidak adjacency.

43

Matrik adjacency berisi 0 dan 1, maka matriks tersebut dinamakan matriks nol satu

(zero-one). Selain dengan angka 0 dan 1, elemen matriks dapat juga dinyatakan dengan

false (0) dan true (1).

1 1 1

5

2 3

2 3 3

2 4

4 4

1 2 3 4 1 2 3 4 5 1 2 3 4

1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0

2 1 0 1 0 2 1 0 1 0 0 2 1 0 1 1

3 1 1 0 1 3 1 1 0 1 0 3 1 0 0 0

4 0 1 1 0 4 0 0 1 0 0 4 0 1 1 0

5 0 0 0 0 0

(a) (b) (c)

2. Incidency Matrix (matriks bersisian)

Bila matriks adjacency menyatkan simpul-simpul di dalam graf, maka incidency matriks

menyatakan simpul dengan sisi. Missalkan G = (V,E) adalah graf dengan n simpul dan

m buah sisi. Incidency matriks G adalah matriks yang berukuran n x m. Baris

menunjukkan simpul dan kolom menunjukan sisi.

Incidency matriks dapat digunakan untuk merepresentasikan graf yang mengandung loop.

44

e1 e1 e2 e3 e4 e5 e6

1 e2

2 1 1 1 0 1 0 0

e4 e3 2 1 1 1 0 0 0

3 3 0 0 1 1 1 0

4 e5 4 0 0 0 0 1 1

e6

3. Adjacency List

Kelemahan adjacency list adalah bila graf memiliki jumlah sisi relative sedikit, karena

matriksnya bersifat jarang (sparse), yaitu mengandung banyak elemen nol, sedangkan

elemen yang bukan nol sedikit.

1 1 5 1

2 3 2 3

4 2 4

4

Adjacency List:

1 : 2,3 1 : 2,3 1: 2

2: 1,3,4 2 : 1,3 2 : 1,3,4

3 : 1,2,4 3 : 1,2,4 3 : 1

4 : 2,4 4 : 3 4 : 2,3

5 : -

(a) (b) (c)

45

Contoh soal:

Tentukan matrik adjacency dan incidency untuk graf tidak berarah dan grah berarah dibawah ini:

1. e 5

V1 e2 V5

e 6

e 1 e8 V4

V2 V3

46

e 3

e 4

e 7

2. e 3

V2 V1 e1

e 5 e4 e2 V3

e6

V4 e7 V5

e 8

3. V1

e 1 e9

V2 V3

e 3 e7

V4 e5 V5

ISOMORPHIC GRAPH (Graf Isomorfik)

Definisi : dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu

antara simpul-simpul keduanya dan antara sisi-sisi keduanya sedemikian hingga jika sisi e

bersisian dengan simpul u dan v di G1, maka sisi e’ yang berkoresponden di G2 juga harus

bersisian dengan simpul u’ dan v’di G2.

3 4 3 v w

44

47

4

e 2

e4 e10

e6 e8

1 2 x y

1 2

(a) G1 (b) G2 (c)G3

Gb. G1 isomorfik dengan G2 tapi G1 tidak isomorfik dengan G3

4 3 8

8 888

7 5

1 3

1 2

2

(d)G4 (e) G5

Untuk graf berarah isomorfiknya:

1 2 1

2 3

3 4

4

(e)G6 (f) G7

1 2 5 1

48

8 5

7 4

4

6

3 2 4

3 5

5

(g)G8

(h) G9

Contoh Soal:

Buatlah graf isomorfik dari gambar graf tak berarah dibawah ini:

1.

G H

49

K L

M N

2. I

I J

Buatlah graf isomorfik untuk graf berarah dibawah ini:

1 A B

2 3 C D

4 5 E F

(3) (4)

GRAF PLANAR & GRAF BIDANG

Definisi : graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling

memotong (bersilangan) disebut graf planar, jika tidak maka disebut graf tidak planar.

(a) (b)

50

Representasi graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan

disebut graf bidang (plane graph).

(a) (b) (c)

Gb. Lima buah graf planar. (b), (c) dan (e) adalah graf bidang.

(d) (f)

Definisi graf tidak planar: sebuah graf adalah tidak planar jika dan hanya jika ia memuat

semua sub-graf homomorfis K3,3 atau K5.

Latihan Soal

Ubahlah graf dibawah ini menjadi graf planar:

A B C G H

D E F I J K L

(1) (2)

51

PEMETAAN & REGION

Sisi-sisi pada graf bidang membagi bidang datar menjadi beberapa wilayah (region) atau muka

(face). Jumlah wilayah pada graf bidang dapat dihitung dengan mudah (termasuk wilayah di

luarnya).

A B C D

R6

G F E

Gb. Graf planar yang terdiri dari 6 wilayah

52

R2 R3 R4

R1 R5

Definisi derajat dari sebuah region : panjang dari path tertutup yang membatasi region.

Derajat dari region r dinyatakan dengan deg (r). Jumlah derajat region dari sebuah pemetaan =

dua kali jumlah sisi (egde) di graf.

Contoh diatas maka:

Deg(r1) = 3, deg (r2) = 3, deg (r3) = 3, deg (r4) = 3, deg(r5) = 3, deg (r6) = 7

Jumlah derajat adalah = 3 + 3 + 3 + 3 + 3 + 7 = 22

Cycle atau path tertutup yang membatasi region:

r 1 = (A,F,G,A)(cycle),r2 = (A,B,F,A)(cycle), r3 = (B,C,F,B)(cycle)

r 4 = (C,D,E,C)(cycle) r5 = (C,E,F,C)(cycle), r6 = (A,B,C,D,E,F,G,A)(cycle)

r 5

r 4 C

r 3

A B B F E

r 1

D

Deg(r1) = 3, deg(r2) = 3, deg(r3) = 5, deg(r4) = 4, deg(r5) = 3

Cycle atau path tertutup yang membatasi region:

r 1 = (A,B,D,A) (cycle) r4 = (A,E,C,B,A) (cycle)

53

r 2

r 2 = (B,C,D,B) (cycle) r5 = (A,E,D,A) (cycle)

r 3 = (C,E,F,E,D,C) (path tertutup)

Contoh Soal:

1. A

r 3

B D C

E

A B C

2. E

r 4

F G H

54

r 2

r 1

r 1

r 2

D r 3

3. A B C

D

E r 3 F

r 4

r 5

RUMUS EULER

Jumlah verteks (v) pada graf planar sederhana juga dapat dihitung dengan rumus euler sebagai

berikut :

atau

Dalam hal ini :

e = jumlah sisi; v = jumlah simpul; r = region/wilayah

55

v – e + r = 2 r = e – v + 2

r 1 r 2

Maka v = 12, e = 17, r = 7 dan 12 – 17 + 7 = 2

Maka v = 3, e = 6, r = 5 dan 3 – 6 + 5 = 2

Contoh soal:

Tentukan jumlah vertex, edge dan region dari setiap pemetaan pada gambar graf dibawah ini:

1.

2.

56

3.

TEOREMA KURATOWSKI

Dalam literature tentang graf, dikenal dua buah graf tidak planar yang khusus yaitu graf

kuratowski, Kasimir Kuratowski matematikawan Polandia, menemukan sifatnya yang unik

[DEO 74].

1. Graf kuratowski pertama, yaitu graf lengkap yang mempunyai lima buah simpul (K5)

adalah graf tidak planar.

2. Graf kuratowski kedua, yaitu graf terhubung teratur dengan 6 buah simpul dan 9 sisi

(K3,3) adalah graf tidak planar.

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.

57

4. Graf kuratowski pertama adalah tidak planar dengan jumlah simpul minimum, dan graf

kuratowski kedua adalah graf tidak planar dengan jumlah sisi minimum. Keduanya

adalah garf tidak planar paling sederhana.

Teorema Kuratowski graf G adalah tidak planar jika dan hanya jika ia mengandung upgraf

yang isomorfik dengan K5 atau K3,3 atau homeomorfik (homeomorphic) dengan salah satu dari

keduanya.

A B C

F E D

G G1

LINTASAN DAN SIRKUIT EULER

Definisi Lintasan Euler: lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.

Bila lintasan tersebut kembali ke simpul asal, membentuk lintasan tertutup (sirkuit), maka

lintasan tertutup itu dinamakan Sirkuit Euler, jadi Sirkuit Euler adalah sirkuit yang melewati

masing-masing sisi tepat satu kali.

Graf yang mempunyai sirkuit euler disebut graf euler (eulerian graph). Graf yang mempunyai

lintasan euler dinamakan semi euler (semi eulerian graph).

Graf terhubung tak berarah G adalah graf euler (memiliki sirkuit euler) jika dan hanya jika

setiap simpul didalam graf tersebut berderajat genap.

Jika ingin membuat graf yang mempunyai sirkuit euler, maka harus dipenuhi kondisi

berikut:

1. graf tersebut harus terhubung, dan

2. semua simpul pada graf berderajat genap

58

Graf terhubung tak berarah G adalah graf semi euler (memiliki lintasan euler) jika dan hanya

jika di dalam graf tersebut terdapat tepat dua simpul berderajat ganjil.

Catatan : bahwa graf yang memiliki sirkuit euler pasti mempunyai lintasan euler tapi tidak

sebaliknya.

Jika kita ingin membuat graf yang mempunyai lintasan euler (tanpa membentuk sirkuit),

maka harus dipenuhi kondisi sbb:

1. graf tersebut graf terhubung

2. graf memiliki tepat dua buah simpul berderajat ganjil

graf terhubung berarah G memiliki sirkuit euler jika dan hanya jika G terhubung dan setiap

simpul memiliki derajat masuk dan keluar sama. G memiliki lintasan euler jika dan hanya jika

G terhubung dan setiap simpul memiliki derajat masuk dan keluar sama kecuali dua simpul :

1. yang pertama memiliki derajat keluar satu lebih besar dari derajat masuk,

2. yang kedua memiliki derajat masuk satu lebih besar dari derajat keluar.

Contoh:

2 1 1 2

4

3 4 5 6

(a) (b)

1 2 a b f

4 5 c d e

59

3

3

(c) (d)

Lintasan euler untuk gb.(a) = 3,1,2.3.1 graf (a) & (b) mempunyai lintasan euler

Lintasan euler untuk gb.(b) = 1,2,4,6,2,3,6,5,1,3 (semi eulerian graph)

a d c d c

b

f g

c

a b a b

e d

(a) (b) (c)

(a) Graf berarah yang mempunyai sirkuit euler (a,g,c,b,g,e,d,f,a)(b) Graf berarah yang memunyai lintasan euler (d,a,b,d,c,b)(c) Graf berarah yang tidak memiliki lintasan dan sirkut euler.

LINTASAN DAN SIRKUIT HAMILTON

Definisi Lintasan Hamilton ialah lintasan yang memulai setiap simpul di dalam graf tepat satu kali. Bila lintasan itu kembali ke simpul asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup dinamakan Sirkuit Hamilton. Dengan kata lain, Sirkuit Hamilton ialah sirkuit yang memulai tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.

Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang memiliki lintasan Hamilton disebut graf semi Hamilton.

Contoh:

1 2 1 2 1 2

4 3 4 3 4 3

60

(a) (b) (c)

(a) Graf yang memiliki lintasan Hamilton (3,2,1,4)(b) Graf yang memiliki sirkuit Hamilton (1,2,3,4,1)(c) Graf yang tidak memiliki lintasan dan sirkuit Hamilton

LINTASAN TERPENDEK (SHORTEST PATH)

Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot (weighted graph) yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Kata “terpendek” jangan selalu diartikan secara fisik sebagai panjang minimum. Namun, secara umum “terpendek” berarti meminimisasi bobot pada suatu lintasan di dalam graf.

Contoh: 40

1 50 2 10 5

20 10 40 15 20 35

30

3 15 4 3 6

Simpul asal Simpul tujuan Lintasan terpendek jarak

61

1 3 1,3 101 4 1,3,4 251 2 1,3,4,2 451 5 1,5 451 6 Tidak ada -

Kalau ditinjau graf berarah pada contoh diatas dengan menggunakan matrik adjency M sebagai berikut:

j =1 2 3 4 5 6

1

2

3

4

5

6

Perhitungan lintasan terpendek dari simpul awal a = 1 ke semua simpul lainnya ditabulasikan sebagai berikut:

Simpul yang Lintasan S D

Dipilih 1 2 3 4 5 6 1 2 3 4 5 6

Initial - - 0 0 0 0 0 0 0 50 10 40 45

(1,2) (1,3) (1,4) (1,5) (1,6)

1 1 1 1 0 0 0 0 0 50 10 40 45

(1,2) (1,3) (1,4) (1,5) (1,6)

2 3 1,3 1 0 1 0 0 0 50 10 25 45

62

0 50 10 40 450 15 10

20 0 15

20 0 35

30 0

3 0

(1,2) (1,3) (1,3,4) (1,5) (1,6)

3 4 1,3,4 1 0 1 1 0 0 45 10 25 45

(1,3,4,2) (1,3) (1,3,4) (1,5) (1,6)

4 2 1,3,4,2 1 1 1 1 0 0 45 10 25 45

(1,3,4,2) (1,3) (1,3,4) (1,5) (1,6)

5 5 1,5 1 1 1 1 1 0 45 10 25 45

(1,3,4,2) (1,3) (1,3,4) (1,5) (1,6)

Keterangan: angka-angka di dalam kurung menyatakan lintasan terpendek dari 1 ke simpul tersebut)

Jadi lintasan terpendek dari:

1 ke 3 adalah 1,3 dengan panjang = 10

1 ke 4 adalah 1,3,4 dengan panjang = 25

1 ke 2 adalah 1,3,4,2 dengan panjang = 45

1 ke 5 adalah 1,5 dengan panjang = 45

1 ke 6 tidak ada lintasan

Contoh: Boston(5)

1500

Chicago(4)

Denver(3) 1200 250

800 1000

San Fransisco(2) 1000 New York(6)

300 1400 900

63

Los Angles(1) 1700 1000 Miami(7)

New Orleans(8)

Carilah jarak terpendek dari beberapa kota di Amerika!

64