Jumat, 13 Februari 2015

GRAPH

GRAPH

Graph adalah kumpulan titik (node) dan garis dimana pasangan-pasangan titik (node) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (verteks) dan segmen garis disebut ruas (edge).


Simpul dan ruas dalam graph dapat diperluas dengan penambahan informasi. Sebagai contoh, simpul bisa diberi nomor atau label dan ruas dapat diberi nilai juga. Perluasan dengan pemberian informasi ini sangat berguna dalam penggunaan graph untuk banyak aplikasi komputer. Contoh, graph dengan simpul yang mempresentasikan kota dan ruas mempresentasikan jarak yang ditempuhkan diantara kota-kota tsb. (atau harga tiket pesawat antara kota-kota tsb.)network” untuk mempelajari total jarak (atau harga) dari suatu perjalanan dengan banyak kota pemberhentian. Satu kemungkinan pertanyaan yang bisa muncul adalah “jalur mana yang terpendek dengan satu atau lebih tempat pemberhentian, yang menghubungkan kota tertentu menuju kota tertentu lainnya dalam transportation network tersebut ?”.



Kelahiran Teori Graph

Gbr1. Jembatan konigsberg
Menurut catatan sejarah, masalah jembatan konigsberg adalah masalah yang pertama kali menggunakan graph (th.1736). masalah jembatan konigsberg adalah “ apakah mungkin melalui tujuh buah jembatan masing-masing tepat satu kali. Dan kembali lagi ke tempat semula ?”. Tak seorang pun yang dapat memecahkan masalah ini. Barulah Euler yang pertama kali menemukan jawabannya. Ia memodelkan masalah dengan memodelkan ke dalam graph. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakan sebagai simpul (vertex) dan jembatan sebagai sisi. Graph dibuat oleh Euler diperlihatkan pada gambar dibawah atas.
Jawabannya adalah : orang tidak mungkin melalui ketujuh jembatan masing-masing satu kali dan kembali  ke tempat keberangkatan. Singkatnya, tidak terdapat siklus Euler pada graph tersebut.  Graph yang memenuhi kondisi diatas tersebut kemudian dikenal dengan nama Graph Eurel dan perjalanannya disebut perjalanan euler.
Perjalanan Euler adalah :
                Perjalanan  dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali. 


Definisi
  • Graph merupakan suatu koleksi dari himpunan VG dan EG. 

         Notasi : G       = { VG, EG}
                     G        = graph
                     VG      = himpunan titik (vertex graph) 
                     EG      = Himpunan garis (edge graph)
  • Titik   : node vortex 
  • Garis : Arc / edge
  • Contoh : Graph G terdiri dari :

    G       = { VG,EG}
    VG     = {a,b,c,d} 
    EG     ={1,2,3,4,5,6,7,8}
  • Edge 1 menghubungkan vertex a & b edge 1 = (a,b) 
  • Edge 2 menghubungkan vertex b & c edge 2 = (b,c) 
  • Edge 3 menghubungkan vertex c & b edge 3 = (b,c), dst
  • Jumlah vertex dalam suatu graph disebut ORDER dari graph tersebut.
  • Contoh : Graph G dengan order = 4 (jumlah vertex = 4 ; a,b,c,d) 
  • Suatu graph hanya ditentukan oleh vertex-vertex dan edge-edgenya. Posisi dari vertex-vertex dan edge-edge dalam penggambaran tidaklah penting. 
GRAPH EQUIVALEN :
Penggambaran yang sama


Suatu graph G disebut SIMPLE GRAPH, jika :

  • Tidak mempunyai edge yang SELF LOOP (tidak ada(V,V) dalam G) 
  • Tidak mempunyai MULTIPLE EDGE (hanya ada (Vi, Vj) dalam G)



MULTIPLE EDGE  adalah 1 vertex dihubungkan oleh beberapa edge.

Contoh :  pada gambar graph equivalen diatas, vertex b dihubungkan oleh edge-edge 1,2,3,5,6,7.

sedangkan vertex c dihubungkan oleh edge-edge 2,3,4

SELF LOOP adalah vertex yang dihubungkan oleh edge-edge menuju edge itu sendiri.

Contoh : pada gambar graph equivalen diatas, vertex a dihubungkan oleh edge 8 menuju a kembali.

Suatu  Graph G disebut CONNECTED (terhubung) jika Graph G dapat dipartisi (dibagi) menjadi 2 graph dengan menghapus paling sedikit 1 edge.

Contoh yang tidak connected :

suatu graph G terdiri dari G = { VG,EG}
                                             VG= {e,f,g,h} 
                                             EG= {1,2,3}
PATH adalah Graph adalah barisan dari 1 buah edge-edge yang menghubungkan 2 vertex.
  • Notasi :

P(Vi,Vj) = (Vi,X1) (X1,X2)(X2,Xn-1)(Xn-1,Xn)(Xn,Vj)
  • Dari gambar simple graph :

P (b,d) =               (b,c) (c,d)

P (b,d) =               (b,c) (c,b) (b,c) (c,d)

P (b,d) =               (b,d)

P (b,d) =               (b,c) (c,b) (b,d)

LENGTH  dari suatu path adalah jumlah edge-edge pada path tersebut.

CONTOH :   perhatikan gambar simple graph :
P (b,d)  = (b,d)                   length = 1
             = (b,c) (c,d)           length = 2
             = (b,c) (c,b) (b,d)  length = 3

CYCLE adalah path yang memenuhi syarat sebagai berikut: 
  • Tidak ada edge yang tampil lebih dari satu kali dalam barisan edge dari path tersebut
Contoh : gambar simple graph :
              P (b,d)  =  (b,c) (c,b) (b,d)
                 Tidak boleh
  • Path harus berbentuk P(V,V)
  • Tidak ada vertex yang dikunjungi lebih dari satu kali
Contoh : P(a,a) = (a,b) (b,c) (c,d) (d,b) (b,a) 
  B dikunjungi lebih dari 1x 
  P(a,a)    = (b,c) (c,b) (b,a) (a,c) (c,b) 
  c & b dikunjungi 3x 
contoh CYCLE : P(b,b) = (b,d) (d,c) (c,b


ACYCLIC adalah graph yang tidak mempunyai cycle.
Contoh : Graph  G terdiri dari :

              G  = {VG,EG}

              VG = {a,b,c,d}

              EG = { 1, 2,3}
Catatan :

  • Graph yang simple belum tentu graph yang Acyclic
  • Graph yang Acyclic adalah graph yang simple


Graph yang berarah disebut DI-GRAPH / DIRECTED GRAPH,  adalah merupakan graph dimana edge-edgenya mempunyai suatu arah.



Pada gambar : (a,b) => 1 arah
                       (b,a) => 0 arah
Graph yang tidak mempunyai arah boleh bolak-balik

Pada gambar : (a,b) => 1 arah
                       (b,a) => 0 arah

Vertex a mempunyai

  • OUT DEGREE (derajat luar) = N

Jika vertex a mempunyai N edge mengarah keluar.

Misal : vertex a mempunyai 2 edge mengarah ke luar (Gambar Digraph diatas)


  • IN DEGREE (derajat masuk) = N


Jika vertex a mempunyai N edge mengarah masuk (Gambar Digraph diatas)


  • DEGREE (derajat) = N


Jika Out Degree a ditambah In Degree a  = N
Misal : vertex b :    In degree          = 2
                              Out degree        = 3
                              Degree              = 5 

Contoh : pada gambar Digraph diatas :
                                  Degree (a) = 3
                                  Degree (b) = 5
                                  Degree (c) = 3
                                  Degree (d) = 5
                                                   = 16 

Graph G dengan himpunan vertex Vo dan edge Eo diasumsikan graph berorder N untuk N 1


Salah satu pendekatan untuk graph ini menggunakan matriks ADJACENCY dengan suatu Array A ukuran N x N .


  • A(i,j)      {   1 jika edge (Vi, Vj) Eij
                  0 jika edge (Vi, Vj) Eij
Contoh  Graph UNDIRECT / Matriks Simetris

 Contoh Graph DIRECT



Penggambaran Node DIRECTORY  

  • Penggambaran node dalam directory dibagi dalam 2 bagian :


  1. Directory
  2. Himpunan Link List (LL)


  • Setiap record dari Link List  mempunyai 2 field;


  1. Node Identifier
  2. Suatu Link yang menghubungkan elemen lain dari list (next)
NODE
NEXT
  • Directory menggambarkan banyak node
  • Link list menunjukkan edge-edgenya.




0 komentar:

Posting Komentar