Pengertian Graph

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.