Fra tidsplanplanlægning til farvelægning og endda at kaste et teaterstykke, er dette smarte stykke matematik svaret, siger Katie Steckles
“Grafer… er ekstremt effektive til modellering af sæt objekter og forholdet mellem dem”
For nylig bad en ven om hjælp med et vanskeligt problem: De iscenesatte et skuespil, og manuskriptet havde et stort antal karakterer. De ønskede ikke at ansætte en skuespiller for hver rolle, og selvom de kunne fordoble sig, ville de løbe ind i problemer, hvis den samme skuespiller spillede to figurer i en scene.
Heldigvis var jeg den rigtige person til at komme til for at få hjælp. Der er et stykke matematik, der er effektiv til at løse mange sådanne problemer, fra at kaste et skuespil til tidsplanplanlægning – og endda farve ind.
Grafer – Netværk af punkter, der er forbundet med linjer, er ekstremt effektive til modelleringssæt med genstande og forholdet mellem dem, med åbenlyse anvendelser til at beskrive strukturer som computernetværk eller veje mellem byer. Matematikere er ofte især interesseret i egenskaberne ved grafer, fordi de fortæller os noget mere om den underliggende struktur.
En sådan egenskab er graffarve. Dette involverer tildeling af en farve til hvert punkt, så alle to punkter, der er forbundet med en linje, tildeles forskellige farver. At finde det mindste antal farver, der er nødvendige for at gøre dette, kan fortælle os noget nyttigt ved grafens struktur. For eksempel vil en graf med en trekant af punkter, der alle er forbundet til et fjerde punkt i midten, have brug for mindst fire farver for at udfylde den.
En applikation er i problemer, der involverer faktisk farvelægning: givet et billede opdelt i tilsluttede regioner, er der en måde at udfylde det kun ved at bruge et begrænset sæt farver, så tilstødende regioner er forskellige nuancer? Beviset for den fire farveteorem bekræftede, at der for diagrammer, der er trukket på papir, nogensinde vil være nødvendigt. Disse svarer til grafer, der kan tegnes på en side uden nogen linjer, der krydser.
Selv hvis en graf ikke kan trækkes uden krydsninger, kan vi stadig finde det mindste antal farver, der er nødvendige for at udfylde den, og bruge dette til at løse problemer.
En af mine foretrukne anvendelser af graffarve er i planlægningsproblemer: Forestil dig et sæt klasser med et delt sæt studerende. Vi kan tegne en graf, der angiver hver klasse med et punkt, og slutte sig til to point, hvis disse klasser har nogen studerende, der tager begge dele (så de ikke kan ske på samme tid).
Derefter finder vi en måde at farve grafen ved hjælp af færrest mulige farver. Det mindste antal farver fortæller os, hvor mange tidsplaner vi har brug for: Hver farve repræsenterer et sæt klasser uden overlapning hos studerende, så de alle kan ske samtidigt.
Dette kan fortælle dig, hvordan jeg løste min vens problem: Jeg foreslog, at de tegner en graf, der repræsenterede hver karakter med et punkt og deltager i to karakterer med en linje, hvis de optrådte i nogen scener sammen. Farvning af denne graf fortalte dem minimalt derefter nøjagtigt, hvor mange skuespillere de skulle have til at arrangere spillet. En anden sejr for matematik – på med showet!
Katie Steckles er en matematiker, lektor, YouTuber og forfatter med base i Manchester, UK. Hun er også rådgiver for LektieForum’s Puzzle Column, BrainTwister. Følg hende @STECKS
For andre projekter kan du besøge newscientist.com/maker