Representasi Graph Isomorfisme sub-bab 8.3
Representasi graph: Adjacency list
1. Adjacency list 2. Adjacency matrix 3. Incidence matrix
1: 2
tiap vertex v
2: 1, 3, 4
di-link dengan
3: 2, 4, 5
semua vertex yang
4: 2, 3, 5
adjacent dengan v
5: 3, 4
Contoh: undirected graph 1
Adjacency matrix
Incidence matrix
e1 e2
2
3 e4
e3
e5 4
e6
0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0
5
baris : vertex kolom: vertex
1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 1
baris: vertex kolom: edge
Representasi graph: Adjacency list
1. Adjacency list 2. Adjacency matrix
1: --
tiap vertex v
2: 1
di-link dengan
3: 2, 4
semua vertex yang
4: 2, 5
adjacent to v
5: 3
Contoh: directed graph
Adjacency matrix
1 e1
0 0 0 0 0 e2
2
3 e4
e3
e5 4
e6
5
1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0
baris : vertex kolom: vertex
Isomorfisme: G1 = (V1, E1) dan G2 = (V2, E2) disebut isomorfik jika ada
f : V1 V2
(f disebut isomorfisme)
Fungsi f adalah 1-1 correspondence jika dan hanya jika
vertex a adjacent to vertex b di G1 vertex f(a) adjacent to vertex f(b) di G2
Contoh: isomorfisme graph G = (V1, E1) a
b
c
V1
graph H = (V2, E2)
d
f
p
q
r
s
V2
a
p = f(a)
(a, b) (p, s)
b
s = f(b)
(a, c) (p, r)
c
r = f(c)
(b, d) (s, q)
d
q = f(d)
(c, d) (r, q)
s
p
r
q
Graph G
Graph H u2
u1
v1
v3
e3
e2
e5 u5
v2
u6
v6
e1
u4
u3
e6
e4 e7
v5
v4
e5
v6
v3 e3
e4
v1
e2
v2
e6
e1 v5
e7
v4
Graph G
Graph H u2
u1 u5
u6
u4
v3
v1
v2
u3
adjacency matrix G u1
0 1 0 1 0 0
u2
1 0 1 0 0 1
u3
0 1 0 1 0 0
u4
1 0 1 0 1 0
u5
0 0 0 1 0 1
u6
0 1 0 0 1 0
v6
v3
v6
v1
v4
v5
v2
v5
v4
adjacency matrix H v6
v6 v3 v4 v5 v1 v2
v3 v4 v5 v1 v2
0 1 0
1 0 1
0 1 0
1 0 1
0 0 0
0 1 0
1 0 0
0 0 1
1 0 0
0 1 0
1 0 1
0 1 0
Invariance dari dua simple graphs yang isomorfik: 1. Banyaknya vertex dalam kedua graphs harus sama 2. Banyaknya edge dalam kedua graphs harus sama 3. Derajat (degree) dari vertex v = derajat dari vertex f(v) di sini f adalah isomorfisme (fungsi) kedua graphs tersebut
Keterhubungan (connectivity) Sub-bab 8.4
Graph G = (V, E) di mana V = {x0, x1, x2, … , xn } dan E = { e1, e2, …, en }
Lintasan (path): Yang disebut lintasan dalam graph G adalah e1, e2, …, en di mana f(e1) = {x0, x1}, f(e2) = {x1, x2}, …, f(en) = {xn-1, xn } x0
x1
xn-1
e1
Circuit (cycle) :
…..…
xn
en
lintasan {x0, x1}, {x1, x2}, …, {xn-1, x0 } x1 x0
x2 xn-1
Catatan:
1. Lintasan / cycle melewati vertices x1, x2, …, xn-1 atau melakukan traversal sepanjang edges e1, e2, …, en
2. Panjang lintasan / cycle = n
3. Lintasan / cycle disebut simple jika tidak berisi suatu edge lebih dari satu kali
Connectivity: Undirected graph: antara setiap pasangan vertex terdapat suatu lintasan (path)
Directed graph: 1. Strong connection: ada lintasan antara vertex a dan vertex b, sebaliknya ada juga lintasan antara vertex b dan vertex a. 2. Weak connection: ada lintasan antara dua vertex dalam underlying undirected graph-nya.
Komponen sebuah graph: 1. Graph G = (V, E) tidak terhubung 2. Masing-masing subgraph yang terhubung disebut komponen dari graph G
Contoh:
a
b
c
e d
G1
f
G2
G = (V, E); V = { a, b, c, d, e, f } Ada 2 komponen G: G1 dan G2
Cut vertex: Sebuah vertex v dengan semua edges yang incident pada v dihapus dari sebuah graph G = (V, E) Hasilnya adalah graph G’ dengan komponen lebih banyak dari pada komponen graph G Maka v disebut cut vertex Bridge: Sebuah edge e dihapus dari sebuah graph G = (V, E) Hasilnya adalah graph G’ dengan komponen lebih banyak dari pada komponen graph G Maka e disebut bridge
Contoh: a
d
b
c
f
g
e
h
cut vertex: e a
d
b
c
f
g
h
Contoh: a
d
b
c
f
g
e
h
bridge: { c, e } a
d
f
g
b
c
e
h
Isomorfisme dan lintasan: Salah satu cara mendeteksi isomorfisme antara dua graphs adalah dengan memeriksa apakah kedua nya memiliki cycle dengan panjang berbeda.
Contoh: cycle-2 cycle-1
cycle-1
cycle-2
Graph G
Graph H
Invariance dua graphs yang isomorfik: 1. Banyaknya vertex dalam kedua graphs harus sama 2. Banyaknya edge dalam kedua graphs harus sama 3. Derajat (degree) dari vertex v = derajat dari vertex f(v) di sini f adalah isomorfisme (fungsi) kedua graphs tersebut 4. Jika dalam graphs terdapat cycle, maka panjang cycle yang bersesuaian dalam kedua graphs harus sama
Banyaknya lintasan dalam sebuah graph dapat ditentukan oleh adjacency matrix graph tersebut.
Artinya: Dalam matriks A : aij = 1 berarti ada 1 lintasan dengan panjang 1 (ada 1 edge) antara vertex-i dan vertex-j Dalam matriks A2 : aij = k berarti ada k lintasan dengan panjang 2 antara vertex-i dan vertex-j Dalam matriks A3 : aij = m berarti ada m lintasan dengan panjang 3 antara vertex-i dan vertex-j Demikian seterusnya.
Contoh: a
d
A2 =
b
c
2 0 0 2 0 2 2 0 0 2 2 0 2 0 0 2
A=
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
A3 =
0
4
4
0
4
0
0
4
4 0
0 4
0 4
4 0
Contoh: a
A=
b
d
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
c
ada 2 lintasan dari a ke a dengan panjang 2
A2 =
panjang lintasan
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
Lintasan dari a ke a dengan panjang 2: a-b-a, a-c-a Lintasan dari c ke b dengan panjang 2: c-d-b, c-a-b
=
2 0 0 2 0 2 2 0 0 2 2 0 2 0 0 2
Contoh: a
d
A3 =
A=
b
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
c
2 0 0 2 0 2 2 0 0 2 2 0 2 0 0 2
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
=
0
4
4
0
4
0
0
4
4 0
0 4
0 4
4 0
ada 4 lintasan dari a ke b dengan panjang 3: a-b-a-b
a-c-d-b
a-b-d-b
a-c-a-b
Tree/ Pohon • Tree/ Pohon adalah sebuah graph yang mempunyai n buah vertex, n – 1 edge dan tidak mempunyai cycle serta merupakan graph terhubung.
• Hubungan antara tree/pohon(T), titik(V), dan rusuk(E) dapat dinyatakan dengan E = V - T
Spanning Tree Sebuah pohon katakanlah T disebut spanning tree dari sebuah graph G, jika T adalah subgraph dari G yang mencakup semua titik graph G
v
G
T
Minimal Spanning Tree Sebuah pohon katakanlah T disebut Minimal spanning tree dari sebuah graph G, jika T adalah subgraph dari G yang mencakup semua titik graph G dan memiliki jumlah bobot/label minimal 4 12 d 8 gv
6 11 e 13 3 2 h
1 7 14 10
4 5 f 9 i
8 2
1 6
5
3
9
