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