Grafo de Petersen

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.
Grafo de Petersen
Petersen1 tiny.svg

O gráfico de Petersen é mais comumente desenhado como um pentágono com um pentagrama no interior, com cinco raios
Nomeado em honra a Julius Petersen
vértices 10
arestas 15
Raio 2
Diâmetro 2
Cintura 5
Automorfismos 120 (S5)
Número cromático 3
Índice cromático 4
Propriedades Cúbico
grafo fortemente regular
distância-transitivo

No campo da matemática da teoria dos grafos o grafo de Petersen é um grafo não-orientado com 10 vértices e 15 arestas. É um pequeno grafo que serve como um exemplo útil e contra-exemplo para muitos problemas em teoria dos grafos. O grafo de Petersen é nomeado em honra a Julius Petersen, que em 1898 construiu o menor grafo cúbico sem ponte cujas arestas não podem ser coloridas com somente três cores[1] . Embora o grafo seja geralmente creditado a Petersen, ele tinha, de facto, aparecido pela primeira vez 12 anos antes, em 1886[2] .

Donald Knuth afirma que o grafo de Petersen é "uma configuração notável que serve como um contra-exemplo para muitas previsões otimistas sobre o que poderia ser verdade para os grafos em geral."[3]

Construções[editar | editar código-fonte]

O grafo de Petersen é o complementar do grafo linha de K_5. É também o grafo Kneser KG_{5,2}; isso significa que ele tem um vértice para cada subconjunto de dois elementos de um conjunto de 5 elementos, e dois vértices são conectados por uma aresta se e somente se os correspondentes subconjuntos de dois elementos são disjuntos entre si. Como um grafo de Kneser da forma KG_{2n-1,n-1} é um exemplo de um grafo ímpar.

Geometricamente, o grafo de Petersen é o grafo formado pelos vértices e arestas do hemi-dodecaedro, ou seja, um dodecaedro com os pontos opostos, linhas e faces identificadas em conjunto.

Incorporações[editar | editar código-fonte]

O grafo de Petersen é não-planar. Qualquer grafo não planar tem como menores tanto o grafo completo K_5, quanto o grafo bipartido completo K_{3,3}, mas o grafo de Petersen tem ambos os menores. O K_5 menor pode ser formado restringindo-se as arestas de um acoplamento perfeito, por exemplo as cinco arestas curtas na primeira figura. O menor K_{3,3} pode ser formado se deletando um vértice (por exemplo, o vértice central do desenho do 3-simétrico) e contratando uma aresta incidente para cada vizinho do vértice que foi excluído.

O grafo de Petersen tem número de cruzamento 2.

O mais comum e simétrico desenho do plano do grafo de Petersen, como um pentagrama dentro de um pentágono, tem cinco cruzamentos. No entanto, este não é o melhor desenho que minimiza os cruzamentos; existe um outro desenho (mostrado na figura), com apenas dois cruzamentos. Assim, o grafo de Petersen tem número de cruzamento 2. Em um toro o grafo de Petersen pode ser desenhado sem cruzamentos de arestas; tem, portanto, gênero orientável 1.

O grafo de Petersen é um grafo distância-unidade: ele pode ser desenhado no plano com cada aresta tendo comprimento de uma unidade.

O grafo de Petersen também pode ser desenhado (com cruzamentos) no plano de tal forma que todas as arestas tenham o mesmo comprimento. Ou seja, ele é um grafo distância-unidade.

A mais simples superfície não orientável em que o grafo de Petersen pode ser incorporado sem cruzamentos é o plano projetivo. Esta é a incorporação dada pela construção em hemi-dodecaedro do grafo de Petersen. A incorporação no plano projetivo também pode ser formada a partir do desenho padrão pentagonal do gráfico Petersen, colocando uma superfície cross-cap dentro da estrela de cinco pontas no centro do desenho, e dirigundo as arestas da estrela através desta cross-cap; o desenho resultante tem seis faces pentagonais. Esta construção forma um mapa regular e mostra que o grafo de Petersen tem um género não-orientável 1.

Simetrias[editar | editar código-fonte]

O grafo de Petersen é fortemente regular (com assinatura srg(10,3,0,1)). É também simétrico, o que significa que é aresta-transitivo e vértice-transitivo. Mais fortemente, é de 3-arcos-transitivo: cada caminho de três arestas dirigidas no grafo de Petersen pode ser transformado em qualquer outro tipo de percurso por uma simetria do grafo.[4]


Referências

  1. BROUWER, Andries E.. The Petersen graph. Visitado em 2010-10-25.
  2. KEMPE, A. B.. (1886). "A memoir on the theory of mathematical form". Philosophical Transactions of the Royal Society of London 177: 1–70. DOI:10.1098/rstl.1886.0002.
  3. Knuth, Donald E., The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching 
  4. Babai, László. In: Lovász, Ronald L.; Grötschel, Martin; László, László. Handbook of Combinatorics. [S.l.]: North-Holland, 1995. Capítulo Automorphism groups, isomorphism, reconstruction. p. 1447–1540. vol. I. Corollary 1.8. .