I den første artikel med matematiske stregpuslerier kiggede vi på opgaver, hvor det gjaldt om at tegne en figur med en lang streg. Måske fandt du ud af, at kun to af disse figurer kan tegnes med en streg uden at løfte blyanten.
Det trick vi benyttede os af til at løse opgaverne – at tælle knudepunkternes valens (antallet af kanter forbundet til punktet), hører til en gren af matematikken, som kaldes grafteori. Og her skal betegnelsen graf forstås som figurerne ovenfor.
Note: Grafer kender de fleste som en form for kurve i et koordinatsystem. Her på det sidste har vi set mange af den slags grafer i nyhederne, når der bliver talt om, hvordan spredningen af Covid-19 udvikler sig. Men det er ikke den slags grafer denne artikel handler. I denne artikel består en graf af punkter og kanter, hvor en kant forbinder to af grafens punkter.
Det var den kendte matematiker Leonhard Euler, der i 1736 gav startskuddet til dannelsen af grafteorien, da han undersøgte og løste det nu klassiske problem om de syv broer i byen Königsberg. Königsberg hedder i dag Kaliningrad og er en russisk by, der ligger nord for Polen, hvor floden Pregolja løber ud mod Østersøen.
På Eulers tid var der tradition for at gå aftentur over broerne i byen. De syv broer forbandt byens forskellige dele som det ses på billedet. Numrene på broerne har her ikke anden betydning end at kunne kende forskel på broerne.
Spørgsmålet Euler stillede sig selv var:
- Er det muligt på en gåtur at gå over alle syv broer præcis en gang?
Prøv engang om du kan finde en sådan gåtur.
Hvordan løste Euler problemet?
Euler kunne fx tjekke alle forskellige rækkefølger på broerne slavisk en efter en. En del vil hurtigt kunne afvises som fysisk umulige, fx kan bro nummer 1 og nummer 7 ikke komme lige efter hinanden, da de ikke forbinder de samme bydele. Desuden er det kun nødvendigt at tjekke halvdelen af rækkefølgerne, for hvis kan man ikke gå ruten forlæns, så kan man heller ikke gå den baglæns; hvis fx 1-2-3-4-5-6-7 ikke virker, så duer ruten 7-6-5-4-3-2-1 heller ikke.
Euler løste ikke problemet ved at tjekke alle muligheder fra en ende af, han tænkte sig om. Det smarte i hans tænkemåde er, at i stedet for at overveje hvor broerne er placeret, så overvejede han hvilke bydele broerne forbandt.
Hver bydel tænkte han som et knudepunkt og hver bro som en kant mellem de to relevante knudepunkter. På den måde fik han lavet et kompliceret kort over byen om til en simpel graf over broerne i byen:
Selv om der kun var syv broer vil det være en langsommelig affære at tjekke alle muligheder fra en ende af, for der er 7·6·5·4·3·2·1=5040 forskellige rækkefølger. Sådanne rækkefølger kalder man i matematik for permutationer:
https://www.dcode.fr/permutations-generator
Nu er opgaven reduceret til en type opgave vi kan løse ved at kigge på knudepunkternes valens, sådan som vi gjorde i den første matematik pusleri-artikel. Euler var den første vi kender til, der benyttede denne tankegang. Og han fandt frem til, som du sikkert også har fundet ud af nu – at det ikke var muligt at gå en aftentur, så man kom over alle broer netop en gang.
Hvad så i dag?
Kigger vi på et moderne kort over Kaliningrad, kan vi se, at situationen har ændret sig. Der er forsvundet nogle broer og der er kommet andre til. De broer, der er rammet ind med rødt svarer til de af de gamle broer, der stadig eksisterer. Bro nummer 2 og nummer 5 fra det gamle kort er forsvundet.
Hvis Euler havde boet i Kaliningrad i dag, ville han så kunne gå den ønskede gåtur over de resterende fem broer (de broer, der er indrammet med rød ovenfor)?
Hvad hvis vi inddrager de tre nye broer, så der i alt er otte, kan han så både starte og slutte hjemme – og betyder det noget hvor han bor?
Den sidste opgave fra første artikel
Det gjaldt om at krydse alle 16 stykker væg netop engang hver med en streg. Hvis du ikke allerede har prøvet opgaven, så giv den et skud. Her ser du et forsøg, som i hvert fald ikke er en løsning.
Her er der 16 stykker væg. Det giver i alt:
16!=16·15·14·13·12·11·10·9·8·7·6·5·4·3·2·1=20.922.789.888.000 forskellige rækkefølger (permutationer) af vægge. Igen kan vi nøjes med at tjekke halvdelen; hver streg viser to muligheder, da man kan starte i begge ender. Og igen vil der være en del permutationer, som er umulige på forhånd, da ikke alle vægge kan forbindes direkte. Men det giver stadig mange millioner muligheder at tjekke igennem.
Godt, at Euler fandt ud af at tænke i grafer!
Det er dog langt fra alle problemer inden for grafteori, som vi ved, hvordan vi skal løse. Som det fremgår af eksemplet med de 16 vægge, så skal der ikke mange knudepunkter og kanter til før at antallet af muligheder bliver så store, at selv vores hurtigste og kraftigste computer må give op.
Forestil dig at du er direktør i NETTO og du skal rundt og besøge alle NETTO-butikker i Danmark, der er omkring 500. Du vil selvfølgelig gerne køre den korteste vej, men hvis du vil være helt sikker og tjekke alle muligheder før du kører, så kommer du aldrig afsted!
Antallet af mulige rejseruter der går forbi de 500 butikker er et tal der har over 1000 cifre (500!≈1,22·101134, se tallet nedenfor). De fleste har det sikkert sådan, at en milliard er et stort tal, men det er altså kun 10 cifre. Selv hvis Euler havde haft en moderne computer tilbage i 1736 og havde sat den i gang med at tjekke muligheder, så ville den knap være kommet i gang på nuværende tidspunkt.
500!=1220136825991110068701238785423046926253574
342803192842192413588385845373153881997605496447
502203281863013616477148203584163378722078177200
480785205159329285477907571939330603772960859086
270429174547882424912726344305670173270769461062
802310452644218878789465754777149863494367781037
644274033827365397471386477878495438489595537537
990423241061271326984327745715546309977202781014
561081188373709531016356324432987029563896628911
658974769572087926928871281780070265174507768410
719624390394322536422605234945850129918571501248
706961568141625359056693423813008856249246891564
126775654481886506593847951775360894005745238940
335798476363944905313062323749066445048824665075
946735862074637925184200459369692981022263971952
597190945217823331756934581508552332820762820023
402626907898342451712006207714640979456116127629
145951237229913340169552363850942885592018727433
795173014586357570828355780158735432768888680120
399882384702151467605445407663535984174430480128
938313896881639487469658817504506926365338175055
478128640000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000
000000000000000000000000000000000000
De første 720 permutationer af tallene 1, 2, 3, 4, 5, 6, 7 - netop alle dem, der starter med tallet 1. Ekstraopgave
Her er tre huse, et vandværk, et gasværk og et elkraftværk. De tre huse skal alle hver have en direkte ledning (tegnet streg) med hhv vand, gas og el fra de tre værker. Ingen af ledningerne må krydse hinanden.
Kan du klare den?
Start debatten med en kommentar