Grafo de Heawood

Predefinição:Info/Grafo No campo da matemática da teoria dos grafos o grafo de Heawood é um grafo não-orientado com 14 vértices e 21 arestas. O grafo é cúbico, e todos os ciclos do grafo têm seis ou mais arestas. Todos os menores grafos cúbicos têm ciclos mais curtos, de modo que este grafo é o gaiola-6, o menor grafo cúbico de cintura 6.

É também o grafo de Levi do plano de Fano, o grafo que representa a incidência entre os pontos e linhas nesta geometria. É um grafo distância-regular; o seu grupo de simetrias é PGL₂(7).

Há 24 correspondências perfeitas no grafo de Heawood; para cada correspondência, o conjunto de arestas fora das correspondências forma um ciclo Hamiltoniano. Por exemplo, a figura mostra os vértices do grafo colocados em um ciclo, com as diagonais internas do ciclo formando uma correspondência. Subdividindo as arestas do ciclo em duas correspondências, podemos particionar o grafo de Heawood em três correspondências perfeitas (isto é, usando 3 cores em suas arestas) em oito formas diferentes (Brouwer).

O grafo de Heawood foi batizado em honra de Percy John Heawood, que em 1890 provou que cada subdivisão do toro em polígonos pode ser colorida, no máximo, com sete cores. O grafo de Heawood forma uma subdivisão do toro com sete regiões adjacentes mutuamente, mostrando que esse limite é apertado.

O grafo de Heawood tem número de cruzamento 3, e é o menor grafo cúbico com este número de cruzamento. Incluindo o grafo de Heawood, existem 8 grafos distintos de ordem 14 com número de cruzamento 3.

O grafo de Heawood é um grafo distância-unidade.

Propriedades algébricas

O grupo de automorfismo do grafo de Heawood é isomórfico ao grupo linear projetivo PGL₂(7), um grupo de ordem 336. Ele atua transitivamente sobre os vértices, nas arestas e nos arcos do grafo. Portanto o grafo Heawood é um grafo simétrico. Ele tem automorfismos que levam qualquer vértice para qualquer outro vértice e qualquer aresta para qualquer outra aresta. De acordo com o censo Foster, o grafo de Heawood, referenciado como F014A, é o único grafo cúbico simétrico com 14 vértices.

O polinômio característico do grafo de Heawood é $(x-3)(x+3)(x^2-2{)}^6$. É o único grafo com este polinômio característico, tornando-se um grafo determinado pelo seu espectro.

Incorporado em um Toro

O grafo de Heawood é um grafo toroidal; ou seja, ele pode ser incorporado sem cruzamentos em um toro. Uma incorporação deste tipo coloca seus vértices e arestas em um espaço euclidiano tri-dimensional como o conjunto de vértices e arestas de um poliedro convexo com a topologia de um toro, o poliedro de Szilassi.

Galeria

• 
  O poliedro de Szilassi.
• 
  O grafo de Heawood tem número de cruzamento 3.
• 
  O índice cromático do grafo de Heawood é 3.
• 
  O número cromático do grafo de Heawood é 2.
• 
  A incorporação do grafo de Heawood em um toro (mostrado como um quadrado com condições de contorno periódicas) particionando-o em sete regiões mutuamente adjacentes