Etikettarkiv: Gulisintagning

Kartor, grafer och kaffemuggar

De som har deltagit i gulisintagningen tidigare under hösten känner kanske till muggen ovan. Vid matematikpunkten på Wall Street Bar fick gulisarna till uppgift att med tusch koppla varje hus till varje enhet (el, vatten, gas) utan att förbindelserna korsar varandra. De fick med andra ord lösa det s.k. Three Utilities Problem. Om du vill fundera på problemet själv och undvika spoilers, gör det nu (Eller kolla på 3Blue1Browns video om temat, rekommenderas varmt).

Det väsentliga som gjorde uppgiften lösbar är att en mugg är (topologiskt sett) fundamentalt annorlunda än ett klot eller ett papper. Om man tänker sig att muggen är gjord av lera, kan man utan att bryta den eller slå nya hål forma om den till en donits. Med andra ord är kaffemuggen en torus, en sluten kropp med ett hål. Det visar sig att uppgiften är lösbar på en torus, men inte på ett klot eller ett papper!

 

Muggproblemet kan förvånansvärt nog ge oss insikt om ett helt annat problem: Om du har en karta där varje land är en sammanhängande region, hur många färger behöver du för att färglägga varje land utan att två grannländer får samma färg? Då kartan är ritad på ett papper eller en boll visar det sig att högst fyra färger behövs; resultatet är känt som Four color theorem.

Kartan över Frankrikes provinser behöver fyra färger

Men om kartan är ritad på en annan slags kropp, t.ex. en torus, räcker fyra färger till? För att förstå denna situation bättre söker vi ett ”renare” sätt att rita vår karta. Vi ersätter först varje region med en punkt. Sedan ritar vi streck mellan två punkter ifall de motsvarande regionerna gränsar till varandra. Det vi får är en graf: en samling noder (punkter) och kanter (streck) mellan dessa. I själva verket är det en planär graf, dvs. den kan ritas utan att två streck korsar varandra.

En karta och dess motsvarande graf

Det visar sig att varje karta motsvarar en planär graf och vice versa. Så istället för att granska kartor på en torus, kan vi kolla på planära grafer på en torus: Hur många färger behövs för att färglägga noderna så att två grannar inte får samma färg? Men här kommer insikten från muggproblemet in: Grafen som bildas i Three Utilities Problem är inte planär på ett papper (dvs två kanter måste korsa varandra) men den är planär på en torus. Det betyder att mängden av planära grafer på en torus är fundamentalt större!

Kan vi alltså hitta en graf som kräver mer än fyra färger? Grafen i muggproblemet kan färgas med endast två färger. Men t.ex. den kompletta grafen K5 kräver 5 färger och kan ritas på en kaffemugg utan att två kanter korsar varandra.

K5 ritad på en kaffemugg utan att två kanter korsar

Och vad är det högsta antalet färger vi kan behöva?
https://mathsgear.co.uk/products/7-colour-torus-mug

Det mest spännande inom matematiken är då två koncept som verkar mycket annorlunda egentligen är nära sammankopplade. Många situationer där vi beaktar föremål (länder) och förbindelser mellan dem (gränser) kan uttryckas med hjälp av grafteori. Men en grafs egenskaper hänger inte bara på grafen själv, utan också på kroppen den ritas på. Kaffemuggen är ett intressant topologiskt föremål, inte bara en pryl för att hälla i sig kaffe.