Teori Graph

Posted on Maret 20, 2013. 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

1. Walk –> sederatan vertex dan edge berganti-gantu, V1, e1,V2,e2,………,Vn, en dimana masing-masing edge en menghubungkan vertex Vn dan Vn+1
2. Trail –> Walk dimana semua edge (didalam deretan) berbeda
3. 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

1. Suatu region dari m, berderajat satu hanya jika batasnya self  loop.
2. 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