Graph. Matematika Informatika 4. Onggo

Graph Matematika Informatika 4 Onggo Wiryawan @OnggoWr

Definisi • Graph adalah struktur diskrit yang mengandung vertex dan edge yang menghubungkan vertex-vertex tersebut.

vertex

edge

Onggo Wiryawan - Pengantar Teori Graph

2

Jenis-jenis Graph •

Definisi 1: Suatu graph simple G(V,E) mengandung V, sebuah himpunan tak-kosong yang berisi vertexvertex, dan E, sebuah himpunan berisi pasangan berurut dari anggota V yang berbeda, disebut dengan edge.


3


Contoh: a

e1

p

q e1

b e2 e2

Graph G V = {a, b, c} E = {e1, e2}

e3

t e4

c

r

Graph H s


V = {p, q, r, s, t} E = {e1, e2, e3, e4} 4


Contoh:

Multiple / parallel edges


6


Contoh :

Loop


7

Istilah dalam Graph •

Definisi 4: Dua vertex u dan v dalam suatu graph G disebut beradjacent (atau bertetangga) di G jika {u, v} adalah suatu edge pada G. Jika e = {u, v}, maka edge e disebut incident dengan vertex u dan v. Edge e juga disebut menghubungkan u dan v. Vertex u dan v disebut endpoints dari edge {u, v}.


8


Definisi 5: Degree dari suatu vertex pada sebuah graph adalah banyaknya edge yang incident dengan vertex tersebut. Degree dari vertex v dinotasikan dengan deg(v).


9


Contoh:

a deg(a) = 2 deg(b) = 4 deg(c) = 4

b

c

d

f

e

g

deg(d) = 1 deg(e) = 3 deg(f) = 4

deg(g) = 0


10


Teorema 1 (The Handshaking Theorem): Misalkan G = (V,E) adalah suatu graph dengan edge sebanyak e, maka

2e   deg(v) vV

yaitu jumlah dari degree setiap vertex sama dengan dua kali banyaknya edge pada graph tersebut. Bukti: Karena setiap edge menghubungkan 2 vertex. Onggo Wiryawan - Pengantar Teori Graph

11


Contoh : Berapa banyak edge yang terdapat pada suatu graph dengan 10 vertex yang masing-masing berdegree 6 ? Jawab: karena jumlah dari degree vertex sebesar 6•10 = 60, artinya 2e = 60. e = 30. Sehingga, banyaknya edge pada graph tersebut adalah 30 edge. Onggo Wiryawan - Pengantar Teori Graph

12

Istilah dalam Graph Teorema 2: Suatu graph (tidak berarah) memiliki sejumlah genap vertex yang berdegree ganjil. Bukti: •

dari teorema 1, 2𝑒 =

deg⁡(𝑣) 𝑣∈𝑉

2𝑒 =

deg⁡(𝑣) + 𝑣∈𝑉1

deg⁡(𝑣) 𝑣∈𝑉2

genap = [ganjil+...+ganjil] + [genap+...+genap] agar persamaan ini berlaku, maka [ganjil+...+ganjil] harus ada sebanyak genap suku. Onggo Wiryawan - Pengantar Teori Graph

13

Beberapa Graph Simple Khusus 1.

Graph Complete [Kn] adalah graph simple yang mengandung tepat satu edge untuk setiap pasang vertex yang berbeda.

? K1

K2

K3 Onggo Wiryawan - Pengantar Teori Graph

K4

K5 14


Cycles [Cn, n  3] graph cycles Cn, mengandung n vertex v1, v2, ..., vn dan edge {v1, v2}, {v2, v3}, ... , {vn-1, vn}, {vn, v1}.

C3

C4 Onggo Wiryawan - Pengantar Teori Graph

15


Wheels [Wn, n  3] graph wheel Wn, diperoleh dengan menambahkan sebuah vertex pada graph cycle Cn lalu menghubungkan vertex baru ini ke setiap vertex yang ada pada Cn, dengan menambahkan edge-edge baru.

W C33

W C4


16


Bipartite Graph suatu graph simple G = (V,E) disebut bipartite jika himpunan vertex V dapat dipartisi menjadi dua himpunan takkosong yang saling lepas V1 dan V2 sedemikian hingga setiap edge pada graph menghubungkan sebuah vertex di V1 dan sebuah vertex di V2 (tapi tidak ada edge yang di G yang menghubungkan setiap pasang vertex di masingmasing V1 atau di V2).


17

Beberapa Graph Simple Khusus •

Contoh Apakah C6 bipartite? Ternyata, C6 merupakan suatu graph bipartite.

C6

C6


18


Exercise Are the graphs G and H bipartite?

G

H Onggo Wiryawan - Pengantar Teori Graph

19


Complete Bipartite Graph Graph complete bipartite Km,n adalah graph yang himpunan semua vertexnya terpartisi ke dalam dua subset. Sehingga ada sebuah edge yang menghubungkan dua vertex jika dan hanya jika vertex pertama terdapat di suatu subset dan vertex kedua di subset lainnya.


20


Contoh Beberapa graph complete bipartite.

K2,3

K3,3 Onggo Wiryawan - Pengantar Teori Graph

21

Modifikasi Graph •

Definisi 1: Suatu subgraph dari sebuah graph G = (V,E) adalah sebuah graph H = (W,F) dengan W  V dan F  E. Contoh:

K4

Sebuah subgraph dari K4 Onggo Wiryawan - Pengantar Teori Graph

22

Modifikasi Graph •

Definisi 2: Gabungan dari dua graph simple G1 = (V1,E1) dan G2 = (V2,E2) merupakan suatu simple graph dengan himpunan vertex V1 V2 dan himpunan edge E1  E2. Gabungan dari graph G1 dan G2 dinotasikan dengan G1  G2


23

Modifikasi Graph Contoh

• b

c

b

c

a

d

a

d

G1

b

a

c

G G

G2

e

e

d

Onggo Wiryawan - Pengantar Teori Graph 1 2

24

Representasi Graph dan Isomorfisma Graph


25

Daftar Adjacency •

Contoh Gunakan daftar adjacency untuk merepresentasikan simple graph G1.

b

c

a

d

Vertex

Beradjacent dengan

a

b

b c d e

a, c b, d, e c, e c, d Onggo Wiryawan - Pengantar Teori Graph

G1

e

26

Matriks Adjacency •

Definisi 1: Jika A = [aij] merupakan suatu matrix adjacency dari graph G, maka aij

=1 =0

jika {vi, vj} adalah suatu edge di G lainnya


27

Matriks Adjacency Contoh Gunakan matriks adjacency untuk merepresentasikan graph G1.

•

a b c d e

a 0 1  0  0  0

b 1 0 1 0 0

c 0 1 0 1 1

d 0 0 1 0 1

e 0 0  1  1 0 

b

c

a

d


G1

e

28

Matriks Incidence •

Definisi 2: Jika M = [mij] merupakan matriks incidence dari graph G, maka mij

=1 =0

jika edge ej berincident dengan vertex vi lainnya


29

Matriks Incidence Contoh Gunakan matriks incidence untuk merepresentasikan graph G1.

•

a b c d e

e1 e2 e3 e4 e5 1 0 0 0 0 1 1 0 0 0   0 1 1 1 0    0 0 1 0 1     0 0 0 1 1 

b

e2

e1 a


c e4 e3

G1

e e5

d

30

Path & Circuit • Definisi 1 Sebuah path sepanjang n dari u ke v, pada suatu graph adalah suatu barisan edge e1, …, en pada graph sedemikian hingga f(e1) = {x0,x1}, f(e2) = {x1,x2}, … , f(en) = {xn-1,xn}, dengan x0 = u dan xn = v.


31

Path & Circuit Catatan • Suatu path disebut sebagai circuit jika dimulai dan diakhiri pada vertex yang sama, yaitu jika u = v. • Suatu path atau circuit disebut simple jika tidak mengandung edge yang sama lebih dari satu kali. • Suatu path atau circuit disebut melewati or melintasi vertex-vertex x1, x2, …, xn-1. Onggo Wiryawan - Pengantar Teori Graph

32

Path & Circuit Contoh

a

b

c

d

e

f

G

• a, d, c, f, e merupakan suatu simple path dengan panjang 4 sebab {a, d}, {d, c}, {c, f}, dan {f, e} semuanya merupakan edge. • d, e, c, a bukan suatu path, sebab {e, c} bukan edge. • b, c, f, e, b merupakan suatu circuit dengan panjang 4 sebab {b, c}, {c, f}, {f, e}, dan {e, b} adalah edgenya. Onggo Wiryawan - Pengantar Teori Graph

33

Graph Terhubung • Definisi 2 Suatu graph disebut terhubung jika terdapat suatu path antara setiap pasang vertex yang berbeda pada graph tersebut. • Teorema 1

Terdapat suatu simple path di antara setiap pasang vertex yang berbeda dari suatu graph yang terhubung. Onggo Wiryawan - Pengantar Teori Graph

34

Graph Terhubung Catatan • Penghapusan sebuah vertex yang disebut cut vertex (titik artikulasi) dari suatu graph terhubung akan menghasilkan sebuah subgraph dengan komponen terhubung yang lebih banyak dari graph aslinya. • Penghapusan suatu edge yang disebut cut edge ( jembatan) dari suatu graph terhubung menghasilkan sebuah subgraph dengan komponen terhubung yang lebih banyak dari graph aslinya. Onggo Wiryawan - Pengantar Teori Graph

35

Graph Terhubung Contoh: a

d

f

g

b

c

e

h

G

Cut vertex dari graph G adalah b, c dan e. Cut edge dari graph G adalah {a,b} dan {c,e}. Onggo Wiryawan - Pengantar Teori Graph

36

Isomorfisme Graph • Definisi Simple graph G1 = (V1,E1) dan G2 = (V2, E2) disebut isomorfis jika terdapat suatu fungsi bijektif f dari V1 ke V2 dengan sifat bahwa a dan b beradjacent di G1 jika dan hanya jika f(a) dan f(b) beradjacent di G2, untuk setiap a dan b di V1. Fungsi f yang seperti ini disebut suatu isomorfisma. Onggo Wiryawan - Pengantar Teori Graph

37

Isomorfisme Graph Contoh • Tunjukkan bahwa graph G(V, E) dan H(W,F) isomorfis. u1

u2

v1

v2

u3

u4

v3

v4

G


H

38

Isomorfisme Graph • Jawab Fungsi F dengan: f(u1) = v1, f(u2) = v4, f(u3) = v3, f(u4) = v2 adalah suatu pemetaan bijektif dari V ke W. u1

u2

v1

v2

u3

u4

v3

v4

G


H

39

Isomorfisme Graph Contoh • Tunjukkan bahwa graph G(V, E) dan H(W,F) tidak isomorfis. b

b

a

c

a

c

e

d

e

d

G


H

40

Isomorfisme Graph • Jawab Perhatikan banyaknya edge & vertex. Perhatikan degree dari setiap vertex. b

b

a

c

a

c

e

d

e

d

G


H

41

Graph. Matematika Informatika 4. Onggo

Recommend Documents