SOP wyk nr 15-Slajd18
Własności grafów
Rozważmy graf składający się z wierzchołków i łuków, rozumianych jako uporządkowane pary wierzchołków. Podstawą definiowania istotnych dla zakleszczenia własności jest osiągalność wierzchołków. Wierzchołek u jest osiągalny z wierzchołka v wtedy i tylko wtedy, gdy istnieje w grafie skierowanym ścieżka rozpoczynająca się w wierzchołku v a kończąca w wierzchołku u .
Cykl w grafie oznacza, że istnieje ścieżka rozpoczynająca się i kończąca w tym samym wierzchołku, czyli jakiś wierzchołek jest osiągalny z samego siebie.
Supeł w grafie oznacza podzbiór wierzchołków, w którym każdy wierzchołek jest osiągalny z każdego innego, a jednocześnie z żadnego z tych wierzchołków nie jest osiągalny wierzchołek poza supłem. Jak łatwo zauważyć, supeł implikuje cykl.
