- 0 ulige knudepunkter: en kreds, fra ethvert knudepunkt tilbage til det
- 2 ulige knudepunkter: en vej fra det ene til det andet
- 4 eller flere: umuligt i ét stræk
Euler-vej-finder
Kan du tegne julemandens hus uden at løfte blyanten og uden at tegne en linje to gange? Ja, men kun hvis du begynder i et af de to nederste hjørner, og der er 44 måder fra hvert af dem. Grunden er et knudepunkts grad, antallet af linjer der mødes der: hver gang blyanten passerer gennem et knudepunkt, bruger den to af dets linjer. Leonhard Euler fandt denne regel i 1736 med Königsbergs syv broer. Tegn selv en figur efter, se hvor du går i stå og hvorfor, bed om et tip, eller se en algoritme tegne den. Vælg en figur, og tegn den efter: tryk på et knudepunkt for at begynde, og derefter på kanterne eller de næste knudepunkter i rækkefølge, eller træk fra knudepunkt til knudepunkt. Hver kant må kun bruges én gang. Tilbage fortryder et trin, Tip viser den næste sikre kant, og Løs afspiller Fleurys eller Hierholzers algoritme trin for trin. Ulige knudepunkter er fyldte, og mærket ved hvert knudepunkt er dets grad. Under Tegn tilføjer et tryk på et tomt sted et knudepunkt, og et tryk på to knudepunkter forbinder dem, endnu en gang for en kant mere; træk i et knudepunkt for at flytte det. Slet fjerner knudepunkter og kanter. Er mere end to knudepunkter ulige, indsætter Tilføj de kanter, der gør figuren mulig at tegne.
Sådan virker det
- Vælg en figur, for eksempel Königsbergs syv broer, julemandens hus eller en stjerne, eller tegn din egen under Tegn, med så mange kanter mellem to knudepunkter, som du vil.
- Tryk på et knudepunkt for at begynde, og derefter på kanterne eller knudepunkterne i rækkefølge, eller træk fra knudepunkt til knudepunkt. Går du i stå, siger statuslinjen hvorfor; Tilbage fortryder et trin, og Tip viser en sikker kant.
- Læs gradreglen under figuren, tilføj de foreslåede kanter til en umulig figur, eller tryk på Løs for at se Fleurys eller Hierholzers algoritme tegne den trin for trin.
Hvorfor de ulige knudepunkter afgør det
Et stræk, der passerer gennem et knudepunkt, kommer ind ad én linje og fortsætter ad en anden, så det bruger knudepunktets linjer to ad gangen. Kun dér, hvor stregen begynder eller slutter, kan en linje blive tilbage uden makker. Derfor skal et knudepunkt med et ulige antal linjer være begyndelsen eller slutningen. Uden ulige knudepunkter slutter stregen, hvor den begyndte: en Euler-kreds. Med to går den fra det ene til det andet: en Euler-vej. Med fire eller flere er der for mange ender til ét stræk, og k ulige knudepunkter kræver k/2 stræk. Königsberg havde fire landstykker med fem, tre, tre og tre broer: alle fire ulige, så ingen tur kunne krydse hver bro én gang. Én ny bro mellem to af dem ville have gjort turen mulig.
Fleurys og Hierholzers algoritmer
At vide, at en figur kan tegnes, er ikke det samme som at tegne den: et uforsigtigt stræk kan skære sig fra de linjer, det stadig mangler. Fleurys algoritme fra 1883 undgår det med én regel: kryds aldrig en bro, altså en linje, hvis fjernelse ville dele de tilbageværende linjer i to dele, medmindre der ikke er andre linjer. Hierholzers algoritme, fra en artikel udgivet i 1873, er hurtigere: gå hvorhen du vil, indtil du går i stå, hvilket kun kan ske ved starten, og gå så fra et knudepunkt på turen, der stadig har frie linjer, endnu en lukket sløjfe, og indsæt den i turen. Tiden vokser proportionalt med antallet af kanter, og sådan finder computere Euler-veje.
Ofte stillede spørgsmål
Hvad er forskellen på en Euler-vej og en Euler-kreds?
Begge bruger hver kant i en graf præcis én gang. En Euler-kreds slutter, hvor den begyndte; en Euler-vej slutter et andet sted. En sammenhængende graf har en kreds, når alle knudepunkter har lige grad, og en vej, når præcis to knudepunkter har ulige grad; vejen går så fra det ene til det andet.
Hvorfor kan Königsbergs syv broer ikke krydses én gang hver?
Tegn hvert landstykke som et knudepunkt og hver bro som en kant. Øen Kneiphof havde fem broer og de tre andre landstykker tre hver, så alle fire knudepunkter er ulige. En tur kan kun begynde eller slutte i et ulige knudepunkt, og fire er for mange. En ekstra bro mellem to af dem efterlader to ulige knudepunkter, og turen bliver mulig.
Hvor mange måder kan julemandens hus tegnes på?
44 fra hvert af de to nederste hjørner, 88 i alt, når en anden rækkefølge eller retning tæller som en anden måde. Fra ethvert andet knudepunkt kan det ikke lade sig gøre, fordi de nederste hjørner er de eneste to med et ulige antal linjer. Appen tæller måderne for små figurer på denne vis.
Hvad er en bro i en graf?
En kant, hvis fjernelse deler en sammenhængende graf i to dele. Fleurys algoritme krydser aldrig en bro blandt de tilbageværende kanter, så længe den har et andet valg, for så ville en del af figuren blive efterladt. I denne app får et stræk, der går i stå efter at have krydset en bro for tidligt, at vide, hvilket trin det var.
Kan der være mere end én kant mellem to knudepunkter?
Ja. En graf med parallelle kanter kaldes en multigraf, og Königsberg kræver en: to broer forbandt Kneiphof med hver bred. Tryk under Tegn igen på to knudepunkter for at tilføje endnu en kant mellem dem, op til fire. Gradreglen virker på samme måde og tæller hver kant med.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor