Blogia
Geeks i d'altres

Els ponts de Königsberg

Si teniu una estona i vos agraden es jocs de lògica mirau-vos aixó.

Conta la llegenda que un bon home es va proposar fer un paseitg per tots els ponts del riu Pregel sense pasar dos pics pel mateix lloc. Si ho intentau fer, veureu que és imposible. Pero no es pot afirmar que una cosa és imposible sense formular unes hipotesis fonamentades i demostrar-ho mitjançant experimentació, o almenys això diu el mètode cientific.
Pero el 1736 el matemàtic suïs Leonard Euler va publicar que era imposible donar aquest paseitg. Anem a veure com ho va demostrar. Podem representar els puents mitjançant el que els matemàtics anomenen "Grafo".

Al "grafo" les aristes representen els ponts i els vertexs terra ferma. Si pensam en com dibuixar el grafo sense aixecar el llapis i sense pasar dues vegades per la mateixa aresta es veu que cada vegam que arribam a un vertex necesitam una altra aresta per "sortir", és a dir, que si a un vertex arriben dues aristes podrem entrar per una i sortir per s'altra. Però si un vertex té tres arestes arribarem per una i surtirem per s'altra, pero la pròxima vegada que hi arribem ja no tendrem sortida.
Concluim que tots els vertex del grafo han de tenir un grau (nombre d'arestes que incideixen en el vertex) parell per poderse dibuixar sense aixecar el llapis començant i acaban al mateix punt. En el cas d'haver dos vertexs de grau imparell també es pot solucionar el problema, pero començant i acabant a diferents punts.
El "grafo" dels ponts de Königsberg té els vertexs A, C i D amb grau imparell, amb el que comprovam que és imposible fer una volta sense pasar dues vegades pel mateix pont. Impresionant, veritat?

Font : Kirai.NET
¿Y esta publicidad? Puedes eliminarla si quieres.

0 comentarios

¿Y esta publicidad? Puedes eliminarla si quieres