I ett drag
Udda noder
Ritade kanter
Sätt att rita den

    • 0 udda noder: en krets, från vilken nod som helst tillbaka till den
    • 2 udda noder: en väg från den ena till den andra
    • 4 eller fler: omöjligt i ett drag

    Metod

    Mer om eulervägar och eulerkretsar

    Eulervägsökare

    Går det att rita jultomtens hus utan att lyfta pennan och utan att dra någon linje två gånger? Det går, men bara om du börjar i ett av de två nedre hörnen, och från vart och ett finns det 44 sätt. Skälet är en nods grad, antalet linjer som möts där: varje gång pennan passerar en nod använder den två av dess linjer. Leonhard Euler fann den här regeln 1736 med Königsbergs sju broar. Rita av en figur själv, se var du kör fast och varför, be om ett tips, eller se en algoritm rita den. Välj en figur och rita av den: tryck på en nod för att börja och sedan på kanterna eller de följande noderna i ordning, eller dra från nod till nod. Varje kant får bara användas en gång. Tillbaka ångrar ett steg, Tips visar nästa säkra kant och Lös spelar upp Fleurys eller Hierholzers algoritm steg för steg. Udda noder är fyllda, och märket vid varje nod är dess grad. Under Rita lägger ett tryck på en tom yta till en nod, och ett tryck på två noder förbinder dem, en gång till för ytterligare en kant; dra i en nod för att flytta den. Radera tar bort noder och kanter. Är fler än två noder udda lägger Lägg till in de kanter som gör figuren ritbar.

    Hur det fungerar

    1. Välj en figur, till exempel Königsbergs sju broar, jultomtens hus eller en stjärna, eller rita din egen under Rita, med hur många kanter du vill mellan två noder.
    2. Tryck på en nod för att börja och sedan på kanterna eller noderna i ordning, eller dra från nod till nod. Kör du fast säger statusraden varför; Tillbaka ångrar ett steg och Tips visar en säker kant.
    3. Läs gradregeln under figuren, lägg till de föreslagna kanterna i en omöjlig figur, eller tryck på Lös för att se Fleurys eller Hierholzers algoritm rita den steg för steg.

    Varför de udda noderna avgör

    Ett drag som passerar en nod kommer in längs en linje och går vidare längs en annan, så det använder nodens linjer två och två. Bara där draget börjar eller slutar kan en linje bli kvar utan partner. Därför måste en nod med ett udda antal linjer vara början eller slutet. Utan udda noder slutar draget där det började: en eulerkrets. Med två går det från den ena till den andra: en eulerväg. Med fyra eller fler finns det för många ändar för ett enda drag, och k udda noder kräver k/2 drag. Königsberg hade fyra landstycken med fem, tre, tre och tre broar: alla fyra udda, så ingen promenad kunde gå över varje bro en gång. En ny bro mellan två av dem hade gjort promenaden möjlig.

    Fleurys och Hierholzers algoritmer

    Att veta att en figur går att rita är inte detsamma som att rita den: ett oförsiktigt drag kan skära av sig från de linjer det fortfarande behöver. Fleurys algoritm från 1883 undviker det med en regel: gå aldrig över en bro, alltså en linje vars borttagande skulle dela de återstående linjerna i två delar, om det inte saknas andra linjer. Hierholzers algoritm, från en artikel som gavs ut 1873, är snabbare: gå vart du vill tills det tar stopp, vilket bara kan hända vid starten, och gå sedan från en nod på turen som fortfarande har lediga linjer ännu en sluten slinga och foga in den i turen. Tiden växer i proportion till antalet kanter, och så hittar datorer eulervägar.

    Ofta ställda frågor

    Vad är skillnaden mellan en eulerväg och en eulerkrets?

    Båda använder varje kant i en graf exakt en gång. En eulerkrets slutar där den började; en eulerväg slutar någon annanstans. En sammanhängande graf har en krets när varje nod har jämn grad, och en väg när exakt två noder har udda grad; vägen går då från den ena till den andra.

    Varför går det inte att gå över Königsbergs sju broar en gång var?

    Rita varje landstycke som en nod och varje bro som en kant. Ön Kneiphof hade fem broar och de tre andra landstyckena tre var, så alla fyra noderna är udda. En promenad kan bara börja eller sluta vid en udda nod, och fyra är för många. En extra bro mellan två av dem lämnar två udda noder, och promenaden blir möjlig.

    Hur många sätt finns det att rita jultomtens hus?

    44 från vart och ett av de två nedre hörnen, 88 totalt, om en annan ordning eller riktning räknas som ett annat sätt. Från någon annan nod går det inte, eftersom de nedre hörnen är de enda två med ett udda antal linjer. Appen räknar sätten för små figurer på det här viset.

    Vad är en bro i en graf?

    En kant vars borttagande delar en sammanhängande graf i två delar. Fleurys algoritm går aldrig över en bro bland de återstående kanterna så länge den har ett annat val, för då skulle en del av figuren lämnas kvar. I den här appen får ett drag som kör fast efter att ha gått över en bro för tidigt veta vilket steg det var.

    Kan det finnas mer än en kant mellan två noder?

    Ja. En graf med parallella kanter kallas multigraf, och Königsberg kräver en: två broar förband Kneiphof med vardera stranden. Tryck under Rita en gång till på två noder för att lägga till ännu en kant mellan dem, upp till fyra. Gradregeln fungerar likadant och räknar varje kant.

    Redo att prova det?

    Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

    Gå till Editor