Graf (matematika)

Za grafični prikaz funkcije glej graf funkcije.

Gráf je v matematiki struktura in predstavlja abstraktno upodobitev množice objektov, v kateri so nekateri pari objektov povezani z vezmi. Medsebojno povezani objekti so upodobljeni z matematičnimi abstrakcijami, imenovanimi točke (ali tudi vozlišča), vezi, ki povezujejo nekatere pare točk, pa se imenujejo povezave. Običajno je graf prikazan v diagramski obliki kot množica pik za točke, ki jih povezujejo daljice ali krivulje za povezave.

Povezave so lahko usmerjene (asimetrične) ali neusmerjene (simetrične). Če na primer točke prikazujejo ljudi na zabavi, in med dvema človekoma, ki se rokujeta, obstaja povezava, je to neusmerjeni graf, saj, če se oseba A rokuje z osebo B, se tudi oseba B rokuje z osebo A. Če na drugi strani točke predstavljajo ljudi na zabavi, in obstaja povezava od osebe A do osebe B, če oseba A pozna osebo B, je to usmerjeni graf, saj poznavanje nekoga ni nujno simetrična relacija, oziroma, če ena oseba pozna drugo osebo, obratno nujno ne velja. Mnogo oboževalcev lahko pozna znano osebo, malo pa je verjetno, da bo znana oseba poznala vse svoje oboževalce. V takšnem usmerjenem grafu so povezave usmerjene in se imenujejo tudi loki.

Besedo »graf« je v tem smislu prvi rabil James Joseph Sylvester leta 1878.^[1]

Veja matematike in računalništva, ki raziskuje značilnosti grafov, se imenuje teorija grafov.

1. ↑ Gross; Yellen (2004), str. 35.