graf Eulera

graf Eulera, graf jednobieżny, graf unikursalny,

mat. graf, który ma drogę zamkniętą, zawierającą każdą krawędź dokładnie raz (cykl Eulera); znaczy to, że rysunek grafu Eulera można sporządzić bez odrywania ołówka od papieru, przechodząc każdą linię tylko raz;

1736 L. Euler opublikował pracę, która zapoczątkowała teorię grafów; przedstawił w niej problem mostów królewieckich: czy można tak zaplanować spacer po Królewcu, by przejść po każdym z 7 mostów (na rzece Pregoła) dokładnie raz; zagadka Eulera ma negatywne rozwiązanie — spójny graf jest grafem Eulera wtedy i tylko wtedy, gdy w każdym jego wierzchołku spotyka się parzysta liczba krawędzi.

Grafów teoria. Plan mostów królewieckich (ilustracja zamieszczona w artykule L. Eulera) i odpowiadający mu graf; zadanie postawione przez L. Eulera: czy można tak zaplanować spacer po Królewcu, by przejść po każdym z mostów na rzece dokładnie raz i powrócić do miejsca, z którego się wyszło?