7. PENGANTAR TEORI GRAF

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



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.




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



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.




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=




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)).




7. PENGANTAR TEORI GRAF (Cont) Connected Graph (Graph yang Terhubung):

Connected Graph

Totally not Connected Graph


Graph Lengkap (Complete Graph)



7. PENGANTAR TEORI GRAF (Cont) Tree atau Pohon Tree  Sebuah Connected Graph yang Acyclic. Acyclic adalah graph terhubung yang tidak ada cyclenya.



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



7. PENGANTAR TEORI GRAF

Recommend Documents