Greetings picture quotes
MATRIKS PENYAJIAN GRAPH
==================================
Misalnya disajikan Graph G dalam Matriks ruas B ukuran (M x 2), maka setiap baris Matriks menyatakan ruas, misalnya baris (4 7) menyatakan ada ruas menghubungkan simpul 4 dan 7.

Matriks Adjacency dari Graph G, yaitu Matriks yang menghubungkan Vertex dengan Vertex, tanpa ruas sejajar adalah Matriks A berukuran (N x N) yang bersifat :
aij=
1 , bila ada ruas (Vi, Vj)
0, bila dalam hal lain.
------------------------------------------
Matriks Adjacency merupakan matriks simetri.
Untuk Graph dengan ruas sejajar, Matriks Adjacency didefinisikan sebagai berikut :
aij =
P, bila ada p buah ruas menghubungkan (Vi, Vj)(p>0)
0, bila dalam hal lain.
------------------------------------------
Matriks Incidence dari Graph G, yaitu Matriks yang menghubungkan Vertex dengan Edge, tanpa self-loop didefinisikan sebagai Matriks M berukuran (NXM) sebagai berikut :
mij =
1, bila ada ruas ej berujung di simpul Vi
0, dalam hal lain.
------------------------------------------
GRAPH TERARAH (DIRECTED GRAPH / DIGRAPH)
Graph terarah adalah Graph yang dapat menghubungkan V1 ke V2 saja (1 arah).
Maksimum jumlah busur dari n simpul adalah :
n ( n - 1 )
Suatu Graph Berarah (Directed Graph) D terdiri atas 2 himpunan :
1) Himpunan V, anggotanya disebut simpul.
2) Himpunan A, merupakan himpunan pasangan terurut, yang disebut ruas berarah atau arkus.

Contoh,
sebuah Graph Berarah D(V,A) dengan :
1. V mengandung 4 simpul, yaitu 1, 2, 3 dan 4
2. A mengandung 7 arkus, yaitu (1,4) ,(2,1), (2,1), (4,2), (2,3), (4,3) dan (2) Arkus (2,2) disebut gelung (self-loop), sedangkan arkus (2,1) muncul lebih dari satu kali, disebut arkus sejajar atau arkus berganda.

- Bila arkus suatu Graph Berarah menyatakan suatu bobot, maka Graph Berarah tersebut dinamakan jaringan / Network. Biasanya digunakan untuk menggambarkan situasi dinamis.

- Bila V’ himpunan bagian dari V serta A’ himpunan bagian dari A, dengan titik ujung anggota A’ terletak di dalam V’, maka dikatakan bahwa D’(V’,A’) adalah Graph bagian (Subgraph) dari D(V,A).
- Bila A’ mengandung semua arkus anggota A yang titik ujungnya anggota V’, maka dikatakan bahwa D’(V’,A’) adalah Graph Bagian yang dibentuk atau direntang oleh V’.
------------------------------------------
GRAPH TAK TERARAH (UNDIRECTED GRAPH)
Graph tak terarah adalah Graph yang menghubungkan 2 verteks V1 ke V2 dan V2 ke V1 (2 arah).
Bila verteks = n, maka Graph tak terarah komplit akan mempunyai busur edge sama dengan :
n ( n - 1 ) / 2
------------------------------------------
MINIMUM SPANNING TREE
Merupakan Spanning Tree yang mempunyai Bobot dan tidak mempunyai arah dengan hasil penjumlahan bobotnya adalah minimum.
------------------------------------------
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 di tinjau.
2. Breadth First Search (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.
Log in
Sign up
Subscribe (1)
Featured feeds