Promjena jezika

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Prijavite se u Mathigon

ili

Novi profil     Resetiranje lozinke     

Grafikoni i mreže
Uvod
Königsberški mostovi
Rukovanje i druženje
Ravni grafikoni
Bojanje karte
Problem putničkog prodavca
Problemi s planiranjem
Grafovi u svakodnevnom životu

Podijeli

Poništavanje napretka

Ovim ćete izbrisati podatke o napretku i chatu za sva poglavlja ovog tečaja i ne možete ih poništiti!

Riječnik

Odaberite jednu od ključnih riječi s lijeve strane ...

Grafikoni i mrežeKönigsberški mostovi

Vrijeme čitanja: ~20 min

Jedan od prvih matematičara koji je razmišljao o grafovima i mrežama bio je Leonhard Euler. Eulera je zaintrigirao stari problem u vezi s gradom Königsberg u blizini Baltičkog mora.

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 , a svaki most koji povezuje dvije regije predstavljen je odgovarajućim .

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 stupnjem. Tada možemo bojati vrhove na različite načine i pokušati otkriti uzorak:

Value
Size
Prime Numbers
Even and Odd

These graphs are possible:

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

These graphs are not possible:

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

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 . Taj se uvjet može objasniti ako na grafu pogledamo samo jednu vršku:

Here you can see a single, magnified vertex in a graph.
If we draw the graph, we will eventually have an edge leading towards this vertex, and then another one leading away. This makes two edges meeting at the vertex.
Maybe the vertex is a crossing rather than a corner. In that case there will be another edge leading towards the vertex, and another edge leading away. Now we have four edges.
And in some graphs, there may even be a third pair of edges leading towards and away from the vertex. Now there are six edges.
Notice that, either way, there always is an even number of edges meeting at the vertex.
The only two exceptions are the vertices where the path starts, and where it ends – these two may have an odd number of edges. If the start and end point are the same, all vertices in the graph are even.

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.

x-img(lightbox width=240 height=260 src="/content/graph-theory/images/prague.jpg")
Archie