Graf (matematyka)

Zobacz też: inne znaczenia wyrazu „graf”.

Graf – podstawowy obiekt rozważań teorii grafów^[1][2] , struktura matematyczna służąca do przedstawiania i badania relacji między obiektami^[3] [4] . W uproszczeniu graf to zbiór wierzchołków, które mogą być połączone krawędziami w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków^[5].

Wierzchołki grafu mogą być numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektami^[6]. Wierzchołki należące do krawędzi nazywane są jej końcami^[7]. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie nazywany jest grafem skierowanym^[8] lub orgrafem^[9]. Krawędź grafu może posiadać wagę, to znaczy przypisaną liczbę, która określa na przykład odległość między wierzchołkami (jeśli np. graf jest reprezentacją połączeń między miastami)^[10]. W grafie skierowanym wagi mogą być zależne od kierunku przechodzenia przez krawędź (np. jeśli graf reprezentuje trud poruszania się po jakimś terenie, to droga pod górkę będzie miała przypisaną większą wagę niż z górki)^[11].

Za pierwszego teoretyka i badacza grafów uważa się^[12] szwajcarskiego matematyka i fizyka Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich. Pierwsze użycie określenia „graf” przypisywane jest Jamesowi Josephowi Sylvesterowi – matematykowi angielskiego pochodzenia^[13].