PODSTAWOWE POJĘCIA TEORII GRAFÓW
Definicja grafu
Z matematycznego punktu widzenia grafy, ściślej grafy zorientowane lub orgrafy, są obiektami abstrakcyjnymi, opisanymi jako systemy algebraiczne, stanowiące trójki uporządkowane:
G = <W,U,P>,
przy czym W-jest przeliczalnym zbiorem elementów zwanych węzłami (wierzchołkami) grafu, U-zbiorem jego gałęzi a P-relacją trójczłonową (P⊂WxUxW) spełniającą warunki:
a) dla każdej gałęzi u∈U istnieje taka para wierzchołków <x,y>∈W, że <x,u,y> ∈ P;
jeżeli dla pewnej gałęzi u∈U istnieją <x,u,y>∈P oraz <y,u,z>∈P, to albo x=v i y=z tub x=z i y=v.
Szczególnym przypadkiem relacji P jest relacja, w której każdej gałęzi u odpowiada wzajemnie jednoznacznie jedna para uporządkowana <x,y>∈WxW taka, że <x,u,y>∈P. Wtedy para uporządkowana <x,y> określa jednoznacznie tę gałąź u i zbiór U jest izomorficzny z relacją dwuczłonową R ⊂ WxW, określoną rozważanym grafem. Takie grafy można zapisywać w postaci dwójki uporządkowanej
G=<W,U>