Heawoodův graf

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

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.

• Obrázky, zvuky či videa k tématu Heawoodův graf na Wikimedia Commons
• Heawoodův graf (anglicky)