graph
DESCRIPTION
GRAPH. Graph digunakan untuk merepresentasikan obyek-obyek diskrit dan hubungan antar obyek-obyek tersebut. Representasi visual dinyatakan sebagai noktah, bulatan atau titik, sedangkan hubungan antara obyek dinyatakan dengan garis. Contoh 1 :. Contoh 2. Contoh 3. GRAPH. - PowerPoint PPT PresentationTRANSCRIPT
GRAPH
• Graph digunakan untuk merepresentasikan obyek-obyek
diskrit dan hubungan antar obyek-obyek tersebut.
• Representasi visual dinyatakan sebagai noktah, bulatan atau titik, sedangkan hubungan antara obyek
dinyatakan dengan garis
Contoh 1 :
Contoh 2
Contoh 3
GRAPH
• Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :
G = (V, E)Dimana
G = GraphV = Simpul atau Vertex, atau Node, atau
TitikE = Busur atau Edge, atau arc
Contoh graph :
B
A C
D E
Undirected graph
vertex
edge
e1 e3e4
e7e5e2
e6
v1
v2
v4 v5
v3
V terdiri dari v1, v2, …, v5
E terdiri dari e1, e2, … , e7
• Sebuah graph mungkin hanya terdiri dari satu simpul
• Sebuah graph belum tentu semua simpulnya terhubung dengan busur
• Sebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain
• Sebuah graph mungkin semua simpulnya saling berhubungan
Graf Sederhana
Simple graphs do not have loops or multiple arcs between pairs of nodes. Most networks in D1 are Simple graphs.
A subgraph Dapat dibentuk dengan membuang garis atau titik dari grafik lain
Graph Subgraph
A bipartite graph adalah grafik dimana ada 2 set node. Tidak ada busur dalam salah satu set node.
A complete bipartite graph adalah grafik bipartit di mana setiap node dalam satu set terhubung ke setiap node pada set lain
Graph Berarah dan Graph Tak Berarah :
B
A C
D E
B
A C
D E
Directed graph
Undirected graph
e1 e3
e4
e7e5e2
e6
v1
v2
v4 v5
v3v1
v2
v3
v5v4
e1
e2
e3
e4
e5
e6
e7
e8 e9
e10
Dapat dilihat dari bentuk busur yang artinya urutan penyebutan pasangan 2 simpul.
• Graph tak berarah (undirected graph atau non-directed graph) :• Urutan simpul dalam sebuah busur tidak
dipentingkan. Mis busur e1 dapat disebut busur AB atau BA
• Graph berarah (directed graph) :• Urutan simpul mempunyai arti. Mis
busur AB adalah e1 sedangkan busur BA adalah e8.
1. Graf Tidak Berarah (Undirected Graph )
Graf yang sisinya tidak mempunyai orientasi arah
disebut graf tak berarah. Pada graf tak – berarah,
urutan pasangan simpul yang dihubungkan oleh
sisi tidak di perhatikan. Jadi (u,v) = (v,u) adalah sisi
yang sama.
Jenis-Jenis Graph
2. Graf Berarah (Directed Graph = Digraph)
Graf yang setiap sisinya diberikan orientasi arah.
Sisi berarah disebut sebagai arch (busur). Pada
graf berarah, (u,v) dan (v,u) menyatakan dua
buah busur yang berbeda. Untuk simpul (u,v),
simpul u dinamakan simpul asal dan simpul v
disebut sebagai Simpul Terminal.
Contoh soal:
Gambarlah sebuah graf sederhana yang dapat di
bentuk dari 4 titik {a, b, c, d} dan 2 garis.
Penyelesaian :
Sebuah garis dalam graf sederhana selalu
berhubungan dengan 2 titik. Oleh karena ada 4
titik, maka ada C(4,2) = 6 garis yang mungkin di
buat. Yaitu garis – garis dengan titik ujung {a,b},
{a,c},{a,d},{b,c},{b,d},{c,d}.
Dari keenam garis yang mungkin tersebut, selanjutnya dipilih 2 garis diantaranya. Jadi ada C(6,2) = 15 buah graf yang mungkin di bentuk dari 4 buah titik dan 2 buah garis.
• Graph Berbobot (Weighted Graph)• Jika setiap busur mempunyai nilai yang
menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.
• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.
Graph Berbobot :
B
A C
D E
B
A C
D E
Directed graph
Undirected graph
5 3
12
684
3
v1
v2
v4 v5
v3v1
v2
v3
v5v4
5
e2
312
8
3
6
4 7
10
Panjang busur (atau bobot) mungkin tidak digambarkan secara panjang yang proposional dengan bobotnya. Misal bobot 5 digambarkan lebih panjang dari 7.
Istilah pada graph
Incident Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.
Degree (derajat), indegree dan outdegreeDegree sebuah simpul adalah jumlah
busur yang incident dengan simpul tersebut.
Indegree sebuah simpul pada graph berarah adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.
Outdegree sebuah simpul pada graph berarah adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.
3. Adjacent Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.
Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.
we
v
v
e w
4. Successor dan PredecessorPada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.
5. PathSebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.
1
43
2
4
2
4
2
4
21
3
1
3
1
3
Representasi Graph dalam bentuk matrix
• Adjacency Matrix Graph tak berarah
B
A C
D E
Graph
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
0 1 1 1 0
A B
A
0
B
C
1 2 43C D E
D
E
0
1
2
4
3
Urut abjad
Degree simpul : 3
Representasi Graph dalam bentuk matrix
• Adjacency Matrix Graph berarah
Graph
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
0 0 1 0 1
0 0 0 0 0
A B
A
0
B
C
1 2 43C D E
D
E
0
1
2
4
3
B
A C
D E
kedari
out
in
• Adjency List graph tak berarah• Digambarkan sebagai sebuah simpul
yang memiliki 2 pointer. • Simpul vertex : Simpul edge :
Representasi Graph dalam bentuk Linked List
info info
Menunjuk ke simpul vertex berikutnya,
dalam untaian simpul yang ada.
Menunjuk ke simpul edge pertama Menunjuk ke
simpul edge berikutnya, bila
masih ada.Menunjuk ke simpul vertex tujuan yang
berhubungan dengan simpul vertex asal.
left right left right
• Define struct untuk sebuah simpul yang dapat digunakan sebagai vertex maupun edge.
typedef struct tipeS {
tipeS *Left;
int INFO;
tipeS *Right;
};
tipeS *FIRST, *PVertex, *PEdge;
Contoh : untuk vertex A, memiliki 2 edge yang terhubung yaitu e1 dan e2.
A
C
D
B
E
e2
Graph
e1B
A C
D E
e1e3
e4
e7e5e2
e6
Urut abjad
Gambar di atas dapat disusun dengan lebih sederhana, sbb :
A
C
D
B
E
D
A
B
A
B
C E
D E
C
C D
B
A C
D E
Graph
B
E
Adjency List graph berarah
A
C
D
B
E
D
A
B
C
E
C
B
E
B
A C
D E
Graph berarah dan berbobot
B
A C
D E
53
2
14
12
6
7
12
0 5 0 2 0
6 0 3 0 0
0 0 0 0 9
0 0 12
0 7
0 14
0 0 0
A
A
0
B
C
1 2 43
D
E
0
1
2
4
3
B C D E
Perhatikan pemilihan nilai 0.
Graf Planar (Planar Graph)Graf yang dapat digambar pada bidang datar dengan sisi-sisi
tidak saling bertindihan disebut graf planar.Jika tidak, maka graf tersebut adalah graf tak-planar.
Graf planar, sisi yang bertindihan dapat diatur menjadi tidak bertindihan
Contoh graf tak-planar
Graf Planar (Planar Graph)
Lintasan dan Sirkuit Euler
Contoh:Lintasan Euler pada graf (a): 3, 1, 2, 3, 4, 1.Lintasan Euler pada graf (b): 1, 2, 4, 6, 2, 3, 6, 5, 1, 3, 5.Sirkuit Euler pada graf (c): 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1.
12
3 4
1 2
34
5 6
1
2 3
45
6 7(a) (b) (c)
Graf (a) dan (b) adalah graf semi-Euler.Graf (c) adalah graf Euler.
Teorema:Graf berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar yang sama.
Teorema:Graf berarah G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang pertama memiliki derajat-keluar satu lebih banyak dari derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih banyak dari derajat-keluar.
Jembatan Königsberg (1736)
Bisakah orang melalui setiap jembatan tepat satu kali dan kembali lagi ke tempat semula?
Solusi:Tidak bisa.Derajat d(A) = 5, d(B) = 3, d(C) = 3, d(D) = 3 4 derajat ganjil.Tidak dapat dibuat sebuah sirkuit Euler.
Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat satu kali.
Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.
Graf yang memiliki lintasan Hamilton disebut graf semi-Hamilton.
Graf yang memiliki sirkuit Hamilton disebut graf Hamilton.
(a) (b) (c)
1 2
34
1 2
34
1 2
34
Contoh:Graf (a) memiliki lintasan Hamilton: misal 3, 2, 1, 4.Graf (b) memiliki sirkuit Hamilton: 1, 2, 3, 4, 1.Graf (c) tidak memiliki lintasan maupun sirkuit Hamilton.
Contoh:Temukan sirkuit Hamilton dari graf berikut ini.
Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat satu kali.
Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.
Graf yang memiliki lintasan Hamilton disebut graf semi-Hamilton.
Graf yang memiliki sirkuit Hamilton disebut graf Hamilton.
Aplikasi Graph
Persoalan pedagang keliling (Travelling salesman problem).
Persoalan tukang pos Cina (Chinese postman problem).
Pewarnaan graf (Graph coloring).
Travelling Salesman Problem (TSP)
Diberikan sejumlah kota dan diketahui jarak antar kota.Tentukan sirkuit terpendek yang harus dilalui oleh seorang
pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan.
Merupakan persoalan menentukan sirkuit Hamilton yang memiliki bobot minimum.
Contoh:Tentukan sirkuit Hamilton terpendek dari graf berikut ini
a b
cd
12
8
15
1095
Solusi:Terdapat 3 sirkuit Hamilton pada graf di atas
a b
cd
12
8
15
10
a b
cd
12
15
95
a b
cd
81095
P1 = (a, b, c, d, a) atau (a, d, c, b, a) Bobot = 12 + 8 + 15 + 10 = 45
P2 = (a, b, d, c, a) atau (a, c, d, b, a) Bobot = 12 + 9 + 15 + 5 = 41
P3 = (a, c, b, d, a) atau (a, d, b, c, a) Bobot = 5 + 8 + 9 + 10 = 32
Sirkuit Hamilton terpendek: P3
a b
cd
12
8
15
10
a b
cd
12
15
95
a b
cd
81095
FUZZY
SYSTEMINPUT OUTPUT
CONTOH : Output bertambah besar jika input bertambah besar
ATAU
Jika input besar maka output besarIF input is BIG THEN output is BIGIF x is B THEN y is B