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