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 Gambar 1. Graph 


cara menghitung derajat vertex

Gambar 2. Region Graph 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Liked it here?
Why not try sites on the blogroll...

%d bloggers like this: