Grafo de Petersen

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. Embora o grafo seja geralmente creditado a Petersen, ele tinha, de facto, aparecido pela primeira vez 12 anos antes, em 1886.

Grafo de Petersen
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

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."

Construções

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

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

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.