Grafer och nätverkPlana diagram
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.
Den
Grafen i de tre verktygspusslet är den
Planhet
Detta är ett plant diagram, men
Eulers formel
Alla plana diagram delar upp planet som de dras på i ett antal områden, kallade ansikten .
När du jämför dessa siffror kommer du att märka att antalet kanter alltid är
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
F | V | E |
0 | 1 | 0 |
0 + 1 = 0 + 1
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.
Många plana diagram ser mycket lika ut som nät av
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 +