From Wikipedia, the free encyclopedia
Els set ponts de Königsberg és un famós problema matemàtic que va donar origen a la teoria de grafs. Königsberg, l'actual Kaliningrad, és una ciutat russa (que fou alemanya fins a la fi de la II Guerra Mundial) per la qual passa el riu Pregel. Enmig del riu, dues grans illes estaven connectades entre elles i a les ribes mitjançant una estructura de set ponts en total.
Per a organitzar una desfilada, els habitants de la ciutat es van plantejar si era possible recórrer els set ponts de manera que només es passés per cadascun d'ells un sol cop.
El 1736, el matemàtic suís Leonhard Euler va demostrar que no era possible en Solutio problematis ad geometriam situs pertinentis.[1] En la història de les matemàtiques, es considera que aquest problema és el que va donar origen a la teoria de grafs, el desenvolupament de la qual va permetre grans avenços en combinatòria i topologia.
Euler va trobar la solució fent abstracció dels elements rellevants en el problema: substituint les illes i riberes per punts (vèrtexs, nodes), i els ponts per camins (branques) que els enllaçaven. El resultat conforma l'estructura que, avui en dia, s'anomena graf.
→
→
Euler va adonar-se que el problema podia ser resolt en funció del grau dels nodes. En el problema dels set ponts, tres nodes tenen grau 3, i un té grau 5. Euler va provar que el circuit que es desitjava era possible si i només si hi havia exactament dos nodes o no cap de grau senar (imparell). Un camí d'aquest tipus s'anomena camí eulerià. A més, si dos nodes tenen grau senar, aquests han de ser el punt d'inici i final del camí eulerià. Per tant, com que el graf corresponent als ponts de Königsberg té quatre nodes de grau senar, no pot tenir un camí eulerià.
Una forma alternativa del problema demana un camí que passi per tots els ponts i també tingui el mateix punt d'inici i final. Un circuit d'aquesta mena s'anomena un circuit eulerià. Existeix un circuit eulerià si i només si no hi ha nodes de grau senar. Es pot veure que tots els circuits eulerians són també camins eulerians.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
