Matematika Diskrit

Jenis-jenis graph

Pendahuluan:

Istilah 'gelang pada' graf adalah, sisi yang menghubungkan suatu titik/vertex dengan dirinya sendiri.

Contoh graf yang memiliki gelang:

Istilah 'sisi ganda' pada graf ditujukan kepada graf yang memiliki lebih dari satu sisi yang menghubungkan dua buah titik.

Contoh graf yang memiliki sisi ganda:

Jenis Graf berdasarkan karakteristik

Graf memiliki karakteristik berdasarkan hal-hal berikut :

1. Keberadaan gelang dan sisi ganda pada graf,
2. Keberhinggaan jumlah sisi pada graf, dan
3. keberadaan orientasi arah.

Jenis	Sisi	Sisi ganda dibolehkan	Sisi gelang dibolehkan
Graf Sederhana (Simple Graf)	tak-berarah	tidak	tidak
Graf Ganda (multi graf)	tak-berarah	Ya	tidak
Graf semu (pseudo graph)	tak-berarah	Ya	Ya
Graf berarah sederhana	Berarah	tidak	tidak
Graf berarah ganda	Berarah	Ya	Ya
Graf Campuran	Berarah dan tak-berarah	Ya	Ya

Graf sederhana (simple graph) :

Tidak memiliki orientasi arah,

Tidak memiliki gelang

Tidak memiliki sisi ganda

Graf ganda (multi graph):

Graf semu (pseudo graph):

Graf berarah sederhana (directed graph) :

Graf berarah ganda (multi directed graph) :

Graf Campuran

Contoh Penerapan Graf

• Graf merepresentasikan Rangkaian Listrik
  • 
• Graf merepresentasikan Interaksi Protein
  • 
• Isomer senyawa Kimia karbon
  •