Gràfics i xarxesEls ponts de Königsberg

Aquesta pàgina ha estat traduïda automàticament i pot contenir errors. Poseu-vos en contacte si voleu ajudar-nos a revisar les traduccions.

Un dels primers matemàtics a pensar en gràfics i xarxes va ser Leonhard Euler . Euler va quedar intrigat per un antic problema sobre la ciutat de Königsberg, prop del mar Bàltic.

El riu Pregel divideix Königsberg en quatre parts separades, que estan connectades per set ponts. És possible passejar per la ciutat creuant tots els ponts exactament una vegada, però no més d’una vegada? (Podeu començar i acabar en qualsevol lloc, no necessàriament al mateix lloc.)

Proveu de trobar una ruta vàlida dibuixant aquests mapes:

Map 1

Map 2

Map 3

Map 4

En el cas de Königsberg sembla ser impossible trobar una ruta vàlida, però algunes altres ciutats funcionen. Euler va aconseguir trobar una regla senzilla que es pugui aplicar a qualsevol ciutat, sense haver de provar gaires possibilitats, utilitzant la teoria de gràfics.

Primer, hem de convertir els mapes de la ciutat en gràfics amb vores i vèrtexs. Tota illa o regió terrestre està representada per i cada pont que connecta dues regions està representada per un corresponent .

Ara el problema de "recórrer una ciutat mentre es creua cada pont exactament una vegada" s'ha convertit en un problema de "dibuixar un gràfic amb un traç continu mentre es traça cada extrem exactament una vegada".

Al paper, traieu uns quants gràfics diferents i, a continuació, intenteu esbrinar quins es poden dibuixar amb un traç únic i continu.

Igual que els mapes de la ciutat d’abans, trobem que alguns gràfics són possibles mentre que d’altres no. Per ajudar-nos a comprendre el perquè, etiquetem tots els vèrtexs amb el seu grau . A continuació, podem acolorir els vèrtexs de diferents maneres i intentar revelar un patró:

Value

Size

Prime Numbers

Even and Odd

These graphs are possible:

These graphs are not possible:

Si comparem aquests nombres per a gràfics possibles i els que no són possibles, sembla que es pot dibuixar un gràfic si no . Aquesta condició es pot explicar si ens fixem en un sol vèrtex al gràfic:

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.

Si aneu cap al mapa de Königsberg, trobareu que hi ha més de dues illes amb un nombre senar de ponts. Per tant, és realment impossible una ruta que creua tots els ponts exactament una vegada, i això va descobrir Leonard Euler.

Pot ser que el descobriment d'Euler no sembli especialment útil a la vida real, però els gràfics són el fonament de molts altres problemes geogràfics, com ara trobar indicacions entre dues ubicacions. Més endavant descobrirem més d’aquestes aplicacions.

Inicieu la sessió a Mathigon

Compartir

Envieu-nos comentaris

Gràcies pels teus suggeriments!

Configuració d’accessibilitat

Restableix el progrés

Glossari

Gràfics i xarxesEls ponts de Königsberg

Map 1

Map 2

Map 3

Map 4

Canviar d'idioma