Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1.Podstawowepojęciagrafów
5
Rys.1.4.ProblemEuleramostówkrólewieckich
zgodnieztradycjąrównieżprzedstawimyproblemmostówkrólewieckich,zwłasz-
czażebędzietointuicyjnymwprowadzeniemdorozdziału7omawiającegotzw.
grafyEulera.
PrzezznacznączęśćswojegożyciaEulerpracowałwKönigsberg(Królewcu,
Kaliningradzie).Wmieścietymznajdowałsiępark,doktóregoEulerchodziłnaspa-
cery.PrzezparkpłynęłarzekaPregoła,ananiejbyłydwiewyspyisiedemmostów.
Rysunek1.4aschematycznieprzedstawiasytuacjętopograficznąmiejsca.Eulerspa-
cerując,zadałsobiepytanie,czystartujączdowolnegopunktu,możnatakzaprojek-
towaćtrasęspaceru,abyprzejśćprzezwszystkiemosty,przekraczająckażdyznich
dokładniejedenraz.ZadanieEuleramożnałatwosformułowaćjakoproblemgrafowy.
Narysunku1.4bjestprzedstawionymodelgrafowyproblemu.Wierzchołkigrafuod-
powiadajączęściomlądowymparku,akrawędziereprezentująmosty.Możnałatwo
stwierdzić,żeodpowiedźjestnegatywna.W1736rokuEuleruogólniłirozwiązał
problemmostówkrólewieckichdladowolnychgrafów[1.2].Grafy,wktórychistnieje
drogazamkniętaspełniającaomówionewarunki,nosząnazwęgrafówEulera.Graf
pokazanynarys.1.4bjestgrafemważonym.Wagimożnainterpretowaćnp.jakodłu-
gościodcinkówdrogi.
