Pengertian graph adalah suatu alat bantu
untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek
tersebut. Graph G didefinisikan sebagai pasangan himpunan (V, E), ditulis
dengan notasi G = (V, E). V (node) merupakan merupakan himpunan tidak kosong
dari simpul. E (edge) merupakan himpunan sisi yang menghubungkan sepasang
simpul. Dan jika suatu edge berasal dari suatu simpul dan ujungnya kembali ke
simpul yang sama, maka edge tersebut dinamakan loop. Simpul pada graph umumnya
dinomori dengan huruf atau angka. Sedangkan sisi pada graph umumnya dinamai
dengan himpunan simpul yang dihubungkan oleh sisi tersebut .
Graph dapat dikelompokkan berdasarkan ada
tidaknya edge-nya yang paralel atau loop, jumlah node, berdasarkan ada tidaknya
arah pada edge-nya, atau ada tidaknya bobot pada edge-nya.
Berdasarkan ada tidaknya edge yang paralel
atau loop graph terdiri dari graph sederhana dan graph tak sederhana. Graph
sederhana adalah graph yang tidak memiliki sisi ganda dan juga loop. Sisi ganda
merupakan kondisi ketika dua buah simpul memiliki lebih dari satu sisi.
Sedangkan graph tak sederhana adalah graph yang memiliki sisi ganda dan atau
loop. Graph tak sederhana dapat dibagi dua, yaitu graph semu (pseudograph) dan
multiplegraph. Graph semu adalah graph yang mempunyai loop dan edge ganda
sedangkan multiplegraph adalah hanya mempunyai edge ganda.
Berdasarkan orientasi arah atau panah graph
dibedakan atas graph tak berarah dan graph berarah. Graph tak berarah adalah
graph yang edge-nya tidak mempunyai orientasi arah atau panah sedangkan graph
berarah adalah graph yang setiap sisinya memiliki orientasi arah dari suatu
simpul ke simpul lainnya.
Graph berbobot adalah graph yang memiliki
nilai pada setiap sisinya. Bobot pada setiap sisi dapat menyatakan jarak antara
dua buah kota, biaya perjalanan, waktu tempuh, ongkos produksi, dan sebagainya.
Tags
Fisika