![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/0/06/Heawood_Graph.svg/langpt-640px-Heawood_Graph.svg.png&w=640&q=50)
Grafo de Heawood
De Wikipedia, a enciclopédia encyclopedia
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.[1] 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.
Grafo de Heawood | |
---|---|
![]() | |
Nomeado em honra a | Percy John Heawood |
vértices | 14 |
arestas | 21 |
Raio | 3 |
Diâmetro | 3 |
Cintura | 6 |
Automorfismos | 336 (PGL2(7)) |
Número cromático | 2 |
Índice cromático | 3 |
Propriedades | Cúbico gaiola distância-transitivo distância-regular Toroidal Hamiltoniano simétrico |
É 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 é PGL2(7).[2]
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.[3][4] 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.[5]