graf Eulera
 
Encyklopedia PWN
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.
Ilustracje
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?wyk. LogoScript/Archiwum Ilustracji WN PWN SA © Wydawnictwo Naukowe PWN
Przeglądaj encyklopedię
Przeglądaj tabele i zestawienia
Przeglądaj ilustracje i multimedia