G = (V, E)
V : himpunan tidak kosong dari simpul-simpul
E : himpunan sisi (edge) yang menghubungkan sepasang simpul
Terdapat 2 kategori graf :
1. Directed graph (Graf berarah), seperti G3.
2. Undirected graph (Graf tidak berarah), seperti G1 dan G2.
Pada graf tersebut dapat didefinisikan himpunan vertex dan himpunan edge sebagai berikut:
V(G1) = {1, 2, 3, 4} E(G1) = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}
V(G2) = {1, 2, 3, 4, 5, 6, 7} E(G2) = {(1,2), (1,3), (2,4), (2,5), (3,6), (3,7)}
V(G3) = {1, 2, 3} E(G3) = {(1,2), (2,1), (2,3)}
Terminologi Graf
1. Adjacent (Ketetanggaan)
Dua simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau G1 : Simpul 1 bertetangga dengan simpul 2 dan 3
Simpul 1 tidak bertetangga dengan simpul 4
2. Incidency (Bersisian)
Tinjau G1 : Sisi (2,3) bersisian dengan simpul 2 dan simpul 3
Sisi (2,4) bersisian dengan simpul 2 dan simpul 4
Sisi (1,2) tidak bersisian dengan simpul 4
3. Isolated Vertex (Simpul Terpencil)
Tinjau G3 : Simpul 5 adalah simpul terpencil
4. Degree (Derajat)
Degree suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Tinjau G1 : d(1) = d(4) = 2
d(2) = d(3) = 3
Tinjau G2 : d(1) = 3 → bersisian dengan sisi ganda
d(4) = 1 → bersisian dengan sisi gelang (loop)
Tinjau G3 : d(5) = 0 → simpul terpencil
Pada graf tak berbobot, minimum spanning tree adalah jalur dengan jumlah edge minimum sehingga semua vertex bisa dicapai.
Pada graf ABCDE terdapat 10 jaring yang menghubungkan kelima vertex, namun sebenarnya dibutuhkan hanya 4 jaring untuk mengunjungi setiap vertex yang ada pada graf tersebut, yaitu AB BC CD DE. Jalur minimum inilah yang disebut sebagai minimum spanning tree.
E = V - 1
Sehingga bila ada 5 vertex maka hanya dibutuhkan 4 edge untuk menghubungkan semua vertex tersebut.
Algoritma Djikstra
Algoritma djikstra adalah algoritma untuk mencari jalur terpendek dari vertex awal ke vertex akhir.
Jalur terpendek : A - B - F - C - H dengan jarak 60.
No comments:
Post a Comment