8.GRAPH (GRAF)
GRAPH
.jpeg)
• Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.
• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.
Istilah pada graph
Incident
Jika
e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w),
maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.
Degree (derajat), indegree dan outdegree
Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.
Indegree sebuah simpul pada graph berarah adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.
Outdegree sebuah simpul pada graph berarah adalah jumlah busur yang ekornya incident dengan simpul tersebut,
atau jumlah busur yang “keluar” atau 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 yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.
Define simpul untuk vertex dan edge
Mengidentifikasi Simpul pertama
sebagai vertex yang pertama
Tambahkan vertex sisanya
Tambahkan edge pada masing-masing vertex
yang telah terbentuk
Tampilkan representasi graph berikut
bobotnya
GRAPH vs TREE
Sebuah Graph memiliki ciri berbeda dengan
Tree
Dalam Graph, edge bebas menghubungkan
node-node mana pun.
Dalam Tree, satu node hanya boleh terhubung
ke satu parent dan beberapa child, tidak boleh ke beberapa parent.
Dalam sebuah Graph bisa dirunut jalur edge
yang membentuk jalur putaran dari 1 node kembali ke node semula; ini tidak
boleh terjadi dalam Tree
SPANNING TREE
Spanning Tree adalah sebuah Tree yang
dibuat dari sebuah Graph dengan menghilangkan beberapa edge-nya. Tree ini harus
mengandung semua node yang dimiliki Graph.
MINIMUM SPANNING TREE
Jika Weighted Graph diubah menjadi Spanning
Tree, tiap kombinasi Tree yang dapat dibuat memiliki total weight yang
berbeda-beda.
Problem Minimum Spanning Tree (MST)
berusaha mencari Tree seperti apa yang bisa dibuat dari sebuah Weighted Graph
dengan total weight seminimal mungkin.
ALGORITMA PRIM-DIJKSTRA
Langkah-langkah algoritma Prim-Dijkstra :
Tentukan node awal, asumsikan semua edge
berwarna hitam
Dari semua edge yang terhubung ke node awal
tersebut, pilih edge dengan bobot terkecil
Tandai edge yang dipilih dengan warna hijau
Apabila ada edge yang kedua node-nya sudah
terkena jalur hijau, tandai edge tersebut dengan warna merah (karena jika
dipilih akan membentuk jalur putaran à melanggar syarat tree)
Tentukan node-node yang berada di jalur
hijau sebagai node aktif
Bandingkan semua edge yang terhubung ke
node aktif (hanya edge hitam), pilih yang bobotnya terkecil
Tandai edge yang dipilih dengan warna hijau
Ulangi dari langkah ke-4 hingga semua node
terlewati jalur hijau
Ketika semua node telah dilewati jalur
hijau, maka jalur hijau yang terbentuk adalah MST yang dicari
ALGORITMA KRUSKAL
Langkah-langkah algoritma Kruskal :
Asumsikan semua edge berwarna hitam
Bandingkan bobot semua edge hitam, pilih
edge dengan bobot terkecil
Tandai edge yang dipilih dengan warna hijau
Apabila ada edge yang kedua node-nya sudah
terkena jalur hijau, tandai edge tersebut dengan warna merah (karena jika
dipilih akan membentuk jalur putaran à melanggar syarat tree)
Ulangi dari langkah ke-2 hingga semua node
terlewati jalur hijau
Ketika semua node telah dilewati jalur hijau, maka jalur hijau yang terbentuk adalah MST yang dicari
Komentar
Posting Komentar