Ordlista

Välj ett av nyckelorden till vänster ...

Grafer och nätverkPlana diagram

Lästid: ~25 min

Här är ett annat pussel som är relaterat till grafteori.

I en liten by finns det tre hus och tre bruksanläggningar som producerar vatten, el och gas. Vi måste ansluta var och en av banorna till var och en av verktygsanläggningarna, men på grund av byns utformning får de olika rören och kablarna inte gå över.

Försök att ansluta vart och ett av husen till vart och ett av verktygsföretagen nedan, utan att några av dina linjer korsar varandra:

Precis som Königsbergbroarna tidigare upptäcker du snabbt att detta problem också är omöjligt. Det verkar som att vissa grafer kan ritas utan överlappande kanter - dessa kallas plana diagram - men andra kan inte.

K3 är plan.

K4 .

K5 .

Den kompletta grafen K5 är den minsta grafen som inte är plan. Alla andra diagram som innehåller K5 som en subgraf på något sätt är inte heller plan. Detta inkluderar K6 , K7 och alla större kompletta diagram.

Grafen i de tre verktygspusslet är den tvåpartsgrafen K3,3 . Det visar sig att alla icke-plana diagram antingen måste innehålla en K5 eller a K3,3 (eller en underindelning av dessa två grafer) som en undergraf. Detta kallas Kuratowski's teorem .

Planhet

Detta är ett plant diagram, men ${n} vertikaler har skrapats upp. Ordna om topparna så att ingen av kanterna överlappar varandra.

Eulers formel

Alla plana diagram delar upp planet som de dras på i ett antal områden, kallade ansikten .

vertikaler ansikten kanter 11 vertikaler + ansikten

vertikaler ansikten kanter 15 vertikaler + ansikten

vertikaler ansikten kanter 25 vertikaler + ansikten

När du jämför dessa siffror kommer du att märka att antalet kanter alltid är än antalet ansikten plus antalet vertikaler. Med andra ord, F + V = E + 1. Detta resultat kallas Eulers ekvation och är uppkallad efter samma matematiker som löste problemet med Königsberg Bridges.

Tyvärr finns det oändligt många grafer och vi kan inte kontrollera var och en för att se om Eulers ekvation fungerar. Istället kan vi försöka hitta ett enkelt bevis som fungerar för alla diagram ...

FVE
010

0 + 1  =  0 + 1

The simplest graph consists of a single vertex. We can easily check that Euler’s equation works.
Let us add a new vertex to our graph. We also have to add an edge, and Euler’s equation still works.
If we want to add a third vertex to the graph we have two possibilities. We could create a small triangle: this adds one vertex, one face and two edges, so Euler’s equation still works.
Instead we could simply extend the line by one: this adds one vertex and one edge, and Euler’s equation works.
Let’s keep going: if we now create a quadrilateral we add one vertex, two edges and one face. Euler’s equation still works.

Alla (begränsade) diagram kan konstrueras genom att börja med ett toppunkt och lägga till fler vertikaler en efter en. Vi har visat att, oavsett sätt vi lägger till nya vertikaler, är Eulers ekvation giltig. Därför är det giltigt för alla diagram.

Den process vi har använt kallas matematisk induktion . Det är en mycket användbar teknik för att bevisa resultat i oändligt många fall, helt enkelt genom att börja med det enklaste fallet, och visa att resultatet håller i varje steg när man bygger mer komplexa fall.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Många plana diagram ser mycket lika ut som nät av polyeder , tredimensionella former med polygonala ytor. Om vi tänker på polyeder som är gjorda av elastiska band, kan vi föreställa oss att sträcka ut dem tills de blir plana, plana grafer:

Detta betyder att vi kan använda Eulers formel inte bara för plana diagram utan också för alla polyhedra - med en liten skillnad. När man omvandlar polyhedraen till diagram, försvinner en av ansiktena: den övre ytan på polyhedraen blir ”utsidan”; av graferna.

Med andra ord, om du räknar antalet kanter , ansikten och toppar av alla polyeder, du kommer att hitta det F + V = E + .

icosahedron 20 ansikten 12 vertikaler 30 kanter

Rhombicosidodecahedron 62 Ansikten 60 vertikaler 120 kanter

Trunkerad Icosahedron 32 ansikten (12 svarta, 20 vita) 60 vertikaler 90 kanter

Archie