PROGRAM STUDI TEKNIK INFORMATIKA
FAKULTAS TEKNIK
UNIVERSITAS MUHAMMADIYAH JEMBER
TEORI GRAF
ILHAM SAIFUDIN Selasa, 13 Desember 2016 Universitas Muhammadiyah Jember
OUTLINE Pendahuluan
Jenis-jenis Graf
Terminologi Graf
Representasi Graf
ILHAM SAIFUDIN
1 2
Definisi Graf
4
Contoh Aplikasi Graf
6
Graf-graf Khusus
8
Graf Isomorfik
3
5
7
TI
TEORI GRAF
1. PENDAHULUAN
OUTLINE
1. PENDAHULUAN a. Pengertian Graf adalah salah satu pokok bahasan Matematika Diskrit yang telah lama dikenal dan banyak diaplikasikan pada berbagai bidang.
b. Sejarah Teori graf muncul pertama kali pada tahun 1736, yakni Ketika Euler mencoba untuk mencari solusi dari permasalahan yang sangat terkenal yaitu Jembatan Konigsberg dan apabila jembatan Konigsberg direpresentasikan kedalam graf. ILHAM SAIFUDIN
TI
TEORI GRAF
1. PENDAHULUAN
OUTLINE
Leonhard Euler 15 April 1707 β 18 September 1783
Gambar 1. Jembatan Konigsberg ο± Simpul (vertex) menyatakan daratan ο± Sisi (edge) menyatakan jembatan
Gambar 2. Representasi graf pada permasalahan jembatan K¨ onigsberg ILHAM SAIFUDIN
TI
TEORI GRAF
2. DEFINISI GRAF
OUTLINE
2. Definisi Graf Suatu graf G didefinisikan sebagai pasangan himpunan (π, πΈ), yang dalam hal ini π adalah himpunan tak kosong dari semua titik π = *π£1 , π£2 , π£3 , β¦ , π£π + dan πΈ adalah himpunan sisi (edges) yang menghubungkan sepasang titik πΈ = *π1 , π2 , π3 , β¦ , ππ +. Dalam sebuah graf, harus ada (vertex) minimal satu sedangkan sisi (edge) tidak ada jumlah minimal sehingga boleh kosong. Jadi satu titik (vertex) saja sudah dapat dikatakan sebagai graf.
ILHAM SAIFUDIN
TI
TEORI GRAF
2. DEFINISI GRAF
OUTLINE
1
1
4
2
4
2
3
3 Gambar 3. Graf Sederhana
Gambar 4. Graf Ganda
Buatlah π dan πΈ nya?
ILHAM SAIFUDIN
TI
TEORI GRAF
3. JENIS-JENIS GRAF
OUTLINE
3. Jenis-jenis Graf Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis: A. Graf sederhana (simple graph) : Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. B. Graf tak-sederhana (unsimple-graph) : Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph).
ILHAM SAIFUDIN
TI
TEORI GRAF
3. JENIS-JENIS GRAF
OUTLINE
Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis: A. Graf tak-berarah (undirected graph) : Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. B. Graf berarah(directed graphatau digraph) : Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada Gambar 3 adalah graf berarah.
ILHAM SAIFUDIN
TI
TEORI GRAF
3. JENIS-JENIS GRAF
OUTLINE
Gambar 5. Graf berarah
ILHAM SAIFUDIN
TI
TEORI GRAF
4. CONTOH APLIKASI GRAF
OUTLINE
4. Contoh Aplikasi Graf A
Jaringan Komputer
Gambar 6. Jaringan Komputer Menggunakan Graf Lengkap
ILHAM SAIFUDIN
TI
TEORI GRAF
4. CONTOH APLIKASI GRAF
OUTLINE
B
Rangkaian Listrik
Gambar 7. (a) Rangkaian Listrik dan (b) Representasi pada Graf
ILHAM SAIFUDIN
TI
TEORI GRAF
4. CONTOH APLIKASI GRAF
OUTLINE
C
Jejaring makanan
Gambar 8. Aplikasi Graf pada Jejaring makanan (Biologi)
ILHAM SAIFUDIN
TI
TEORI GRAF
4. CONTOH APLIKASI GRAF
OUTLINE
D
Pewarnaan Peta (Graf Coloring )
Gambar 9. Aplikasi Graf pada Pewarnaan Peta
ILHAM SAIFUDIN
TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
5. Terminologi Graf 1
Ketetanggaan (Adjacent) Dua buah simpul dikatakan terhubung langsung.
bertetangga
1
4
bila keduanya
β’ simpul 1 bertetangga dengan simpul 2 dan 4 2
3 Gambar 10. πΊ1 ILHAM SAIFUDIN
TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
2
Bersisian (Incidency) Untuk sembarang sisi π = (π£π , π£π ) dikatakan β’ π bersisian dengan simpul π£π β’ π bersisian dengan simpul π£π 1
4
2
β’ sisi (2, 3) bersisian dengan simpul 2 dan simpul 3
3 Gambar 11. πΊ1 ILHAM SAIFUDIN
TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
3
Simpul Terpencil (Isolated Vertex) Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya. 1 5 4
2
3 Gambar 12. πΊ2 : simpul 5 adalah simpul terpencil ILHAM SAIFUDIN
TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
4
Graf Kosong (null graph atau empty graph)
Graf yang himpunan sisinya merupakan himpunan kosong.
1 5 4
2
3 Gambar 13. πΊ3 : null graph ILHAM SAIFUDIN
TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
5
Derajat (Degree) Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut. Notasi: π(π£)
1 5
4
2
ο§ ο§ ο§ ο§
π π π π
1 4 2 5
=π 3 =2 =3 =4 =1
3 Gambar 14. πΊ4 ILHAM SAIFUDIN
TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
6
Lintasan (Path) Lintasan yang panjangnya ndari simpul awal π£0 ke simpul tujuan π£π di dalam graf πΊ ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk π£0 , π1 , π£1 , π2 , π£2 , β¦ , π£πβ1 , ππ , π£π . 1
4
2
3 Gambar 15. πΊ5 ILHAM SAIFUDIN
TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
7
Siklus (Cycle) atau Sirkuit (Circuit) Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.
1
4
2
3 Gambar 16. πΊ6 ILHAM SAIFUDIN
TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
8
Terhubung (Connected) Dua buah simpul π£1 dan simpul π£2 disebut terhubung jika terdapat lintasan dari π£1 ke π£2 . 1
2
Gambar 17. πΊ7 ILHAM SAIFUDIN
TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
9
Upagraf (Subgraph) dan Komplemen Upagraf ο§ Misalkan πΊ = (π, πΈ) adalah sebuah graf. πΊ = (π1 , πΈ1 ) adalah upagraf (subgraf) dari πΊ jika π1 β π dan πΈ1 β πΈ. ο§ Komplemen dari upagraf πΊ1 terhadap πΊ adalah πΊ2 = (π2 , πΈ2 ) sedemikian sehingga πΈ2 = πΈ-πΈ1 dan π2 adalah himpunan simpul yang anggota-anggota πΈ2 bersisian dengannya.
Gambar 18. πΊ8 ILHAM SAIFUDIN
Gambar 19. πΊ9 : upagraf Gambar 20. πΊ10 : Komplemen TI
TEORI GRAF
5. TERMINOLOGI GRAF
OUTLINE
10
Graf Berbobot (Weighted Graph)
ο§ Graf berbobotadalah graf yang setiap sisinya diberi sebuah harga (bobot).
1 3
2
4
5 Gambar 21. πΊ11 ILHAM SAIFUDIN
TI
TEORI GRAF
TUGAS
OUTLINE
TUGAS INDIVIDU
SEBUT DAN JELASKAN MACAM-MACAM GRAF KHUSUS DAN HASIL OPERASI PADA GRAF !
ILHAM SAIFUDIN
TI
TEORI GRAF
OUTLINE
βTERIMAKASIHβ
ILHAM SAIFUDIN
TI
TEORI GRAF
