M t Matematika tik Diskrit Di k it 2
Teori Graph Teori Graph
1
K l hir T Kelahiran Teori ri Gr Graph ph
Masalah Jembatan Konigsberg g g:
Mulai dan berakhir pada tempat yang sama, bagaimana caranya untuk melalui setiap jembatan tepat satu kali ?
1736 Leonhard 1736: L h d Euler E l
Teori Graph
Basel, 1707-St. Petersburg, 1786 Mampu mengungkap misteri Jembatan Konigsberg 2
Pr bl ddan M Problem Model d l Gr Graph ph Anallisis
MASALAH
MODEL Analisis Teori Graph
ALGORITMA
Data
IMPLEMENTASI PROGRAM
SOLUSI YANG DIHARAPKAN 3
Pr bl 1 Problem
Setiap 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 telepon umum ttersebut, b t dan d akhirnya khi kembali k b li ke kantor lagi. Problem yang muncul adalah petugas tersebut menginginkan suatu rute perjalanan dengan waktu minimal ?
Teori Graph
4
Pr bl 2 Problem
Pada suatu p persimpangan p g jjalan yyang g ramai akan dipasang lampu lalu lintas (TL). Telah diatur bahwa jalan A, C, D, E, dan F satu arah serta jalan B adalah 2 arah arah. Perjalanan yang diperbolehkan adalah :
AÆB DÆC
AÆC DÆE
AÆE FÆB
BÆC FÆC
BÆE FÆE
Problemnya adalah bagaimana menentukan pola l TL d dengan jjumlah l h ffase minimal,dan i i l d pada d setiap fase tidak ada perjalanan yang saling melintas ? Teori Graph
5
Pr bl 3 Problem Rute
perjalanan dari kota A ke P dapat dilakukan dengan berbagai macam alternatif Dari sekian banyak alternatif alternatif. yang ada maka tentukanlah rute yang paling minimal untuk ditempuh (misalkan minimal dalam hal jarak tempuh/waktu tempuh) ?
Teori Graph
6
M d l Gr Model Graph ph Jika kita lakukan analisis terhadap p ketiga g problem tadi, maka kita akan buatkan model persoalannya ke dalam model Graph. Problem P bl 1 pada d model d lG Graph h dik dikenall d dengan problem Travelling Salesman. Problem 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 l Pendahuluan Definisi 1 : Suatu Graph G = (V,E) adalah koleksi atau pasangan p g dari dua himpunan p V ((tidak kosong) 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 order Banyaknya edge disebut size (ukuran)
Teori Graph
8
P d h l Pendahuluan
(L j t ) (Lanjutan)
Contoh 1 : V = {s, u, v, w, x, y, z} E = {(x,s), {(x s) (x,v) (x v)1, (x,v)2, (x,u), (v,w), (s,v), (s,u), (s,w), (s,y), (w,y), (u,y), (u,z),(y,z)}
Teori Graph
9
Edge Ed Edge merupakan pasangan tak terurut dari simpul. Misalkan edge e = (v,w) = (w,v). Edge g e dikatakan incident p pada v dan w. Verteks terpencil (terisolasi) adalah suatu verteks tanpa p edge g incident.
p
Teori Graph
10
Ed Kh Edge Khusus
Edge Paralel
Dua edge atau lebih yang mempunyai kedua verteks erteks ujung j ng yang ang sama.
Graph disamping : edge (a b) merupakan edge (a,b) paralel atau edge sejajar.
Loop (self-loops)
Suatu edge yang kedua verteks ujungnya sama.
Teori Graph
Graph p disamping, p g, edge g (d,d) Æ self-loops. 11
Gr ph Kh Graph Khusus
Simple graph (Graph sederhana)
Suatu graph yang tidak memiliki self-loops dan ruas sejajar.
Weighted W i ht d graph h (Graph berlabel / berbobot)
Suatu graph yang setiap ruasnya dikaitkan dengan besaran tertentu (“bobot”) ( bobot ).
Teori Graph
12
G hB Graph Berarah h (Di (Digraph) h) G disebut graph berarah atau directed graph/ digraph jika setiap ruas merupakan pasangan terurut dari simpul. (dpl. Setiap ruasnya memiliki arah).
Teori Graph
13
G hB Graph Berarah h (Di (Digraph) h) Definisi: Jika (u,v) adalah edge dari graph berarah G, u dik t k adjacent dikatakan dj t ke k v dan d v dikatakan dik t k adjacent dari u. Vertex u dikatakan sebagai verteks inisial dari (u,v) dan v dikatakan sebagai verteks terminal atau verteks akhir (u (u,v). v) verteks inisial dan verteks terminal dari sebuah loop adalah sama Teori Graph
14
D r j t Verteks Derajat V rt k Derajat dari simpul v, dinotasikan dgn δ(v), adalah banyaknya ruas yang melalui v Contoh :
Teori Graph
δ(a) = 4, δ(c) = 4, δ(e) ( ) = 4, 4 δ(g) = 3.
δ(b) = 3, δ(d) = 6, δ(f) (f) = 4, 4
15
D r j tp Derajat pada d Gr Graph ph Teorema (The Handshaking Theorem): jika G suatu graph tidak berarah dengan m edge dan n verteks maka jjumlah derajat j semua verteks adalah 2m. n
Σ δ(vi) = 2m i=1
Æ jumlah dari derajat semua verteks pada graph tidak berarah adalah genap genap. Teori Graph
16
D r j tp Derajat pada d Gr Graph ph Teorema : Sebuah graph tidak berarah G memiliki sejumlah genap vertek berderajat ganjil
Teori Graph
17
D r j tp Derajat pada d Gr Graph ph Definisi: Sebuah graph berarah G memiliki derajat masuk dari sebuah verteks ((in-degree g of a vertex)) v,, 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), (v) menyatakan banyaknya edge dengan v sebagai verteks inisial. Teori Graph
18
G hB Graph Berarah h (Di (Digraph) h) δ-(a) = 1, δ-(b) = 2, δ-(c) = 2, δ-(d) = 3, δ-(e) = 1, δ-(f) = 1,
Teori Graph
δ+(a) = 2, δ+(b) = 1, δ+(c) = 2, δ+(d) = 2, δ+(e) = 2, δ+(f) = 1
19
D r j tp Derajat pada d Gr Graph ph Teorema : Misalkan G = (V (V,E) E) adalah graph berarah maka: − + δ ( v ) = δ ∑ ∑ (v ) = E v∈V
Teori Graph
v∈V
20
Gr ph L Graph Lengkap k pKn
Misalkan n > 3 Graph Lengkap (complete graph) h) Kn adalah d l h graph h dengan n simpul dan setiap pasang p g simpulnya p y terhubung g oleh satu ruas. Derajat setiap vertex sama Contoh di samping merupakan Graph lengkap K5
Teori Graph
21
Gr ph Bip Graph Bipartisi rti i
Graph p bipartisi p G adalah suatu graph sedemikian sehingga berlaku V(G) = V(G1) ∪ V(G2) |V(G1)| = m, |V(G2)| = n 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 Complete bipartite rtit graph r ph Km,n Suatu graph bipartisi adalah graph bipartisi lengkap (Complete bipartite graph) Km,n jika setiap simpul pada V(G1) terhubung dengan simpul pada V(G2) dan sebaliknya, sebaliknya |V(G1)| = m |V(G2)| = n
Teori Graph
23
Gr ph T Graph Terhubung rh b
Suatu Graph dikatakan terhubung (Connected) jika setiap pasang dari verteks dapat dilalui dengan suatu jalur.
Setiap subgraph terhubung dari suatu graph tak terhubung G disebut component dari G
Teori Graph
24
J l r(P th) dan Jalur(Path) d Cycle C l Suatu S t
Jalur J l (Path) (P th) dengan d panjang j n adalah barisan dari n + 1 verteks dan n edge d secara b berurutan. t Æ (v0, e1 , v1, e2 , v2, e3 , …, vn-1, en , vn)
Suatu
Cycle adalah jalur dengan verteks awal dan verteks akhirnya sama.
Teori Graph
25
Jalur (Path) dan Cycle
(Lanjutan)
Contoh : Diketahui suatu Graph G : 1 e6
e1 e7
6
e5
2 e8 5
e2 e9 e4
3 e3 4
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, 1, 6 5 Cycle dgn panjang 3 : 1, 2, 5, 1 atau 2, 3, 5, 2 Cycle dgn panjang 6 : 1 1, 2 2, 3 3, 4 4, 5 5, 6 6, 1
Teori Graph
26
S b r ph Subgraph Definisi : Misal G=(V,E) suatu Graph, G’ =(V’,E’) disebut d sebut subg subgraph ap da dari G jika j a:
V’ ⊆ V dan E’ ⊆ E
Contoh: Diketahui graph G sebagai berikut : a
subgraph
Teori Graph
e
b
c
27
P rj l Perjalanan Euler E l r
Sebuah perjalanan Euler (Euler cycle) pada graph G adalah sebuah cycle sederhana yang melalui setiap edge di G hanya sekali. sekali Problem jembatan Königsberg:
Apakah memungkinkan untuk memulai dan mengakhiri suatu perjalanan dari titik yang sama melalui ke 7 jembatan hanya sekali?
Problem dapat dinyatakan dengan sebuah graph Edge menyatakan jembatan dan setiap verteks menyatakan daerah (region) (region).
Teori Graph
28
Gr ph E Graph Euler l r Sebuah g graph p G adalah g graph p Euler jjika memiliki Euler cycle. Teorema: G adalah Graph Euler jika dan hanya jika G terhubung dan semua vertex memiliki derajat genap. Graph terhubung merepresentasikan problem jembatan Königsberg. Graph tersebut bukan Graph Euler.
Teori Graph
Berarti problem jembatan Königsberg tidak memiliki solusi. 29
