Heawoodův graf

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.

Minimální křížení

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

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