Mata Kuliah Matematika Diskrit Fakultas Matematika dan Ilmu Pengetahuan Alam
Anny Kartika Sari, S.Si., M.Sc.
7. PENGANTAR TEORI GRAF Definisi : Secara umum merupakan kumpulan titik dan garis. Sebuah garf G terdiri dari: 1. Sebuah himpunan V=V(G) yang memiliki elemen2 yg dinamakan verteks/titik/node. 2. Sebuah kumpulan E=E(G) merupakan pasangan terurut dari titik2 berbeda yg dinamakan edge/sisi. Graf G dilambangkan G(V,E) Graf sederhana (graf): graf yg tdk memiliki sisi ganda dan loop. Multigraf (graf ganda): graf yang memiliki sisi ganda atau loop.
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada
Mata Kuliah Matematika Diskrit Fakultas Matematika dan Ilmu Pengetahuan Alam
Anny Kartika Sari, S.Si., M.Sc.
7. PENGANTAR TEORI GRAF Pengertian2: 1. Sisi Ganda: 2 atau lebih sisi yg menghubungkan 2 titik yg sama. 2. Kalang: sisi yg berpangkal dan berujung pd titik yg sama. 3. Walk: urutan titik dan garis (diawali dengan titik dan diakhiri titik). Garis boleh berulang. 4. Trail: walk yang semua sisinya berlainan. 5. Path: trail yang tidak mengulangi titik (semua titiknya berbeda) 6. Cycle: path yang tertutup (titiknya tidak boleh berulang). Minimal terdiri dari 3 garis. 7. Panjang: jumlah sisi pada walk. 8. Jarak : panjang path terpendek dari 2 titik d(u,v) 9. Derajat (deg(v)): jumlah sisi yg memuat v sbg titik ujung. 10. Diameter: jarak maksimum antara 2 titiknya.
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada
Mata Kuliah Matematika Diskrit Fakultas Matematika dan Ilmu Pengetahuan Alam
Anny Kartika Sari, S.Si., M.Sc.
7. PENGANTAR TEORI GRAF (Cont) Contoh dari Definisi-definisi tersebut:
x4
V4 x3 V1
V3
x5
x6
x1 V2
x2
V5
Path = V1 V2 V4 V3 Cycle = ada 3 cycle, yaitu : Cycle 1 =V2, V4, V3, V5 Cycle 2 = V2, V4, V3 Cycle 3 = V2, V5, V3 Jarak = V1 ke V3 adalah 2 Pusat Pengembangan Pendidikan - Universitas Gadjah Mada
Mata Kuliah Matematika Diskrit Fakultas Matematika dan Ilmu Pengetahuan Alam
Anny Kartika Sari, S.Si., M.Sc.
7. PENGANTAR TEORI GRAF
11. Subgraf: H (V’,E’) adalah subgraf dari G(V,E) jika V’ subset dari V dan E’ subset dari E. 12. Komponen terhubung: subgraf terhubung maksimal dari G 13. Subgraf G-v: subgraf G yg didapat dr menghapus titik v dari G dan sisi2 yg berujung di v. 14. Titik potong v: G-v menghasilkan G yg terhubung menjadi tidak terhubung. 15. Subgraf G-e: subgraf G yg didapat dr menghapus sisi e. 16. Jembatan e: G-e menghasilkan G yg terhubung menjadi tidak terhubung.
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada
Mata Kuliah Matematika Diskrit Fakultas Matematika dan Ilmu Pengetahuan Alam
Anny Kartika Sari, S.Si., M.Sc.
7. PENGANTAR TEORI GRAF (Cont) Contoh Sub Graph: Definisi Suatu graph, misal S = Subgraph dari G. Artinya semua titik di S ada di G dan semua garis di S ada di G.
S=
G=
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada
Mata Kuliah Matematika Diskrit Fakultas Matematika dan Ilmu Pengetahuan Alam
Anny Kartika Sari, S.Si., M.Sc.
7. PENGANTAR TEORI GRAF Beberapa macam graf khusus: 1. Graf terhubung: graf yg dari sembarang titiknya bisa ditemukan path ke titik yg lain. 2. Graf lengkap: graf yg setiap titiknya terhubung ke setiap titik lain (Kn). Jml sisi = (n(n-1)/2 3. Graf regular: graf yg setiap titiknya memiliki derajat yg sama (k-regular). 4. Tree : graf acyclic (graf yg tdk mempunyai cycle) dan terhubung memiliki paling sedikit 2 titik berderajat 1. 5. Graf berbobot: graf yg setiap sisi e dipetakan ke bilangan l(e) yg disebut bobot/panjang sisi e. 6. Graf berarah (directed graph): graf yg sisi-sisinya diberi arah ((u, v) ≠ (v, u)).
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada
Mata Kuliah Matematika Diskrit Fakultas Matematika dan Ilmu Pengetahuan Alam
Anny Kartika Sari, S.Si., M.Sc.
7. PENGANTAR TEORI GRAF (Cont) Connected Graph (Graph yang Terhubung):
Connected Graph
Totally not Connected Graph
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada
Graph Lengkap (Complete Graph)
Mata Kuliah Matematika Diskrit Fakultas Matematika dan Ilmu Pengetahuan Alam
Anny Kartika Sari, S.Si., M.Sc.
7. PENGANTAR TEORI GRAF (Cont) Tree atau Pohon Tree Sebuah Connected Graph yang Acyclic. Acyclic adalah graph terhubung yang tidak ada cyclenya.
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada
Mata Kuliah Matematika Diskrit Fakultas Matematika dan Ilmu Pengetahuan Alam
7. PENGANTAR TEORI GRAF
Matriks sbg representasi graf:
1. Matriks adjacency: A (aij) adalah matriks m x m dg aij = 1 jk (vi, vj) adalah sisi = 0 jk tidak 2. Matriks incident: M = (mij) adl matriks m x n dg mij = 1 jk titik vi incident pd sisi ej = 0, jk tdk 3. Matriks bobot: B (bij) adl matriks m x m dg bij = l(vi, vj) jk vi dan vj adjacent = ∞ jk tidak
Pusat Pengembangan Pendidikan - Universitas Gadjah Mada
Anny Kartika Sari, S.Si., M.Sc.