Heawoodův graf je neorientovaný graf o 14 vrcholech a 21 hranách, známý z teorie grafů. Každý vrchol je spojen třemi hranami a všechny cykly v grafu mají šest nebo více hran.

Heawoodův graf.

Heawoodův graf je pojmenován po britském matematikovi jménem Percy John Heawood, který v roce 1890 dokázal, že každé rozdělení tóru do polygonů může být obarveno nejvýše sedmi barvami. Heawoodův graf tvoří rozdělení tóru na sedm vzájemně propojených oblastí, čímž dokázal, že tato hranice je těsná. Jedná se o toroidní graf.

Minimální křížení editovat

 
Heawoodův graf při minimálním křížení.

Problém minimálního křížení, kdy hledáme takové rozmístění vrcholů grafu, abych počet průniků hran byl minimální, má pro Heawoodův graf řešení 3.

Externí odkazy editovat