Grap Problem

Grap

Pendahuluan

Menurut Dasgupta dkk (2008), graph merupakan himpunan tak kosong titik-titik yang

disebut vertex (juga disebut dengan node) dan himpunan garis-garis yang

menghubungkan titik tersebut yang disebut dengan edge (juga disebut dengan arc,

sehingga dapat dinotasikan sebagai G(V,E). Vertex atau node pada graf dapat

dinomori dengan huruf, seperti a,b,c,d, ..., atau dengan bilangan asli 1,2,3, … atau

juga gabungan dengan keduanya. Sedangkan untuk edge atau arc yang

menghubungkan antara simpul u dan v dinyatakan dengan (u,v) atau dapat dinyatakan

dengan lambang e1,e2,e3, … dengan 1,2,3 adalah indeks. Dapat dikatakan bahwa jika e

merupakan sisi yang menghubungkan simpul u dengan v, maka e dapat ditulis sebagai

e = (u,v)

1 Rinal munir

2 Usu

Grap pada umumnya di gunakan untuk sebagai cara yang sederhana untuk memodelkan banyak jaringan,

sebuah jaringan adalah sebuah sistem yang melibatkan perpindahan, bisa perpindahan data, atau informasi

dapat dimodelkan ke dalam bentuk grap, dimana

Dalam memodelkan sebuah jaringan dengan graph,

simpul dalam graph umumnya dinyatakan dalam bentuk titik yang menyatakan asal

aliran serta tempat berakhir (contohnya, stasiun kereta api, terminal,Sebuah graph juga memberikan model struktural dari jaringan. Dalam

kebanyakan jaringan, metode konstruksi biasanya dinyatakan oleh harga, efisiensi,

kehandalan dan kapasitas.

jenis grap

berdasarkan arah dan bobot

grap yang setiap sisinya diberikan orientasi arah yang disebut dengan busur, dalam grap berarah menyatakan dua buah busur yang berbeda

Graph berarah dan berbobot sering digunakan untuk menggambarkan aliran proses,

peta lintas kota dan lain sebagainya.

berdasarkan  arah dan tidak berbobot

Merupakan graph yang mempunyai orientasi arah namun tidak mempunyai bobot

apapun

grap tidak berarah dan tidak berbobot