Planära grafer



I ett sällskap med många personer kan man leka en lek som kallas “knuten”. Alla ställer sig i en ring och sluter ögonen. Sedan sträcker alla fram båda sina händer och börjar gå mot mitten. Alla ska ta tag i två andra händer med sina egna.

Efter att alla är klara med det öppnar man ögonen. Målet är nu att lösa upp “knuten” som bildats utan att släppa taget med händerna. Det gäller att bilda en stor ring igen (det kan också hända att det blir flera ringar).

Ett liknande spel är Planarity, fast personerna i spelet kan ha fler än två händer. Målet är att lösa upp all tilltrassel så att inga par av händer måste hållas över varandra.

Personer är representerade med punkter och en kant som går mellan två punkter visar att de två personerna håller handen. Alla spelande har väldigt uttänjbara händer. Försök att klara några nivåer! (Jag kom till Level 7.)

Sådana här bilder kallas grafer, om de går att “plana ut” på det här snygga sättet (så att inga två kanter korsar varandra) kallas de planära. Det är svårt att se direkt huruvida en graf är planär eller inte, däremot uppfyller alla planära grafer följande formel.

Eulers formel

En graf är ritad på ett plan på så sätt, att inga två kanter korsar varandra. Om V är antalet hörn i grafen, E – antalet kanter och F – antalet områden som planet delas upp i, så gäller:

V – E + F = 2

Att det blev just talet 2 beror på att man ritade på ett plan. Ritar man grafer på andra konstiga ytor blir det ett annat specifikt tal just för denna yta. Det talet kallas ytans eulerkaraktäristik.

2 reaktioner till “Planära grafer”

  1. Förtydligande: planära grafer behöver inte ha raka streck, de kan vara krokiga också, det viktigaste är att det inte korsar varandra.

    Frågan är nu om det finns ett exempel på en graf som är planär, men som inte går att rita med raka kanter. Jag tror att det borde finnas …

Kommentera