ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI GRAF PPT \ PENGANTAR GRAF PPT

FILE ASLI PPT NYA BISA DI DOWNLOAD DISINI

Rinaldi M/IF2091 Strukdis 1
Graf
(bagian 1)
Bahan Kuliah
IF2091 Struktur Diskrit
Rinaldi M/IF2091 Strukdis 2
Pendahuluan
• Graf digunakan untuk merepresentasikan objek-objek diskrit
dan hubungan antara objek-objek tersebut.
• Gambar di bawah ini sebuah graf yang menyatakan peta
jaringan jalan raya yang menghubungkan sejumlah kota di
Provinsi Jawa Tengah.
Brebes Tegal
Slawi
Pemalang
Purwokerto
Cilacap
Banjarnegara
Wonosobo
Kebumen
Purworejo
Kendal

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI GRAF PPT \ PENGANTAR GRAF PPT

Semarang
Pekalongan
Purbalingga
Magelang
Salatiga
Klaten
Solo
Purwodadi
Demak
Kudus
Rembang
Blora
Sukoharjo
Wonogiri
Sragen
Boyolali
Kroya
Temanggung
Rinaldi M/IF2091 Strukdis 3
• Sejarah Graf: masalah jembatan Königsberg (tahun 1736)
Gambar 1. Masalah Jembatan Königsberg

• Graf yang merepresentasikan jembatan Königsberg:
Simpul (vertex) → menyatakan daratan
Sisi (edge) → menyatakan jembatan
• Bisakah melalui setiap jembatan tepat sekali dan kembali lagi
ke tempat semula?
C

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI GRAF PPT \ PENGANTAR GRAF PPT

A
B
D
Rinaldi M/IF2091 Strukdis 4
Leonhard Euler
15 April 1707 – 18 September 1783
Konigsberg Bridge Problem
Rinaldi M/IF2091 Strukdis 5
Rinaldi M/IF2091 Strukdis 6
Definisi Graf
Graf G = (V, E), yang dalam hal ini:
V = himpunan tidak-kosong dari simpul-simpul (vertices)
= { v1 , v2 , ... , vn }
E = himpunan sisi (edges) yang menghubungkan sepasang
simpul
= {e1 , e2 , ... , en }
Rinaldi M/IF2091 Strukdis 7
G1 G2 G3
Gambar 2. (a) graf sederhana, (b) graf ganda, dan (c) graf semu
Contoh 1. Pada Gambar 2, G1 adalah graf dengan
V = { 1, 2, 3, 4 } E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }
G2 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }
= { e1, e2, e3, e4, e5, e6, e7}
G3 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7, e8}
1 1 1
2 3
4
2 3
4
2
4

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI GRAF PPT \ PENGANTAR GRAF PPT

3
e1
e2
e3
e4
e5
e6
e7
e1
e2
e3
e4
e5
e6
e7
e8
Rinaldi M/IF2091 Strukdis 8
G1 G2 G3
Gambar 2. (a) graf sederhana, (b) graf ganda, dan (c) graf semu
• Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisiganda (multiple edges atau paralel edges) karena kedua sisi
ini menghubungi dua buah simpul yang sama, yaitu simpul 1
dan simpul 3.
• Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop)
karena ia berawal dan berakhir pada simpul yang sama.
1 1 1
2 3
4
2 3
4
2
4
3
e1
e2
e3
e4
e5
e6
e7

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI GRAF PPT \ PENGANTAR GRAF PPT

e1
e2
e3
e4
e5
e6
e7
e8
Rinaldi M/IF2091 Strukdis 9
Jenis-Jenis Graf
• Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu
graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda
dinamakan graf sederhana. G1 pada Gambar 2 adalah
contoh graf sederhana
2. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan
graf tak-sederhana (unsimple graph). G2 dan G3 pada
Gambar 2 adalah contoh graf tak-sederhana
Rinaldi M/IF2091 Strukdis 10
• Berdasarkan orientasi arah pada sisi, maka secara umum graf
dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut
graf tak-berarah. Tiga buah graf pada Gambar 2 adalah
graf tak-berarah.
2. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut
sebagai graf berarah. Dua buah graf pada Gambar 3 adalah
graf berarah.
Rinaldi M/IF2091 Strukdis 11 (a) G4 (b) G5
Gambar 3 (a) graf berarah, (b) graf-ganda berarah
1 1
2 3
4
2 3
4
Rinaldi M/IF2091 Strukdis 12
Tabel 1 Jenis-jenis graf [ROS99]
Jenis Sisi Sisi ganda
dibolehkan?
Sisi gelang
dibolehkan?
Graf sederhana
Graf ganda
Graf semu
Graf berarah
Graf-ganda berarah
Tak-berarah
Tak-berarah
Tak-berarah
Bearah
Bearah
Tidak
Ya
Ya
Tidak
Ya
Tidak
Tidak
Ya
Ya
Ya

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI GRAF PPT \ PENGANTAR GRAF PPT

Rinaldi M/IF2091 Strukdis 13
Contoh Terapan Graf
1. Rangkaian listrik.
(a) (b)
A
B
C
E D
F
A
B
C
E D
F
Rinaldi M/IF2091 Strukdis 14
2. Isomer senyawa kimia karbon
metana (CH4
) etana (C2H6
) propana (C3H8
)
C
H
H
H H
Rinaldi M/IF2091 Strukdis 15
3. Transaksi konkuren pada basis data terpusat
Transaksi T0 menunggu transaksi T1 dan T2
Transaksi T2 menunggu transaksi T1
Transaksi T1 menunggu transaksi T3
Transaksi T3 menunggu transaksi T2
deadlock!
T1
T0
T3
T2
Rinaldi M/IF2091 Strukdis 16
4. Pengujian program
read(x);
while x <> 9999 do
begin
if x < 0 then writeln(‘Masukan tidak boleh negatif’) else x:=x+10; read(x); end; writeln(x); Keterangan: 1 : read(x) 5 : x := x + 10 2 : x <> 9999 6 : read(x)
3 : x < 0 7 : writeln(x)
4 : writeln(‘Masukan tidak boleh negatif’);
1 2
3
4
5
6 7
Rinaldi M/IF2091 Strukdis 17
5. Terapan graf pada teori otomata [LIU85].
Mesin jaja (vending machine)
Keterangan:
a : 0 sen dimasukkan
b : 5 sen dimasukkan
c : 10 sen dimasukkan
d : 15 sen atau lebih dimasukkan
a b c d
P P P
P
5
5
10
10
10
10
5
5
Rinaldi M/IF2091 Strukdis 18

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI GRAF PPT \ PENGANTAR GRAF PPT

Latihan
Gambarkan graf yang menggambarkan
sistem pertandingan ½ kompetisi
(round-robin tournaments) yang diikuti
oleh 6 tim.

Tweet

Postingan terkait:

— Sunday, May 31, 2020 — Add Comment — matematika