M t tik Di k it 2Matematika Diskrit 2

Teori GraphTeori Graph

Teori Graph 1

K l hir T ri Gr phKelahiran Teori GraphMasalah Jembatan Konigsberg : g g

Mulai dan berakhir pada tempat yang sama, bagaimana caranya untuk melalui setiap jembatan tepat satu kali ?

1736 L h d E l1736: Leonhard EulerBasel, 1707-St. Petersburg, 1786Mampu mengungkap misteri Jembatan Konigsberg

Teori Graph 2

Mampu mengungkap misteri Jembatan Konigsberg

Pr bl d M d l Gr phProblem dan Model GraphData

MASALAHAn

al

MODEL IMPLEMENTASI

lisis

PROGRAMAn

ali

ALGORITMA SOLUSI YANGDIHARAPKAN

sis

Teori Graph 3

Pr bl 1Problem 1Setiap minggu sekali, seorang petugasSetiap minggu sekali, seorang petugas kantor telepon berkeliling untuk mengumpulkan koin pada telepon umum yang dipasang diberbagai tempat. Berangkat dari kantornya, ia mendatangi satu demi satu t l t b t d khi k b litelepon umum tersebut, dan akhirnya kembali ke kantor lagi. Problem yang muncul adalah petugas tersebut menginginkan suatu rutepetugas tersebut menginginkan suatu rute perjalanan dengan waktu minimal ?

Teori Graph 4

Pr bl 2Problem 2Pada suatu persimpangan jalan yang ramai p p g j y gakan dipasang lampu lalu lintas (TL). Telah diatur bahwa jalan A, C, D, E, dan F satu arah serta jalan B adalah 2 arah Perjalanan yangserta jalan B adalah 2 arah. Perjalanan yang diperbolehkan adalah :

A B A C A E B C B ED C D E F B F C F E

Problemnya adalah bagaimana menentukan l TL d j l h f i i l d dpola TL dengan jumlah fase minimal,dan pada

setiap fase tidak ada perjalanan yang saling melintas ?

Teori Graph 5

melintas ?

Pr bl 3Problem 3Rute perjalanan dari kota A ke P dapatRute perjalanan dari kota A ke P dapat dilakukan dengan berbagai macam alternatif Dari sekian banyak alternatifalternatif. Dari sekian banyak alternatif yang ada maka tentukanlah rute yang paling minimal untuk ditempuhpaling minimal untuk ditempuh (misalkan minimal dalam hal jarak tempuh/waktu tempuh) ?tempuh/waktu tempuh) ?

Teori Graph 6

M d l Gr phModel GraphJika kita lakukan analisis terhadap ketiga p gproblem tadi, maka kita akan buatkan model persoalannya ke dalam model Graph.P bl 1 d d l G h dik l dProblem 1 pada model Graph dikenal dengan problem Travelling Salesman.Problem 2 pada model Graph dikenal denganProblem 2 pada model Graph dikenal dengan problem Coloring Graph (pewarnaan Graph).Problem 3 pada model Graph dikenal dengan problem Shortest Path.

Teori Graph 7

P d h lPendahuluanDefinisi 1 :Definisi 1 :

Suatu Graph G = (V,E) adalah koleksi atau pasangan dari dua himpunan V (tidak kosong) p g p ( g)dan E dengan

V = V(G) = himpunan verteks atau simpul atau node. E = E(G) = himpunan edge atau ruas atau sisi.

Banyaknya verteks disebut orderBanyaknya edge disebut size (ukuran)

Teori Graph 8

P d h l (L j t )Pendahuluan (Lanjutan)Contoh 1 :Contoh 1 :

V = {s, u, v, w, x, y, z}E = {(x s) (x v)E = {(x,s), (x,v)1, (x,v)2, (x,u), (v,w), (s,v), (s,u), (s,w), (s,y),(s,v), (s,u), (s,w), (s,y), (w,y), (u,y), (u,z),(y,z)}

Teori Graph 9

EdEdgeEdge merupakan pasangan tak terurut dariEdge merupakan pasangan tak terurut dari simpul. Misalkan edge e = (v,w) = (w,v).Edge e dikatakan incident pada v dan w.g pVerteks terpencil (terisolasi) adalah suatu verteks tanpa edge incident.p g

p

Teori Graph 10

Ed KhEdge KhususEdge ParalelEdge Paralel

Dua edge atau lebih yang mempunyai kedua erteks j ng angverteks ujung yang

sama. Graph disamping : edge (a b) merupakan edge(a,b) merupakan edge paralel atau edge sejajar.

Loop (self-loops)Suatu edge yang kedua verteks ujungnya sama.

Graph disamping, edge

Teori Graph 11

p p g, g(d,d) self-loops.

Gr ph KhGraph Khusus

Simple graph (Graph sederhana)

Suatu graph yang tidakSuatu graph yang tidak memiliki self-loops dan ruas sejajar.

W i ht d hWeighted graph (Graph berlabel / berbobot)berbobot)

Suatu graph yang setiap ruasnya dikaitkan dengan besaran tertentu (“bobot”)

Teori Graph 12

besaran tertentu ( bobot ).

G h B h (Di h)Graph Berarah (Digraph)

G disebut graph berarah atau directed graph/ digraph jikagraph/ digraph jika setiap ruas merupakan pasangan terurut daripasangan terurut dari simpul. (dpl. Setiap ruasnya memiliki arah).

Teori Graph 13

G h B h (Di h)Graph Berarah (Digraph)

Definisi:Jika (u,v) adalah edge dari graph berarah G, u dik t k dj t k d dik t kdikatakan adjacent ke v dan v dikatakan adjacent dari u. Vertex u dikatakan sebagai verteks inisial dariVertex u dikatakan sebagai verteks inisial dari (u,v) dan v dikatakan sebagai verteks terminal atau verteks akhir (u v)atau verteks akhir (u,v).verteks inisial dan verteks terminal dari sebuah loop adalah sama

Teori Graph 14

loop adalah sama

D r j t V rt kDerajat VerteksDerajat dari simpul v,Derajat dari simpul v, dinotasikan dgn δ(v),adalah banyaknya ruas yang melalui vContoh :

δ(a) = 4, δ(b) = 3, δ(c) = 4, δ(d) = 6, ( ) 4 (f) 4δ(e) = 4, δ(f) = 4, δ(g) = 3.

Teori Graph 15

D r j t p d Gr phDerajat pada GraphTeorema (The Handshaking Theorem):Teorema (The Handshaking Theorem):

jika G suatu graph tidak berarah dengan m edge dan n verteks maka jumlah derajat semua j jverteks adalah 2m.

nn

Σ δ(vi) = 2mi = 1i 1

jumlah dari derajat semua verteks pada graph tidak berarah adalah genap

Teori Graph 16

graph tidak berarah adalah genap.

D r j t p d Gr phDerajat pada Graph

Teorema : Sebuah graph tidak berarah G memilikiSebuah graph tidak berarah G memiliki sejumlah genap vertek berderajat ganjil

Teori Graph 17

D r j t p d Gr phDerajat pada GraphDefinisi:Definisi:

Sebuah graph berarah G memiliki derajat masuk dari sebuah verteks (in-degree of a vertex) v, ( g ) ,dinotasikan sebagai δ-(v), menyatakan banyaknya edge dengan v sebagai verteks terminal. Derajat keluar dari sebuah verteks (out-degree of a vertex) v, dinotasikan sebagai δ+(v) menyatakan banyaknya edge dengan vδ+(v), menyatakan banyaknya edge dengan v sebagai verteks inisial.

Teori Graph 18

G h B h (Di h)Graph Berarah (Digraph)

δ-(a) = 1, δ+(a) = 2, δ-(b) = 2, δ+(b) = 1,δ-(c) = 2, δ+(c) = 2,δ-(d) = 3, δ+(d) = 2,δ-(e) = 1, δ+(e) = 2,δ-(f) = 1, δ+(f) = 1

Teori Graph 19

D r j t p d Gr phDerajat pada Graph

Teorema : Misalkan G = (V E) adalah graph berarah maka:Misalkan G = (V,E) adalah graph berarah maka:

Evv ∑∑ +− == )()( δδ EvvVvVv∑∑∈∈

)()( δδ

Teori Graph 20

Gr ph L k p KGraph Lengkap K n

Misalkan n > 3Graph Lengkap (complete

h) K d l h hgraph) Kn adalah graph dengan n simpul dan setiap pasang simpulnya terhubung p g p y goleh satu ruas. Derajat setiap vertex sama Contoh di sampingContoh di samping merupakan Graph lengkap K5

Teori Graph 21

Gr ph Bip rti iGraph BipartisiGraph bipartisi G adalah suatu p pgraph sedemikian sehingga berlaku

V(G) V(G ) V(G )V(G) = V(G1) ∪ V(G2)|V(G1)| = m, |V(G2)| = nV(G ) ∩V(G ) = ∅V(G1) ∩V(G2) = ∅Tidak terdapat edge antara sembarang verteks pada subset V(Gk) yang sama; k = 1,2.

Teori Graph 22

C pl t bip rtit r ph KComplete bipartite graph Km,n

Suatu graph bipartisi adalah graph bipartisi lengkap (Complete bipartite graph)Km,n jika setiap simpul pada V(G ) terhubung denganV(G1) terhubung dengan simpul pada V(G2) dan sebaliknyasebaliknya, |V(G1)| = m |V(G )| = n

Teori Graph 23

|V(G2)| = n

Gr ph T rh bGraph Terhubung

Suatu Graph dikatakan terhubung (Connected) jika setiap pasang dari vertekssetiap pasang dari verteks dapat dilalui dengan suatu jalur.

Setiap subgraph terhubung dari suatu graph takdari suatu graph tak terhubung G disebut component dari G

Teori Graph 24

J l r(P th) d C lJalur(Path) dan Cycle

S t J l (P th) d jSuatu Jalur (Path) dengan panjang nadalah barisan dari n + 1 verteks dan n d b tedge secara berurutan.

(v0, e1 , v1, e2 , v2, e3 , …, vn-1, en , vn)

Suatu Cycle adalah jalur dengan verteksSuatu Cycle adalah jalur dengan verteks awal dan verteks akhirnya sama.

Teori Graph 25

Jalur (Path) dan Cycle (Lanjutan)Jalur (Path) dan Cycle (Lanjutan)Contoh :

Diketahui suatu Graph G :1 2 3e1 e2

456

e3

e4e5

e6 e7e8 e9

Jalur dari verteks 1 ke 5 : 1, 5 atau 1, 2, 5 atau 1, 2, 3, 4, 5 atau 1, 2, 3, 5, atau 1 6 5

56

1, 6, 5Cycle dgn panjang 3 : 1, 2, 5, 1 atau 2, 3, 5, 2 Cycle dgn panjang 6 : 1 2 3 4 5 6 1

Teori Graph 26

Cycle dgn panjang 6 : 1, 2, 3, 4, 5, 6, 1

S b r phSubgraphDefinisi :Definisi :

Misal G=(V,E) suatu Graph, G’ =(V’,E’) disebut subgraph dari G jika :d sebut subg ap da G j a

V’ ⊆ V dan E’ ⊆ E

Contoh:Diketahui graph G sebagai berikut :

a

besubgraph

Teori Graph 27c

P rj l E l rPerjalanan EulerSebuah perjalanan Euler (Euler cycle)Sebuah perjalanan Euler (Euler cycle)pada graph G adalah sebuah cycle sederhana yang melalui setiap edge di G hanya sekaliG hanya sekali.Problem jembatan Königsberg:

Apakah memungkinkan untuk memulai dan mengakhiri suatu perjalanan dari titik yangmengakhiri suatu perjalanan dari titik yang sama melalui ke 7 jembatan hanya sekali?

Problem dapat dinyatakan dengan sebuah graphsebuah graph Edge menyatakan jembatan dan setiap verteks menyatakan daerah (region)

Teori Graph 28

(region).

Gr ph E l rGraph EulerSebuah graph G adalah graph Euler jika g p g p jmemiliki Euler cycle.

Teorema: G adalah Graph Euler jika dan hanya jika G terhubung dan semua vertex memiliki derajat genap.derajat genap.Graph terhubung merepresentasikan problem jembatan Königsberg. Graph tersebut bukan Graph Euler. Berarti problem jembatan Königsberg

Teori Graph 29

tidak memiliki solusi.