{"id":2273,"date":"2018-10-02T15:12:59","date_gmt":"2018-10-02T12:12:59","guid":{"rendered":"http:\/\/spektrum.fi\/spektraklet\/?p=2273"},"modified":"2018-10-02T15:12:59","modified_gmt":"2018-10-02T12:12:59","slug":"kartor-grafer-och-kaffemuggar","status":"publish","type":"post","link":"https:\/\/spektrum.fi\/spektraklet\/kartor-grafer-och-kaffemuggar\/","title":{"rendered":"Kartor, grafer och kaffemuggar"},"content":{"rendered":"

\"\"<\/a><\/p>\n

De som har deltagit i gulisintagningen tidigare under h\u00f6sten k\u00e4nner kanske till muggen ovan. Vid matematikpunkten p\u00e5 Wall Street Bar fick gulisarna till uppgift att med tusch koppla varje hus till varje enhet (el, vatten, gas) utan att f\u00f6rbindelserna korsar varandra. De fick med andra ord l\u00f6sa det s.k. Three Utilities Problem<\/a>. Om du vill fundera p\u00e5 problemet sj\u00e4lv och undvika spoilers, g\u00f6r det nu (Eller kolla p\u00e5\u00a03Blue1Browns video<\/a> om temat, rekommenderas varmt).<\/p>\n

Det v\u00e4sentliga som gjorde uppgiften l\u00f6sbar \u00e4r att en mugg \u00e4r (topologiskt sett) fundamentalt annorlunda \u00e4n ett klot eller ett papper. Om man t\u00e4nker sig att muggen \u00e4r gjord av lera, kan man utan att bryta den eller sl\u00e5 nya h\u00e5l forma om den till en donits. Med andra ord \u00e4r kaffemuggen en\u00a0torus<\/em>, en sluten kropp med ett h\u00e5l. Det visar sig att uppgiften \u00e4r l\u00f6sbar p\u00e5 en torus, men inte p\u00e5 ett klot eller ett papper!<\/p>\n

\"\"<\/a><\/p>\n

 <\/p>\n

Muggproblemet kan f\u00f6rv\u00e5nansv\u00e4rt nog ge oss insikt om ett helt annat problem: Om du har en karta d\u00e4r varje land \u00e4r en sammanh\u00e4ngande region, hur m\u00e5nga f\u00e4rger beh\u00f6ver du f\u00f6r att f\u00e4rgl\u00e4gga varje land utan att tv\u00e5 grannl\u00e4nder f\u00e5r samma f\u00e4rg? D\u00e5 kartan \u00e4r ritad p\u00e5 ett papper eller en boll visar det sig att h\u00f6gst fyra f\u00e4rger beh\u00f6vs; resultatet \u00e4r k\u00e4nt som Four color theorem<\/a>.<\/p>\n

\"\"<\/a>
Kartan \u00f6ver Frankrikes provinser beh\u00f6ver fyra f\u00e4rger<\/figcaption><\/figure>\n

Men om kartan \u00e4r ritad p\u00e5 en annan slags kropp, t.ex. en torus, r\u00e4cker fyra f\u00e4rger till? F\u00f6r att f\u00f6rst\u00e5 denna situation b\u00e4ttre s\u00f6ker vi ett ”renare” s\u00e4tt att rita v\u00e5r karta. Vi ers\u00e4tter f\u00f6rst varje region med en punkt. Sedan ritar vi streck mellan tv\u00e5 punkter ifall de motsvarande regionerna gr\u00e4nsar till varandra. Det vi f\u00e5r \u00e4r en graf<\/em>: en samling noder<\/em> (punkter) och kanter<\/em> (streck) mellan dessa. I sj\u00e4lva verket \u00e4r det en\u00a0plan\u00e4r\u00a0<\/em>graf, dvs. den kan ritas utan att tv\u00e5 streck korsar varandra.<\/p>\n

\"\"<\/a>
En karta och dess motsvarande graf<\/figcaption><\/figure>\n

Det visar sig att varje karta motsvarar en plan\u00e4r graf och vice versa. S\u00e5 ist\u00e4llet f\u00f6r att granska kartor p\u00e5 en torus, kan vi kolla p\u00e5 plan\u00e4ra grafer p\u00e5 en torus: Hur m\u00e5nga f\u00e4rger beh\u00f6vs f\u00f6r att f\u00e4rgl\u00e4gga noderna s\u00e5 att tv\u00e5 grannar inte f\u00e5r samma f\u00e4rg? Men h\u00e4r kommer insikten fr\u00e5n muggproblemet in: Grafen som bildas i Three Utilities Problem \u00e4r inte plan\u00e4r<\/strong> p\u00e5 ett papper (dvs tv\u00e5 kanter m\u00e5ste korsa varandra) men den \u00e4r plan\u00e4r<\/strong> p\u00e5 en torus. Det betyder att m\u00e4ngden av plan\u00e4ra grafer p\u00e5 en torus \u00e4r fundamentalt st\u00f6rre!<\/p>\n

Kan vi allts\u00e5 hitta en graf som kr\u00e4ver mer \u00e4n fyra f\u00e4rger? Grafen i muggproblemet kan f\u00e4rgas med endast tv\u00e5 f\u00e4rger. Men t.ex. den kompletta grafen K5<\/sub><\/a> kr\u00e4ver 5 f\u00e4rger och kan ritas p\u00e5 en kaffemugg utan att tv\u00e5 kanter korsar varandra.<\/p>\n

\"\"<\/a>
K5 ritad p\u00e5 en kaffemugg utan att tv\u00e5 kanter korsar<\/figcaption><\/figure>\n

Och vad \u00e4r det h\u00f6gsta antalet f\u00e4rger vi kan beh\u00f6va?
\nhttps:\/\/mathsgear.co.uk\/products\/7-colour-torus-mug<\/a><\/p>\n

Det mest sp\u00e4nnande inom matematiken \u00e4r d\u00e5 tv\u00e5 koncept som verkar mycket annorlunda egentligen \u00e4r n\u00e4ra sammankopplade. M\u00e5nga situationer d\u00e4r vi beaktar f\u00f6rem\u00e5l (l\u00e4nder) och f\u00f6rbindelser mellan dem (gr\u00e4nser) kan uttryckas med hj\u00e4lp av grafteori. Men en grafs egenskaper h\u00e4nger inte bara p\u00e5 grafen sj\u00e4lv, utan ocks\u00e5 p\u00e5 kroppen den ritas p\u00e5. Kaffemuggen \u00e4r ett intressant topologiskt f\u00f6rem\u00e5l, inte bara en pryl f\u00f6r att h\u00e4lla i sig kaffe.<\/p>\n","protected":false},"excerpt":{"rendered":"

De som har deltagit i gulisintagningen tidigare under h\u00f6sten k\u00e4nner kanske till muggen ovan. Vid matematikpunkten p\u00e5 Wall Street Bar fick gulisarna till uppgift att med tusch koppla varje hus till varje enhet (el, vatten, gas) utan att f\u00f6rbindelserna korsar varandra. De fick med andra ord l\u00f6sa det s.k. Three Utilities Problem. Om du vill … Forts\u00e4tt l\u00e4sa Kartor, grafer och kaffemuggar<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":21,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[87,42],"tags":[132,130,133,57,131],"_links":{"self":[{"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/posts\/2273"}],"collection":[{"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/comments?post=2273"}],"version-history":[{"count":9,"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/posts\/2273\/revisions"}],"predecessor-version":[{"id":2290,"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/posts\/2273\/revisions\/2290"}],"wp:attachment":[{"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/media?parent=2273"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/categories?post=2273"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/spektrum.fi\/spektraklet\/wp-json\/wp\/v2\/tags?post=2273"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}