Teori Graph

Posted on August 3, 2009. Filed under: Diagram Jaringan, Teori GRAPH | Tags: Diagram Jaringan, Map Region, Teori Euler, Teori GRAPH |

Graph biasa kita mengenal pada saat mata kuliah teori graph sendiri dan matematika diskrit, disini saya akan menjelaskan tentang graph itu sendiri
Graph adalah himpunan V yang elemennya disebut vertex/point/node/titik, dimana himpunan E merupakan pasangan terurut dari vertex-vertex yang biasa disebut edge.

Selain Graph kita juga mengenal multigraph dimana multigraph adalah suatu graph yang tak mengandung edge sejajar ataupun self-loop.

Mari kita liat derajat dan keterhubungan MultiGraph.

Derajat Multigraph

Derajat vertex V ditulis d(V) adalah banyaknya edge yang menghubungi V tersebut
Jumlah derajat semua vertex suatu graph = 2x jumlah edge (Garis) graph

Keterhubungan Multigraph

Walk –> sederatan vertex dan edge berganti-gantu, V1, e1,V2,e2,………,Vn, en dimana masing-masing edge en menghubungkan vertex Vn dan Vn+1
Trail –> Walk dimana semua edge (didalam deretan) berbeda
Path –> Suatu trail yang semua vertexnya (didalam deretan) berbeda

Teori EULER

Suatu multigraph berhingga dan terhubung adalah eulerian jika dan hanya jika derajat setiap vertexnya genap.

Multigraph bisa dikatakan euler jika suatu graph yang hanya memiliki trail

Formula EULER

V – E + R = 2

Ket :

V = Vertex

E = Edge

R = Region

MAP REGION

Map adalah terhubung kalau graph yang bersangkutan terhubung.

Map Ragion adalah Map akan membagi-bagi bidang rata atas beberapa region/daerah.

Theorema : Jumlah derajat dari semua region suatu map = 2x jumlah edge graph yang bersangkutan.

Gambar 1. Graph

cara menghitung derajat vertex

Gambar 2. Region Graph

d(r1) = 2

d(r2) = 2

d(r3) = 2

d(r4) = 2

Representatif planar grap dari Graph, maka

Suatu region dari m, berderajat satu hanya jika batasnya self loop.
Suatu region dari m dapat mempunyai serajat 2 jika batsnya mengandung 2 edge sejajar

Theorema : G adalah planar graph terhubung , dengan P(vertex), E(edge) dimana P>=3 maka q = 3p-6