Problèma dels sèt ponts de Königsberg

Lo problèma dels sèt ponts de Königsberg es un problèma matematica conegut per èsser a l'origina de la teoria dels grafes. Resolgut per Leonhard Euler en 1736, se presente atal:

→ →

La vila de Königsberg (ara Kaliningrad) es bastida a l'entorn de doas ilas situadas sul Pregel e ligadas entre elas per un pont. Sièis autres ponts ligan las ribas del riu a l'una o l'autre de las doas ilas, coma presentats sul plan çai-sus. Lo problèma consistís a determinar s'existís o non una caminda per las carrièras de Königsberg permetent, dempuèi quin que siá lo punt de partença, de passar un e sonque un còp per cada pont, e tornar al punt de partença, se comprendent que se pòt passar lo Pregel sonque pels ponts.

Resolucion del problèma

Una tala caminada existís pas, e foguèt Euler que donèt la solucion del problèma caracterizant los grafs que se nomena ara « eulerians » en referéncia a l'illustre matematician, a l'ajuda d'un teorèma que la demonstracion rigourosafoguèt  publicada per Carl Hierholzer en 1873.

Lo problèma a jos aquela forma non generalizada sonqu'un interés istoric, car pel cas, es pro intuitiu de demostrar que la caminada demandada existís pas. Per o veire, sufís d'associar un graf a la vila coma dins la figura çai-sus e de supausar que la caminada cercada existís. Se pòt alara, dempuèi la caminada, ordonar las sèt arestas del graf de biais que doas arestas consecutivas al respècte de nòstre òrdre sián adjacentas dins lo graf (considerant que la darrièra e la primièra aresta son consecutivas, perque i a retorn al punt de partença).

Atal tot som del graf es necessariament incident a un nombre par d'arestas (perque es incident a une arèsta es  tanben incident a l'aresta precedenta o que li succèda dins l'òrdre). Mas lo graf a de soms que son incidents amb tres arestas, d'ont l'impossibilitat.

Notam que quitament se renonciam a exigir lo retorn al punt de partença, una caminada passent un e un sol còp cada pont existí tampauc pas. Existeririá se pel mai dos soms del graf, correspondon als punts de causir respectivament coma partença e arribada, èran incidents a un nombre impar d'arestas, mas los soms del graf dels ponts de Königsberg son totes quatre dins aquel cas; la caminada es donc impossible. Pasmens caldriá de suprimir o d'apondre un pont quin que siá per que lo graf modificat permeta de caminadas per totes los ponts sens retorns (sols dos soms demorant d'incidéncia impara). E son al mens dos ponts, plan causits, que caldriá apondre o levar per permetre la caminada amb retorn d'en primièr cercat.

Se pòt donar a aquel problèma una solucion mens teoric. Sufís de remarcar qu'i a quatre zonas, las doas rivas e las doas ilas, caduna ligada a las autras per un nombre impar de ponts. Aquel nombre impar fat que s'intram dins una region R, devèm i demorar. Mas se pòt acabar sa caminada dins mai d'una d'aquelas quatre regions.

Notas e referéncias

• Leonhard Euler, « Solutio problematis ad geometriam situs pertinentis » (1759), dans Mémoires de l'Académie des sciences de Berlin
• Édouard Lucas, Récréations mathématiques, vol. I (1882), éd. Gauthier Villars, Paris : le « problème des sept ponts » fait l'objet de la « récréation nº 2 ».

Articles connèxes

• Graf eulerian
• Nos gordian
• Uòu de Colomb