BLOGGER TEMPLATES - TWITTER BACKGROUNDS

Jumat, 18 Juni 2010

MATRIKS PENYAJIAN GRAPH

Matriks Penyajian Graph
Matriks Adjacency dari Graph G, yaitu Matriks yang menghubungkan Vertex dengan Vertex, tanpa ruas sejajar adalah Matriks A berukuran (NxN).
Matriks Adjacency merupakan matriks simetri.
Matriks Incidence dari Graph, yaitu Matriks yang menghubungkan Vertex dengan edge, tanpa self-loop diefinisikan sebagai matriks M berukuran (NxM).

Graph Terarah (Directed Graph / Digraph)
Graph terarah adalah grap yang dapat menghubungkan V1 ke V2 saja (1 arah).
Maksimum jumlah busur dari n simpul adalah :



Graph Tak Terarah (Undirected Graph)
Graph tak terarah adalah graph yang menghubungkan 2 vertex V1 ke V2 dan V2 ke V1 (2 arah). Bila Vertex = n, maka Graph tak terarah komplit akan mempunyai busur edge sama dengan :


Penelusuran graph
Dapat dilakukan dengan 2 cara, yaitu :
1. Depth First Search (DFS)
Penelusuran dengan DFS pada graph tak berarah dengan melakukan pengecekan pada node dengan kedalaman pertama dari node yang ditinjau.
2. Breadh First Searh (BFS)
Berbeda dengan cara BFS, dengan BFS penelusuran akan diawasi dari node-1, kemudian melebar pada Adjacent Node dari Node-1 dan diteruskan pada Node-2, Node-3 dan seterusnya.

0 komentar: