Eulervägar och eulerkretsar förklarade
Somliga figurer går att rita i ett drag, utan att lyfta pennan och utan att dra någon linje två gånger, och andra går inte, hur länge man än försöker. Man behöver inte försöka: räkna linjerna vid varje hörn. Har högst två hörn ett udda antal linjer går figuren att rita, och vid de hörnen måste draget börja och sluta. Leonhard Euler fann den här regeln 1736 och grundade med den grafteorin.
Königsbergs sju broar
Den preussiska staden Königsberg, i dag Kaliningrad, låg på båda stränderna av floden Pregel och på två öar i den, Kneiphof och Lomse. Sju broar förband de fyra delarna: två från Kneiphof till vardera stranden, en mellan de två öarna och en från Lomse till vardera stranden. Stadsborna undrade om en promenad kunde gå över varje bro exakt en gång. Euler svarade i en skrift som han lade fram för akademien i Sankt Petersburg 1735 och som trycktes 1741: det går inte. Hans avgörande steg var att kasta bort allt utom stadsdelarna och broarna mellan dem, och det är just vad en graf gör: en nod för varje landstycke och en kant för varje bro, med två kanter där två broar förbinder samma platser.
Gradregeln
En nods grad är antalet kanter vid den. Ett drag som passerar en nod kommer in längs en kant och går ut längs en annan, så det använder nodens kanter parvis. Bara dragets första och sista nod kan behålla en kant utan partner. Därför måste en nod med udda grad vara dragets början eller slut. Kneiphof hade fem broar och de tre andra delarna tre var: fyra udda noder, två för många. I allmänhet har en sammanhängande graf en eulerkrets, ett drag som slutar där det började, när varje grad är jämn, och en eulerväg när exakt två grader är udda, från den ena till den andra. Antalet udda noder är aldrig ett, eller något annat udda tal: varje kant lägger 2 till summan av alla grader, så summan är jämn. Det märkte Euler också, och det kallas i dag handskakningslemmat.
Varför regeln räcker
Euler visade att en figur med fler än två udda noder inte går att rita, och påstod utan bevis att varje annan sammanhängande figur går. Beviset kom från Carl Hierholzer, en tysk matematiker som dog ung 1871; hans artikel kom ut 1873. Börja vid en udda nod om det finns en, annars var som helst, och gå längs oanvända kanter så länge du kan. Eftersom varje annan nod har jämn grad kan du bara köra fast vid slutnoden. Finns kanter kvar rör några av dem vägen du redan gått, för figuren hänger samman. Gå från en sådan nod igen tills det tar stopp, vilket nu sker tillbaka vid den noden, och foga in slingan i vägen där. Upprepa tills ingen kant är kvar. Beviset är samtidigt den snabbaste algoritmen: varje kant granskas ett bestämt antal gånger.
Fleurys algoritm: bränn inte dina broar
Ett drag kan misslyckas även på en figur som går att rita. Ta två trianglar förbundna av en enda kant och börja i ett hörn av den första: går du över till den andra triangeln innan den första är klar kommer du aldrig tillbaka. Den förbindande kanten är en bro: tar man bort den delas figuren i två. Fleurys algoritm från 1883 ger en regel: ta vid varje nod en kant som inte är en bro bland de kanter som är kvar, om det inte saknas andra. Följer man den blir man alltid klar. Att testa för en bro tar tid, så Fleurys algoritm är långsammare än Hierholzers, men det är den man kan följa med en penna, och tipset i appen använder den.
Att laga en figur
En figur med k udda noder kräver k/2 drag. För att rita den i ett enda lägger man till kanter som parar ihop de udda noderna: varje ny kant gör två udda noder jämna. Med k/2 − 1 kanter blir två udda noder kvar och man får en väg; med k/2 blir ingen kvar och man får en krets. En bro till i Königsberg, mellan två godtyckliga av de fyra delarna, hade gjort promenaden möjlig, och två hade gjort en rundtur möjlig. Historien gjorde något liknande: två broar gick förlorade i andra världskriget och två ersattes av en modern väg, och de fem broar som i dag står på de gamla platserna kan passeras en gång var, från den ena ön till den andra.
Att räkna sätten
Jultomtens hus, en kvadrat med båda diagonalerna och ett tak, är den tyska barnversionen av pusslet: ”Das ist das Haus vom Ni-ko-laus” har åtta stavelser, en för varje streck. Dess två nedre hörn är de enda udda noderna, och från vart och ett finns exakt 44 sätt att rita det, 88 totalt. För riktade grafer finns en formel för antalet eulerkretsar, BEST-satsen, uppkallad efter de Bruijn, van Aardenne-Ehrenfest, Smith och Tutte. För vanliga grafer är ingen sådan formel känd, och räkning anses i allmänhet svår, så appen räknar små figurer genom att pröva varje sätt och hoppa över de steg som skulle dela figuren i två.
Var eulervägar används
En snöplog, en sopmaskin eller en brevbärare vill köra varje gata en gång och återvända. Har varje korsning ett jämnt antal gator räcker en eulerkrets; annars måste några gator köras två gånger, och att välja de billigaste är det kinesiska brevbärarproblemet, ställt av Meigu Guan 1962. En pennplotter eller en laserskärare sparar tid genom att dra så många linjer som möjligt utan att lyfta. Vid genomsekvensering sätts miljoner korta DNA-bitar ihop genom att man söker en eulerväg genom en De Bruijn-graf, där varje bit är en kant. Och samma regel säger vilka streckteckningar i ett pysselhäfte som är värda att pröva.
Pröva själv
Öppna eulervägsökaren för att själv rita av tolv figurer, från Königsberg 1736 och i dag till stjärnor, kvadrater i varandra och en kub, eller rita dina egna med parallella kanter. De udda noderna är fyllda, varje nod visar sin grad, och gradregeln under figuren säger vad som är möjligt och vilka kanter som skulle laga figuren. Kör du fast säger appen om du började vid fel nod eller gick över en bro för tidigt, och vid vilket steg. Tips ger en säker kant, och Lös ritar figuren med Fleurys algoritm, där brotestet visas, eller med Hierholzers, där varje infogning visas.
Ofta ställda frågor
Är en eulerväg detsamma som en hamiltonväg?
Nej. En eulerväg använder varje kant en gång och får besöka en nod flera gånger; en hamiltonväg besöker varje nod en gång och behöver inte använda varje kant. Om en graf har en eulerväg avgörs genast genom att räkna udda noder, men för hamiltonvägar är inget snabbt test känt, och att hitta en är ett av datavetenskapens klassiska svåra problem.
Gäller gradregeln när två noder är förbundna av fler än en kant?
Ja. Varje kant räknas i graden för båda sina ändar, oavsett om ytterligare en kant förbinder samma två noder. Königsberg är en sådan multigraf, med två broar från Kneiphof till vardera stranden. En kant från en nod till sig själv, en ögla, lägger 2 till dess grad och ändrar aldrig om den är udda.
Hur är det med enkelriktade gator?
I en riktad graf har varje kant en riktning, och regeln jämför kanterna in i varje nod med kanterna ut. Det finns en eulerkrets när varje nod har lika många kanter in som ut och kanterna hänger samman, och en eulerväg när en nod har en kant mer ut än in, en har en mer in än ut och alla andra är i balans. Vägen går då från den första till den andra.
Kan det finnas en figur med exakt en udda nod?
Nej. Graderna för alla noder summerar till dubbla antalet kanter, eftersom varje kant har två ändar. Den summan är jämn, så antalet udda grader i den måste också vara jämnt: 0, 2, 4 och så vidare, aldrig 1 eller 3.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna eulervägsökaren