teori graf - ilhamsaifudin12.files.wordpress.com · 4 contoh aplikasi graf terminologi graf 5 6...
Embed Size (px)
TRANSCRIPT
TEORI GRAF
PROGRAM STUDI TEKNIK INFORMATIKA
FAKULTAS TEKNIK
UNIVERSITAS MUHAMMADIYAH JEMBER
ILHAM SAIFUDIN Selasa, 13 Desember 2016 Universitas Muhammadiyah Jember
OUTLINE
ILHAM SAIFUDIN TI TEORI GRAF
1
2
3
Pendahuluan
Definisi Graf
Jenis-jenis Graf
4 Contoh Aplikasi Graf
5 Terminologi Graf
6 Graf-graf Khusus
7 Representasi Graf
8 Graf Isomorfik
OUTLINE 1. PENDAHULUAN
1. PENDAHULUAN
a. Pengertian Graf adalah salah satu pokok bahasan Matematika Diskrit yang telah lama dikenal dan banyak diaplikasikan pada berbagai bidang.
ILHAM SAIFUDIN TI TEORI GRAF
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.
OUTLINE 1. PENDAHULUAN
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 1. Jembatan Konigsberg
Gambar 2. Representasi graf pada permasalahan jembatan K onigsberg
Simpul (vertex) menyatakan daratan
Sisi (edge) menyatakan jem-batan
Leonhard Euler 15 April 1707 18 September 1783
OUTLINE 2. DEFINISI GRAF
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, , +.
ILHAM SAIFUDIN TI TEORI GRAF
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.
OUTLINE 2. DEFINISI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 3. Graf Sederhana Gambar 4. Graf Ganda
1
2 4
3
1
2 4
3
Buatlah dan nya?
OUTLINE 3. JENIS-JENIS GRAF
3. Jenis-jenis Graf
ILHAM SAIFUDIN TI TEORI 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).
OUTLINE 3. JENIS-JENIS GRAF
ILHAM SAIFUDIN TI TEORI GRAF
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.
OUTLINE 3. JENIS-JENIS GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 5. Graf berarah
OUTLINE 4. CONTOH APLIKASI GRAF
4. Contoh Aplikasi Graf
ILHAM SAIFUDIN TI TEORI GRAF
A Jaringan Komputer
Gambar 6. Jaringan Komputer Menggunakan Graf Lengkap
OUTLINE 4. CONTOH APLIKASI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
B Rangkaian Listrik
Gambar 7. (a) Rangkaian Listrik dan (b) Representasi pada Graf
OUTLINE 4. CONTOH APLIKASI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
C Jejaring makanan
Gambar 8. Aplikasi Graf pada Jejaring makanan (Biologi)
OUTLINE 4. CONTOH APLIKASI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
D Pewarnaan Peta (Graf Coloring )
Gambar 9. Aplikasi Graf pada Pewarnaan Peta
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 10. 1
5. Terminologi Graf
1 Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
1
2 4
3
simpul 1 bertetangga dengan simpul 2 dan 4
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 11. 1
2 Bersisian (Incidency)
Untuk sembarang sisi = ( , ) dikatakan
bersisian dengan simpul
bersisian dengan simpul
1
2 4
3
sisi (2, 3) bersisian dengan simpul 2 dan simpul 3
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 12. 2: simpul 5 adalah simpul terpencil
3 Simpul Terpencil (Isolated Vertex)
Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.
1
2 4
3
5
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 13. 3: null graph
4 Graf Kosong (null graph atau empty graph)
Graf yang himpunan sisinya merupakan himpunan kosong.
1
2 4
3
5
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 14. 4
5 Derajat (Degree)
Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut. Notasi: ()
1
2 4
3
5 1 = 3 = 2 4 = 3 2 = 4 5 = 1
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 15. 5
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
2 4
3
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 16. 6
7 Siklus (Cycle) atau Sirkuit (Circuit)
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.
1
2 4
3
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 17. 7
8 Terhubung (Connected)
Dua buah simpul 1 dan simpul 2 disebut terhubung jika terdapat lintasan dari 1 ke 2.
1
2
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 18. 8
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 2adalah himpunan simpul yang anggota-anggota 2 bersisian dengannya.
Gambar 19. 9: upagraf Gambar 20. 10: Komplemen
OUTLINE 5. TERMINOLOGI GRAF
ILHAM SAIFUDIN TI TEORI GRAF
Gambar 21. 11
10 Graf Berbobot (Weighted Graph)
Graf berbobotadalah graf yang setiap sisinya diberi sebuah harga (bobot).
2
5
4
1
3
OUTLINE TUGAS
ILHAM SAIFUDIN TI TEORI GRAF
TUGAS INDIVIDU
SEBUT DAN JELASKAN MACAM-MACAM GRAF KHUSUS DAN HASIL OPERASI PADA GRAF !
TERIMAKASIH
OUTLINE
ILHAM SAIFUDIN TI TEORI GRAF