Sabtu, 25 Mei 2013

Graph


Definisi Graph

Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :

G = (V, E)
Dimana :  
G = Graph
V = Simpul atau Vertex, atau Node
E = Busur atau Edge, atau arc

Sifat-Sifat Graph

žSebuah graph mungkin hanya terdiri dari satu simpul
 
 
 
 
 
žSebuah graph belum tentu semua simpulnya terhubung dengan busur
 
  
ž
žSebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain 
 
 
 
žSebuah graph mungkin semua simpulnya saling berhubungan
 
  
 
Contoh Graph
 
 


V terdiri dari V1, V2, V3 .....,V5 
E terdiri dari e1, e2, e3, .....,e5
Dimana :
V = Vertex
E = Edge
 
 
Istilah-Istilah dalam Graph
 
žIncident
  Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebutterletakpada e, dan e disebut incident dengan v dan w.

žDegree
  Degree dari suatu verteks x dalam undigraph adalah jumlah busur yang incident dengan simpul tersebut.
 
žIndegree
  Indegree dari suatu verteks x dalam digraph adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masukatau menuju simpul tersebut.
 
žOut Degree
  Outdegree dari suatu verteks x dalam digraph adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluaratau berasal dari simpul tersebut.
 
žAdjacent
      Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang  menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.
 
     Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.



žSuccessor dan Predecessor
  Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.

žPath
  Sebuah path adalah serangkaian simpul-simpul berbeda yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.
 Representasi Graph dalam Matrik
 
 



    Kotak yang berisi angka satu menunjukan bahwa dalam dua vertex tersebut terdapat edge yang menghubungkannya. Dan jika dalam kotak terdapat angka nol, maka hal tersebut menandakan tidak ada edge yang mengubungkan secara langsung dua vertex tersebut.

 
    Pada Weighted Direct Graph, penulisan matrix tidak menggunakan angka no 1 dan 0 lagi, melainkan menggunakan nilai (bobot) jika ada edge yang menghubungkan dua buah verterx dan nilai 0 jika tidak ada edge yang menghubungkan vertex - vertex tersebut.
 
 
Jenis-Jenis Graph
 
Derected Graph
 
Sebuah Graph yang sisi atau busurnya berlaku satu arah saja, sesuai dengan arah tanda panah.
Misal :
e1 = (A,B)
Berarti hanya berlaku untuk Graph A ke B saja, tidak berlaku
Untuk B ke A
 
 
 
 
 
 
 
 
 
 
Undirect Graph
 
Graph yang sisi atau busurnya bisa berlaku ke dua Arah. Secara Grafik dapat dilihat tidak ada arah panah pada Busur.
Edge pada Undigraph bisa direpresentasikan sebagai garis dengan panah 2 arah.
Misal :
e1 = (A,B)
e1 = Bisa dikatakan Graph A ke B atau Graph B ke A
 
 
 
Weighted Graph



ž
  
 
 
Weighted Graph adalah Graph yang sisi / busurnya memiliki nilai (bobot). Weighted Graph terdiri dua jenis :
  - Weighted Direct Graph
          Bobot berlaku satu arah saja
  - Weighted Undirect Graph
Bobot Berlaku 2 arah

Metode Pencarian Vertex
 
Depth first search (DFS)
 
žPencarian dengan metode ini dilakukan dari node awal secara mendalam   hingga yang paling akhir (dead-end) atau sampai ditemukan
  
 
 
žKelebihan :
  - Cepat Mencapai kedalaman ruang pencarian
  - Tidak boros waktu, jika lintasannya panjang
  - Lebih efisien
žKekurangan
  - Memungkinkan tidak ditemukan tujuan yang di harapkan
  - Pada setiap pencarian hanya menghasilkan 1 solusi saja
ž
BREADTH FIRST SEARCH (BFS)

žProsedur Breadth First Search merupakan pencarian yang dilakukan dengan mengunjungi tiap-tiap node secara sistematis pada setiap  level  hingga  keadaan tujuan (goal  state) ditemukan.
 
 
 
žKelebihan
  - Tidak akan menemukan jalan Buntu
  - Jika lebih dari solusi, maka BFS akan solusi minimum akan ditemukan
žKekurangan
  - Menyimpan memori yang besar karena menyimpan semua node yang ada dalam satuatu pohon. 

 
 
 Minimmum Spanning Tree

žSpanning Tree adalah sebuah cabang yang terbentuk dari subset edge-edge serta menghubungkan setiap vertex dalam suatu Graph.
ž
žMinimum Spanning Tree adalah total bobot minimal dari edge-edge yang menghubungkan setiap vertex.
 
žAlgoritma MST :
  1. Algoritma Kruskal
  2. Algoritma Prim

žContoh Minimum Spanning Tree
  Unweighted Undirect Graph
 
Kemungkinan MST


GRAPH pada JAVA

žUntuk pengaplikasian teori Graph dapat di lakukan pada program Java.  
Software yang kita gunakan pada Program yang kita buat adalah Eclipse žUntuk pengaplikasian teori Graph dapat di lakukan pada program Java.
Software yang kita gunakan pada Program yang kita buat adalah Eclipse.

žPada Package GRAPH_BASIC
  Terdapat 5 file berextensi .java yang saling berhubungan.

 

Untuk melakukan Logika pada package GRAPH_BASIC
terdapat pada file main.java


Output yang di hasilkan akan seperti di Bawah ini

 


Referensi:
http://gallerycode.files.wordpress.com/2010/11/graph1.pptx 
 

1 komentar: