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 