Teoria grafów
Pojęcie grafu jest bardzo proste:
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:
W naszym MiNIwykładzie najczęściej będziemy zajmować się grafami prostymi, czyli grafami nieskierowanymi bez wielokrotnych krawędzi, pętli, wag, etykiet:
Zapraszamy do przeczytania naszego MiNIwykładu i zapoznania się z najciekawszymi problemami rozwiązywanymi za pomocą grafów, wybranymi definicjami i przykładami interesujących rodzin grafów.
- Jak to się zaczęło - czyli mosty królewieckie [ wejdź ]
- Problemy i algorytmy grafowe[ wejdź ]
- Ważniejsze definicje[ wejdź ]
- Przykłady grafów o ciekawych własnościach[ wejdź ]
[ Początek strony ] [ MiNIWykłady ]