Euler-veje og Euler-kredse forklaret
Nogle figurer kan tegnes i ét stræk, uden at løfte blyanten og uden at tegne en linje to gange, og andre kan ikke, hvor længe man end prøver. Man behøver ikke prøve: tæl linjerne i hvert hjørne. Har højst to hjørner et ulige antal linjer, kan figuren tegnes, og i de hjørner skal stregen begynde og slutte. Leonhard Euler fandt denne regel i 1736 og grundlagde med den grafteorien.
Königsbergs syv broer
Den preussiske by Königsberg, i dag Kaliningrad, lå på begge bredder af floden Pregel og på to øer i den, Kneiphof og Lomse. Syv broer forbandt de fire dele: to fra Kneiphof til hver bred, én mellem de to øer og én fra Lomse til hver bred. Byens borgere spekulerede på, om en tur kunne krydse hver bro præcis én gang. Euler svarede i en afhandling, han fremlagde for akademiet i Sankt Petersborg i 1735, trykt i 1741: det kan den ikke. Hans afgørende skridt var at se bort fra alt andet end bydelene og broerne imellem dem, og det er netop, hvad en graf gør: et knudepunkt for hvert landstykke og en kant for hver bro, med to kanter hvor to broer forbinder de samme steder.
Gradreglen
Et knudepunkts grad er antallet af kanter ved det. Et stræk, der passerer gennem et knudepunkt, kommer ind ad én kant og ud ad en anden, så det bruger knudepunktets kanter parvis. Kun strækkets første og sidste knudepunkt kan beholde en kant uden makker. Derfor skal et knudepunkt med ulige grad være strækkets begyndelse eller slutning. Kneiphof havde fem broer og de tre andre dele tre hver: fire ulige knudepunkter, to for mange. Generelt har en sammenhængende graf en Euler-kreds, et stræk der slutter hvor det begyndte, når alle grader er lige, og en Euler-vej, når præcis to grader er ulige, fra det ene til det andet. Antallet af ulige knudepunkter er aldrig ét eller et andet ulige tal: hver kant lægger 2 til summen af alle grader, så summen er lige. Det bemærkede Euler også, og det kaldes i dag håndtrykslemmaet.
Hvorfor reglen er nok
Euler viste, at en figur med mere end to ulige knudepunkter ikke kan tegnes, og sagde uden bevis, at enhver anden sammenhængende figur kan. Beviset kom fra Carl Hierholzer, en tysk matematiker, der døde ung i 1871; hans artikel udkom i 1873. Begynd i et ulige knudepunkt, hvis der er et, ellers hvor som helst, og gå ad ubrugte kanter, så længe du kan. Fordi alle andre knudepunkter har lige grad, kan du kun gå i stå i slutknudepunktet. Er der kanter tilbage, rører nogle af dem turen indtil nu, for figuren hænger sammen. Gå fra sådan et knudepunkt igen, indtil du går i stå, hvilket nu sker tilbage i det knudepunkt, og indsæt sløjfen i turen dér. Gentag, til ingen kant er tilbage. Beviset er samtidig den hurtigste algoritme: hver kant bliver set på et fast antal gange.
Fleurys algoritme: brænd ikke dine broer
Et stræk kan slå fejl selv på en figur, der kan tegnes. Tag to trekanter forbundet af en enkelt kant, og begynd i et hjørne af den første: går du over til den anden trekant, før den første er færdig, kommer du aldrig tilbage. Den forbindende kant er en bro: fjerner man den, deles figuren i to. Fleurys algoritme fra 1883 giver én regel: tag i hvert knudepunkt en kant, der ikke er en bro for de tilbageværende kanter, medmindre der ikke er andre. Følger man den, bliver man altid færdig. At teste for en bro tager tid, så Fleurys algoritme er langsommere end Hierholzers, men det er den, man kan følge med en blyant, og tippet i appen bruger den.
At reparere en figur
En figur med k ulige knudepunkter kræver k/2 stræk. For at tegne den i ét tilføjer man kanter, der parvis forbinder de ulige knudepunkter: hver ny kant gør to ulige knudepunkter lige. Med k/2 − 1 kanter bliver to ulige knudepunkter tilbage, og man får en vej; med k/2 bliver ingen tilbage, og man får en kreds. Én bro mere i Königsberg, mellem to vilkårlige af de fire dele, ville have gjort turen mulig, og to ville have gjort en rundtur mulig. Historien gjorde noget lignende: to broer gik tabt i Anden Verdenskrig, og to blev erstattet af en moderne vej, og de fem broer, der i dag står på de gamle steder, kan krydses én gang hver, fra den ene ø til den anden.
At tælle måderne
Julemandens hus, et kvadrat med begge diagonaler og et tag, er den tyske børneversion af opgaven: „Das ist das Haus vom Ni-ko-laus“ har otte stavelser, én for hver streg. Dets to nederste hjørner er de eneste ulige knudepunkter, og der er præcis 44 måder at tegne det på fra hvert af dem, 88 i alt. For orienterede grafer findes der en formel for antallet af Euler-kredse, BEST-sætningen, opkaldt efter de Bruijn, van Aardenne-Ehrenfest, Smith og Tutte. For almindelige grafer kendes ingen sådan formel, og tælling anses generelt for svær, så appen tæller små figurer ved at prøve hver måde og springe de trin over, der ville dele figuren i to.
Hvor Euler-veje bruges
En sneplov, en fejemaskine eller et postbud vil køre hver gade én gang og vende tilbage. Har hvert kryds et lige antal gader, klarer en Euler-kreds det; ellers skal nogle gader køres to gange, og at vælge de billigste er det kinesiske postbudproblem, stillet af Meigu Guan i 1962. En pennplotter eller en laserskærer sparer tid ved at tegne så mange linjer som muligt uden at løfte. Ved genomsekventering sættes millioner af korte DNA-stykker sammen ved at finde en Euler-vej gennem en De Bruijn-graf, hvor hvert stykke er en kant. Og den samme regel fortæller, hvilke stregtegninger i et opgavehæfte der er værd at prøve.
Prøv selv
Åbn Euler-vej-finderen for selv at tegne tolv figurer efter, fra Königsberg i 1736 og i dag til stjerner, kvadrater i hinanden og en terning, eller tegn dine egne med parallelle kanter. De ulige knudepunkter er fyldte, hvert knudepunkt viser sin grad, og gradreglen under figuren siger, hvad der er muligt, og hvilke kanter der ville reparere figuren. Går du i stå, siger appen, om du begyndte i det forkerte knudepunkt eller krydsede en bro for tidligt, og ved hvilket trin. Tip giver en sikker kant, og Løs tegner figuren med Fleurys algoritme, hvor brotesten vises, eller med Hierholzers, hvor hver indsættelse vises.
Ofte stillede spørgsmål
Er en Euler-vej det samme som en Hamilton-vej?
Nej. En Euler-vej bruger hver kant én gang og må besøge et knudepunkt flere gange; en Hamilton-vej besøger hvert knudepunkt én gang og behøver ikke bruge hver kant. Om en graf har en Euler-vej, afgøres straks ved at tælle ulige knudepunkter, men for Hamilton-veje kendes ingen hurtig test, og at finde en er et af datalogiens klassiske svære problemer.
Gælder gradreglen, når to knudepunkter er forbundet af mere end én kant?
Ja. Hver kant tæller med i graden af begge sine ender, uanset om en anden kant forbinder de samme to knudepunkter. Königsberg er sådan en multigraf, med to broer fra Kneiphof til hver bred. En kant fra et knudepunkt til sig selv, en løkke, lægger 2 til dets grad og ændrer aldrig, om det er ulige.
Hvad med ensrettede gader?
I en orienteret graf har hver kant en retning, og reglen sammenligner de kanter, der går ind i hvert knudepunkt, med dem, der går ud. Der er en Euler-kreds, når hvert knudepunkt har lige så mange kanter ind som ud, og kanterne hænger sammen, og en Euler-vej, når ét knudepunkt har én kant mere ud end ind, ét har én mere ind end ud, og alle andre er i balance. Vejen går så fra det første til det andet.
Kan der findes en figur med præcis ét ulige knudepunkt?
Nej. Graderne af alle knudepunkter lagt sammen giver det dobbelte af antallet af kanter, fordi hver kant har to ender. Den sum er lige, så antallet af ulige grader i den skal også være lige: 0, 2, 4 og så videre, aldrig 1 eller 3.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn Euler-vej-finderen