Grafikoni i mrežeKönigsberški mostovi
Jedan od prvih matematičara koji je razmišljao o grafovima i mrežama bio je
Rijeka Pregel dijeli Königsberg na četiri odvojena dijela koji su povezani sedam mostova. Je li moguće hodati gradom prelazeći sve mostove točno jednom - ali ne više od jednom? (Možete započeti i završiti bilo gdje, ne nužno na istom mjestu.)
Pokušajte pronaći valjanu rutu crtanjem na ovim mapama:
Map 1
Map 2
Map 3
Map 4
U slučaju Königsberga čini se da je nemoguće pronaći valjanu rutu, ali neki drugi gradovi djeluju. Euler je uspio pronaći jednostavno pravilo koje se može primijeniti u bilo kojem gradu, bez da je isprobao puno mogućnosti - koristeći teoriju grafova.
Prvo moramo pretvoriti karte gradova u grafikone s rubovima i vrhovima. Svaki otok ili područje kopna predstavljen je
Sada je problem "obilaska grada dok je prešao svaki most točno jedanput" postao problem "crtanja grafa jednim kontinuiranim kretom, istodobno pronalazeći svaki rub točno jedanput".
Na papiru smislite nekoliko različitih grafova, a zatim pokušajte utvrditi koji se mogu izvući jednim kontinuiranim taktom.
Baš kao i prije na kartama grada, utvrdili smo da su neki grafovi mogući, dok drugi nisu. Da bismo lakše razumjeli zašto, označimo svaku vršku s
Uspoređujući ove brojeve za moguće grafikone i one koji nisu mogući, čini se da se graf može izvući ako
Ako se vratite na kartu Königsberga, vidjet ćete da postoji više od dva otoka s neparnim brojem mostova. Stoga je ruta koja točno jednom prelazi svaki most zaista nemoguća - a to je otkrio Leonard Euler. Eulerovo otkriće možda se ne čini osobito korisnim u stvarnom životu, ali grafovi su temelj mnogih drugih geografskih problema, poput pronalaženja uputa između dviju lokacija. Više tih aplikacija otkrit ćemo kasnije.