Grafo de Petersen

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou seçã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 . É também o grafo Kneser ; 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 é 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 , quanto o grafo bipartido completo , mas o grafo de Petersen tem ambos os menores. O menor pode ser formado restringindo-se as arestas de um acoplamento perfeito, por exemplo as cinco arestas curtas na primeira figura. O menor 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». Consultado em 25 de outubro de 2010 
  2. KEMPE, A. B. (1886). «A memoir on the theory of mathematical form». Philosophical Transactions of the Royal Society of London. 177. pp. 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.