NOWA MATeMAtyka 2. Zakres podstawowy i rozszerzony — strona 260

Graf $G=(V,E)$ składa się ze zbioru wierzchołków $V$ i zbioru krawędzi $E$, które opisują połączenia między wierzchołkami. W grafie nieskierowanym krawędź nie ma kierunku, a w grafie skierowanym jest uporządkowanym łukiem od jednego wierzchołka do drugiego. Krawędziom można też przypisać wagi, na przykład długości dróg lub koszty przejazdu.

Podstawowe pojęcia teorii grafów to:

• stopień wierzchołka — liczba końców krawędzi przy tym wierzchołku;
• droga — ciąg kolejnych wierzchołków połączonych krawędziami;
• cykl — droga zamknięta;
• graf spójny — graf, w którym między każdą parą wierzchołków istnieje droga;
• graf eulerowski — graf spójny mający zamknięty spacer przechodzący każdą krawędzią dokładnie raz;
• graf hamiltonowski — graf mający cykl przechodzący przez każdy wierzchołek dokładnie raz.

W grafie nieskierowanym suma stopni wszystkich wierzchołków jest dwa razy większa od liczby krawędzi:

$$\sum_{v\in V}\deg(v)=2|E|.$$

Graf mostów królewieckich jest spójnym multigrafem nieskierowanym: może mieć kilka krawędzi łączących tę samą parę wierzchołków. Jego stopnie to $5,3,3,3$, więc wszystkie cztery wierzchołki mają stopień nieparzysty. Nie istnieje w nim ani cykl Eulera, ani droga Eulera.

Graf półeulerowski to spójny graf, w którym istnieje droga Eulera, czyli otwarty spacer wykorzystujący każdą krawędź dokładnie jeden raz, ale nie istnieje cykl Eulera.

Dla skończonego grafu nieskierowanego zachodzi następujące kryterium:

• graf jest eulerowski wtedy i tylko wtedy, gdy wszystkie jego wierzchołki mają stopnie parzyste;
• graf jest półeulerowski wtedy i tylko wtedy, gdy dokładnie dwa wierzchołki mają stopnie nieparzyste.

Droga Eulera w grafie półeulerowskim musi zaczynać się w jednym wierzchołku stopnia nieparzystego i kończyć w drugim. Każdy wierzchołek pośredni jest odwiedzany krawędziami w parach: jedną krawędzią wchodzimy i jedną wychodzimy.

Graf mostów królewieckich ma cztery wierzchołki stopnia nieparzystego, dlatego nie jest ani eulerowski, ani półeulerowski.