TEKNIK INFORMATIKA
TEKNIK INFORMATIKA
Teori Graf mulai dikenal pada saat seorang matematikawan bangsa Swiss, bernama Leonhard Euler, berhasil mengungkapkan Misteri Jembatan Konigsberg pada tahun 1736. Di Kota Konigsberg (sekarang bernama Kalilingrad, di Uni Soviet) mengalir sebuah sungai bernama sungai Pregel. Di tengah sungai tersebut terdapat dua buah pulau. Dari kedua pulau tersebut terdapat jembatan yang menghubungi ke tepian sungai dan diantara kedua pulau. Jumlah jembatan tersebut adalah 7 buah seperti gambar berikut :
Teori Dasar Graf A
Sungai Pregel di Kalilingrad (Uni Soviet)
C
D
B
TEKNIK INFORMATIKA
Konon kabarnya, penduduk kota Konigsberg sering berjalan-jalan ke tempat tersebut pada hari-hari libur. Kemudian muncul suatu keinginan untuk dapat menikmati daerah tersebut dengan melalui ketujuh jambatan tepat satu kali, yakni bermula dari satu tempat (A, B, C atau D) dan kembali ke tempat semula. Mereka berusaha untuk memperoleh rute yang sesuai dengan keinginan tersebut, dengan selalu mencoba menjalaninya. Setelah mencoba berkali-kali dan karena sudah cukup lama tidak diperoleh rutenya, akhirnya penduduk tersebut mengirim surat kepada Euler. Euler dapat memecahkan masalah tersebut, yakni bahwa perjalanan / rute yang diinginkan (yakni berawal dari suatu tempat, melalui ketujuh jembatan tepat satu kali, dan kembali ke tempat semula) tidak mungkin dicapai.
TEKNIK INFORMATIKA
Secara singkat, dalam tulisannya, Euler menyajikan keadaan jembatan Konigsberg tersebut seperti gambar berikut :
Dalam masalah di atas, daratan (tepian A dan B, serta pulau C dan D) disajikan sebagai titik dan jembatan disajikan sebagai ruas garis. Euler mengemukakan teoremanya yang mengatakan bahwa perjalanan yang diinginkan di atas (yang kemudian dikenal sebagai perjalanan Euler) akan ada apabila graf terhubung dan banyaknya garis yang datang pada setiap titik (derajat simpul) adalah genap.
TEKNIK INFORMATIKA
GRAPH • Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :
G = (V, E) Dimana G = Graph V = Simpul atau Vertex, atau Node, atau Titik E = Busur atau Edge, atau arc
TEKNIK INFORMATIKA
Contoh graph : vertex v2 B
e1 v1
A
e4
V terdiri dari v1, v2, …, v5 e3
C v3
edge
e2 v4 D
e5
e6
E terdiri dari e1, e2, … , e7 e7
E
v5
Undirected graph
TEKNIK INFORMATIKA
• 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
TEKNIK INFORMATIKA
Graph v2Berarah dan Graph Tak Berarah : v2 B
e8 e1 v1
A e2
e10
D
v4
e3 e4
e5 e6
B
e9
C
e1 v3
e7
E v5
Directed graph
v1
e3 e4
A e2 v4 D
C v3
e5
e6
e7
E
v5
Undirected graph
Dapat dilihat dari bentuk busur yang artinya urutan penyebutan pasangan 2 simpul.
TEKNIK INFORMATIKA
• 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.
TEKNIK INFORMATIKA
• 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.
TEKNIK INFORMATIKA
Graph Berbobot : B
4 5 v1
A e2
12
8 v4
B
7 3
10
D
v2
v2
3
5
C
v3
6
E v5
Directed graph
v1
3 12
A 4 v4 D
C v3
8
3
6
E
v5
Undirected graph
Panjang busur (atau bobot) mungkin tidak digambarkan secara panjang yang proposional dengan bobotnya. Misal bobot 5 digambarkan lebih panjang dari 7.
TEKNIK INFORMATIKA
Incident
Istilah pada graph
Jika e merupakan busur dengan simpulsimpulnya 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 outdegree Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.
TEKNIK INFORMATIKA
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.
TEKNIK INFORMATIKA
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. e
w
v
Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v. e v
w
TEKNIK INFORMATIKA
4. Successor dan Predecessor Pada 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. Path Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya. 1
2
3
4
1 3
2
1
2
1
2
4
3
4
3
4
TEKNIK INFORMATIKA
Representasi Graph dalam bentuk matrix
• Adjacency Matrix Graph tak berarah Urut abjad
B
A
C
D Graph
E
A 0
B 1
C 2
D 3
E 4
0
1
0
1
0
1
0
1
0
1
A
0
B
1
C
2
D
3
0
1
0
1
1
E
4
1
0
1
0
1
0
1
1
1
0
Degree simpul : 3
TEKNIK INFORMATIKA
Representasi Graph dalam bentuk matrix
• Adjacency Matrix Graph berarah ke dari
B
A
C
D
E Graph
A 0
B 1
C 2
D 3
E 4
0
1
0
1
0
1
0
1
0
1
A
0
B
1
C
2
D
3
0
1
0
1
1
E
4
0
0
1
0
1
0
0
0
0
0
out
in
TEKNIK INFORMATIKA
PROBLEMA DAN MODEL GRAPH DALAM METODE GREEDY ( Lanjutan )
1. TRAVELLING SALESMAN Untuk menentukan waktu perjalanan seorang salesman seminimal mungkin. Problema : Setiap minggu sekali, seorang petugas kantor telepon berkeliling untuk mengumpulkan coin-coin pada telepon umum yang dipasang diberbagai tempat. Berangkat dari kantornya, ia mendatangi satu demi satu telepon umum tersebut dan akhirnya kembali ke kantor lagi. Problemnya, ia menginginkan suatu route perjalanan dengan waktu minimal
TEKNIK INFORMATIKA
MODEL GRAPH : 8
10
7 1
11
12 11
4
2
9 5
8
9
10 3
Misalnya : Kantor pusat adalah simpul 1 dan misalnya ada 4 telepon umum, yg kita nyatakan sebagai simpul 2, 3, 4 dan 5 dan bilangan pada tiap-tiap ruas menunjukan waktu ( dalam menit ) perjalanan antara 2 simpul .
TEKNIK INFORMATIKA
Langkah penyelesaian : 1. Dimulai dari simpul yg diibaratkan sebagai kantor pusat yaitu simpul 1 . 2.Dari simpul 1 pilih ruas yg memiliki waktu yg minimal. 3. Lakukan terus pada simpul – simpul yg lainnya tepat satu kali yg nantinya Graph akan membentuk Graph tertutup karena perjalanan akan kembali ke kantor pusat. 4. Problema diatas menghasilkan waktu minimalnya adalah 45 menit dan diperoleh perjalanan sbb :
TEKNIK INFORMATIKA
Problema diatas menghasilkan waktu minimalnya adalah 45 menit dan diperoleh perjalanan sbb : 7 1
8
2
12 5
4
10 3
8
TEKNIK INFORMATIKA
2. MINIMUM SPANNING TREE Kasus MST Problem = m’cari min.biaya (cost) spanning tree dr setiap ruas (edge) graph yg m’btk pohon (tree). Solusi dr p’masalah’ ini : a. Dgn memilih ruas suatu graph yg memenuhi kriteria dr optimisasi yg m’hasilk’ biaya min. b. Penambah’ dr setiap ruas pd seluruh ruas yg m’btk graph akan m’hasilk’ nilai/biaya yg kecil (minimum cost). Kriteria2 dr spanning tree, yakni : 1. Setiap ruas pada graph harus terhubung (conected) 2. Setiap ruas pd graph hrs mpy nilai (label graph) 3. Setiap ruas pd graph tdk mpy arah (graph tdk berarah)
TEKNIK INFORMATIKA
Pros.Total minimum cost terbentuknya graph dgn tahapan sbb: • Dari graph yg tetbentuk, apakah memenuhi kriteria MST. • Lakukan secara urut dr simpul ruas awal s/d ruas akhir • Pada setiap simpul ruas perhatikan nilai/cost dr tiap-tiap ruas • Ambil nilai yg paling kecil (jarak tertpendek setiap ruas). • Lanjutkan s/d semua simpul ruas tergambar pd spanning tree • Jumlahkan nilai/cost yg dipilih tadi.
TEKNIK INFORMATIKA 10
1
2
45
30
50 40
4 20
3
35
25 5 55 6
15
3. SHORTEST PATH PROBLEM 1. Permasalahan= menghitung jalur terpendek dr sbh graph berarah. 2. Kriteria utk permasalahan jalur terpendek/SP problem tsb : 3. Setiap ruas pd graph hrs mpy nilai (label graph) 4. Setiap ruas pd graph tdk hrs terhubung (unconnected) 5. Setiap ruas pd graph tsb hrs mempunyai arah (graph berarah).
TEKNIK INFORMATIKA 45
A 10
B
50
20
20
15
E
10 35 30
C
F
D
15
3
Penyelesaian: Jalur A–C
Panjang jarak 10
A–C–D
25
A–C–D–B
45
A–E
45
