Grafer och nätverkPlana diagram

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 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 .

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 ett mindre större samma sak ä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 ...

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 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 + .