Us anem a proposar un problema:
Podries creuar tots els pont començant per qualsevol però sense creuar un mateix pont dos cops?
Aquest curiós problema va donar lloc a la Teoria de Grafs ja que per a la seva resolució, Leonhard Euler, va crear un graf substituint les illes i riberes per punts i els ponts per arestes. I així, va aconseguir demostrar que no era possible recorrer els set pont sense haver de repetir-ne algun.
El problema va sorgir l’any 1736, perquè a una ciutat anomenada Königsberg, situada a Rússia però que abans era d’Alemanya, es volia fer una desfilada, i els habitants de la ciutat es van plantejar si podien creuar els 7 ponts sense repetir-ne cap. Van demanar ajuda a Euler i ell va resoldre el problema.
Euler es va adonar que el problema es resolia en funció del grau dels nodes o vèrtexs (és a dir, del número d’arestes que hi arriben): Va provar que el circuit que es desitjava era possible si hi ha exactament dos nodes o ningun de grau senar. Si no n’hi ha cap (tots els vèrtexs parells) és possible començar en qualsevol node i acabar en el mateix, en canvi, si n’hi ha dos de senars cal començar en un d’ells i acabar en l’altre.
En el cas dels ponts de Königsberg hi ha 3 nodes de grau 3 i un de grau 5, per tant, tots quatre són senars i per això no es pot recorrer.
Ara intenta recorre aquests grafs passant per totes les arestes sense repetir-ne cap. Sabries fer el mateix sortint d’un punt i tornant al mateix?
Ja ho heu provat?
Haureu comprovat que el primer graf es pot recórrer partint de qualsevol vèrtex i tornant al mateix. Això és degut a que tots els seus vèrtexs són parells (tots tenen grau 4). Un graf així s’anomena Eulerià.
El segon graf es pot recórrer només si començem en el vèrtexs G o H i l’acabem sempre en l’altre. Això és degut a que aquests són els seus únics dos vèrtexs senars (G té grau 3 i H té grau 1). Un graf així s’anomena Semieulerià.
El tercer graf no es pot recórrer sense repetir alguna aresta. Això és degut a que té més de 2 vèrtexs senars (A, B, C i D tenen grau 3). Un graf així s’anomena No-Eulerià.
Si no n’heu tingut prou, proveu de passar pels 17 ponts que uneixen entre sí les parts del territori de Leningrad, sense recórrer ningun d’ells dues vegades:
L’any 1931, un enginyer elèctric i matemàtic que es deia Harry Beck va crear el recorregut de les línies de metro de Londres a través d’un disseny topogràfic i no geogràfic com els anteriors i aplicant la teoria de Grafs. Fins avui dia la idea topogràfica de Beck es la més utilitzada en el mon per aquests tipus de plànols.
Us deixem una pàgina web molt interesant sobre grafs on podeu practicar tot això:
https://dl.dropboxusercontent.com/u/44162055/manipulables/topologia/topologia_trazos.html
El següent enllaç és un editor de grafs:
AleshoresB 
És curiós com un problema de la vida quotidiana pot portarnos a desenvolupar coses així. Molt bona feina!
M'agradaM'agrada
Sabíeu que en realitat Beck era un simple empleat del Metro que va notar que degut a que el tren viatjava per sota terra, las ubicacions físiques de les estacions eren irrellevants pel viatger que buscava com arribar d’una a una altre estació. Per això va decidir realitzar un mapa més simplificat de forma topològica que encara es manté avui en dia.
El següent enllaç es sobre una imatge del mapa geogràfic de 1908 (gran diferencia!!):
M'agradaLiked by 2 people
Una curiositat és que posteriorment que es demostrés que els ponts de Köningsberg no es podien creuar sense repetir-ne cap, van construir un altre pont per així poder fer el circuit sencer sense repetir un pont.
M'agradaLiked by 1 person
La Clara Grima ha escrit un nou article a CienciaXplora titulat “¿Es posible hacer cualquier animalito con globos?” on explica les matemàtiques que hi ha darrera dels artistes que fan figures amb globus: l’estudi dels grafs.
Interessantíssim com tots el que escriu la Clara, no us el podeu perdre!! I si teniu temps aneu llegint tots els seus articles que en surten enllaçats, val molt la pena!
Aquí l’enllac: http://www.cienciaxplora.com/divulgacion/posible-hacer-cualquier-animalito-globos_2016020300176.html
M'agradaM'agrada