Čo je to graf?

Každý graf sa skladá z dvoch zložiek (z formálneho hľadiska sú to dve množiny):

• Množina vrcholov. Vrcholy môžu byť v princípe ľubovoľné objekty a z matematického hľadiska nás veľmi nezaujíma, čo presne reprezentujú. Na obrázkoch ich zvykneme kresliť ako bodky, alebo krúžky. Množina vrcholov musí byť neprázdna a konečná (teda každý graf obsahuje jeden alebo viac vrcholov, ale musí ich obsahovať konečný počet). Množinu vrcholov zvykneme značiť $V$ (z anglického vertex) a ich počet zvykneme značiť $N$.
• Množina hrán. Hrany spájajú dvojice vrcholov (z formálneho hľadiska hrany sú dvojice vrcholov). Na obrázkoch ich zvykneme kresliť ako čiary spájajúce vrcholy. Množinu hrán zvykneme značiť $E$ (z anglického edge ) a môže byť aj prázdna. Počet hrán zvykneme značiť $M$.

Príklad grafu môžete vidieť na obrázku. Jeho vrcholy sú 1, 2, 3, 4 a 5, hrany sú 1-2, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5 a 4-5.