Teori Graph

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

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

Make a Comment

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

4 Responses to “Teori Graph”

RSS Feed for Anita Megayanti 332208595 Blog's Comments RSS Feed

apa multigraph sama dengan graph multipartit?

beda…tetapi graph multi partisi merupakan bagian dari multigraph……

Siiiiiiiip….LAnjutkan…

kalo graph multipartit itu apa sih sebenarnya????


Where's The Comment Form?

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

%d bloggers like this: