Teori Graf The whole of mathema,cs consists in the organiza,on of a series of aids to the imagina,on in the process of reasoning.” – Alfred North Whitehead
Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
1
Struktur Graf • Simpul (vertex // verBces) • Sisi (edge // edges)
o Lintasan o Sirkuit
Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
2
Jenis Graf Graf (dak berarah dan graf berarah Misal suatu graf dengan: Himpunan simpul = {v1, v2, v3, v4, v5, v6} Himpunan sisi = {e1, e2, e3, e4, e5, e6, e7} Contoh fungsi sisi-‐endpoint
Contoh fungsi sisi-‐endpoint
Sisi
Endpoint
Sisi
Endpoint
e1
{v1, v2}
e1
(v1, v2)
e2
{v1, v3}
e2
(v1, v3)
e3
{v1, v3}
e3
(v1, v3)
e4
{v2, v3}
e4
(v2, v3)
e5
{v5, v6}
e5
(v5, v6)
e6
{v5}
e6
(v5)
e7
{v6}
e7
(v6) Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
3
Terminologi Graf • Bertetangga (adjacent) – Suatu simpul bertetangga dengan simpul yang dihubungkan dengan sisi yang sama – Suatu sisi bertetangga dengan sisi yang memiliki endpoint pada simpul yang sama
• Bersisian (incidentcy) – Suatu sisi bersisian dengan simpul yang menjadi endpoint-‐nya.
• Simpul terpencil (isolated vertex) Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
4
Graf Spesial • • • • • • •
Graf sederhana Graf Bdak sederhana Graf bipar,te lengkap Subgraf Cut set Graf berbobot …. dan sebagainya Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
5
Konsep Derajat Misal G adalah suatu graf dan v adalah simpul dari G. Derajat dari simpul v, dinotasikan dengan deg(v) adalah jumlah sisi yang bersisian dengan v, dimana suatu sisi yang membentuk loop dihitung dua kali. Derajat total dari G adalah jumlah derajat semua simpul pada G. Teorema Jabat Tangan: Jika G adalah suatu graf, maka jumlah derajat semua simpul pada G adalah dua kali jumlah sisi pada G. Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
6
Representasi Graf • Lis Ketetanggaan (adjacency list) • Matriks Ketetanggaan (adjacency matrix) • Matriks Bersisian (incidency matrix)
Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
7
Lis Ketetanggaan Tentukan lis ketetanggaan graf – graf berikut ini:
(i)
(ii)
Sumber: Kenneth H. Rosen – Discrete Mathema,cs and Its Applica,ons, 7th Ed Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
8
Matriks Ketetanggaan Tentukan matriks ketetanggaan graf – graf berikut ini:
(i)
(ii)
Sumber: Kenneth H. Rosen – Discrete Mathema,cs and Its Applica,ons, 7th Ed Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
9
Matriks Bersisian Tentukan matriks bersisian graf – graf berikut ini:
(i)
(ii)
Sumber: Kenneth H. Rosen – Discrete Mathema,cs and Its Applica,ons, 7th Ed Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
10
Keterhubungan Misal G adalah suatu graf. Dua simpul v dan w pada G dikatakan terhubung jika dan hanya jika ada lintasan dari v ke w. Graf G dikatakan terhubung jika dan hanya jika diberikan sembarang simpul v dan w pada G, maka ada lintasan dari v ke w.
Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
11
Contoh Graf Terhubung dan Tidak Terhubung
Sumber: Kenneth H. Rosen – Discrete Mathema,cs and Its Applica,ons, 7th Ed Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
12
Sirkuit Euler Misal G adalah suatu graf. Sirkuit Euler pada G adalah sirkuit yang memuat semua simpul dan semua sisi pada G. Pada sirkuit Euler, semua simpul dikunjungi minimal satu kali, sedangkan semua sisi dilewaB tepat satu kali saja. Teorema: 1. Jika suatu graf memiliki sirkuit Euler, maka semua simpulnya memiliki derajat berupa bilangan genap posiBf. 2. Jika suatu graf terhubung dan semua simpulnya memiliki derajat berupa bilangan genap posiBf, maka graf tersebut memiliki sirkuit Euler. Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
13
Contoh Sirkuit Euler
Sumber: Susanna S. Epp – Discrete Mathema,cs with Applica,ons 4th Ed. Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
14
Sirkuit Hamiltonian Misal G adalah suatu graf. Sirkuit Hamilton pada G adalah sirkuit sederhana yang melewaB semua simpul pada G. Pada sirkuit Hamilton, semua simpul hanya dikunjungi tepat satu kali saja, kecuai simpul awal dan akhir.
Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
15
Contoh Sirkuit Hamiltonian
Sirkuit Hamiltonian ditandai dengan garis berwarna hitam Sumber: Susanna S. Epp – Discrete Mathema,cs with Applica,ons 4th Ed. Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
16
Graf Isomorfik Dua buah graf, G dan G’ dikatakan isomorfik jika terdapat korespondensi satu-‐satu antara simpul-‐simpul keduanya dan antara sisi-‐sisi keduanya sedemikian sehingga jika sisi e bersisian dengan simpul u dan v di G, maka sisi e’ yang berkorespon di G’ juga harus bersisian dengan simpul u’ dan v’. -‐ Rinaldi Munir
Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
17
Contoh Graf Isomorfik
Sumber: Susanna S. Epp – Discrete Mathema,cs with Applica,ons 4th Ed. Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
18
Referensi Susanna S .Epp. Discrete Mathema-cs with Applica-ons 4th Ed. Kenneth H. Rosen. Discrete Mathema-cs and Its Applica-ons 7th Ed. Rinaldi Munir. Matema-ka Diskrit edisi ke-ga. Matema(ka Komputasi -‐ Teori Graf Agi Putra Kharisma, ST., MT.
19
