Grafos i ponts de Königsberg

Els grafs

Un graf és un conjunt de punts units mitjançant una sèrie d'arestes. Els grafs conexos són aquells que sempre podem trobar un camí que unix un vértex a un vértex qualsevol.
Un graf té un cicle eulerià si és un graf conex i de cada vértex ix un nombre parell d'arestes.
D'acord amb açò, en un cicle eulerià, podrem recórrer totes les arestes una vegada per a passar per tots els punts i començar i acabar en el mateix vértex.
Un graf té un camí eulerià si és un graf conex i de cada vértex ix un nombre parell d'arestes exceptuant de dos, que seran el vérteix d'eixida i el vértex final.
Reflexionant sobre açò, per a que un graf es puga recórrer des d'un vértex, passant una única vegada per tots els vértexs i acabant en el mateix vértex, el nombre d'arestes que ixen de cada vértex ha de ser parell, sense cap excepció.

Els ponts de Königsberg

Els ponts de Königsberg és un problema matemàtic resolt per el matemàtic Euler, que utilitza els grafs per a explicar la solució.
El problema diu així:
La ciutat de Königsberg, que actualment s'anomena Kaliningrado, a Rússia, restava dividida en 4 parts, separades per el riu Pregolya, que s'havien unit amb set ponts. La pregunta deia així: és possible creuar tots els ponts únicament una vegada eixint i acabant a la mateixa part de la ciutat?
Euler va representar aquest problema amb un graf, representant els ponts com arestes i les parts de la ciutat com vértexs.




      →






Els punts intermitjos d'un recorregut possible necessariament han d'estar connectats a un nombre parell de línies. Si arribem a un punt des d'alguna línea, l'única manera d'eixir d'eixe punt és mitjançant una línia diferent. Tant el punt incial com el final serien els únics que podríen estar connectats amb un nombre senar de línees. El requisit addicional del problema diu que el punt inicial ha de ser el final, per la qual cosa no pot existir més d'ún únic punt connectat amb un nombre senar de línies.