|
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[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çõesO 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çõesO 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 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 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. SimetriasO 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
|
||||||||||||||||||||||||||
