Gràfics i xarxesEls ponts de Königsberg
Un dels primers matemàtics a pensar en gràfics i xarxes va ser
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
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
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
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.