TEORIA GRAFÓW

Graf to zbiór wierzchołków, który na rysunku zwykle reprezentujemy kropkami, na przykład:

oraz krawędzi łączących wierzchołki, co na rysunku można przedstawić następująco:

Czasem dopuszcza się wielokrotne krawędzie i pętle (czyli krawędzie o początku i końcu w tym samym wierzchołku):

Niekiedy wygodnie jest rozważać grafy o krawędziach skierowanych (grafy skierowane):

Wiele zastosowań mają grafy ważone, w których każdej krawędzi przyporządkowano liczbę - wagę, może ona oznaczać na przykład odległość między wierzchołkami:

W grafach etykietowanych każdy wierzchołek ma swoją nazwę - etykietę:

Tak więc grafy, o których uczy się w szkole podstawowej, to grafy skierowane, ważone, o zaetykietowanych wierzchołkach:

Należy pamiętać, że rysunek grafu to tylko jedna z wielu jego reprezentacji graficznych. Każdy graf można narysować na wiele sposobów. Oto kilka reprezentacji graficznych tego samego grafu: