Det generella tunnelbaneproblemet

AlefWiki
Version från den 20 november 2009 kl. 22.26 av Eric (diskussion | bidrag)
Hoppa till navigering Hoppa till sök

Det generella tunnelbaneproblemet är ett öppet problem som konstaterats av Niklas den Yngre som en del av en tävling efter att han själv endast lyckats lösa det specifika tunnelbaneproblemet. För närvarande är inte tävlingen avgjord och priset av en låda kakor kvarstår till den som först kan formulera en lösning eller visa att en sådan ej kan existera.

Problemet

Problemet i sig är som följer: Om vi har ett tunnelbanenät som är en sammanhängande graf av n noder så [math] n \isin N[/math] där vi definierar en resa som en färd från en nod till en annan nod som aldrig passerar någon nod mer än en gång, finn ett slutet uttryck för antalet möjliga resor.

Lösningar

Här kan man, om man tror sig ha en korrekt lösning, lägga upp den för allmän beskådan och genomgång. Ännu finns det inga lösningsförslag.

Se även

Det specifika tunnelbaneproblemet