![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/langpt-640px-Petersen1_tiny.svg.png&w=640&q=50)
Grafo simétrico
De Wikipedia, a enciclopédia encyclopedia
No campo da matemática da teoria dos grafos, um grafo G é simétrico (ou arco-transitivo) se, dados quaisquer dois pares de vértices ligados u1—v1 e u2—v2 de G , há um automorfismo
- f : V(G) → V(G)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/200px-Petersen1_tiny.svg.png)
tal que
- f(u1) = u2 and f(v1) = v2.[1]
Em outras palavras, um grafo é simétrico se seu grupo de automorfismo age transitivamente em pares ordenados de vértices ligados (isto é, sobre as arestas consideradas como tendo um sentido).[2] Tal grafo é chamado às vezes também 1-arco-transitivo[2] ou flag-transitivo.[3]
Por definição (ignorando u1 e u2), um grafo simétrico sem vértices isolados deve também ser vértice-transitivo.[1] Como a definição acima mapeia uma aresta a outra, um grafo simétrico também deve ser aresta-transitivo. Contudo, um grafo aresta-transitivo não precisa ser simétrico, uma vez que a—b pode mapear a c—d, mas não a d—c. Grafos simétricos, por exemplo, aão aresta-transitivos e regulares, mas não vértice-transitivos.
Todo grafo simétrico conexo deve, portanto, ser tanto vértice-transitivo quanto aresta-transitivo, e o inverso é verdadeiro para grafos de grau ímpar.[3] No entanto, para graus pares, existem grafos conectados que são vértice-transitivos e aresta-transitivos, mas não simétricos.[4] Tais grafos são denominados meio-transitivos.[5] O menor grafo conexo meio-transitiva é o grafo de Holt, com grau 4 e 27 vértices.[1][6] De forma confusa, alguns autores usam o termo "grafo simétrico" para significar um grafo que é vértice-transitivo e aresta-transitivo, ao invés de um grafo arco-transitivo. Tal definição inclui grafos meio-transitivos, que são excluídos pela definição acima.
Um grafo distância-transitivo é aquele em que em vez de considerar pares de vértices ligados (i.e. vértices a uma distância de um), a definição abrange dois pares de vértices, cada um à mesma distância. Tais grafos são automaticamente simétricos, por definição.[1]
Um t-arco é definido como uma sequência de t+1 vértices ligados, com quaisquer vértices repetidos estando a mais de 2 passos distante. Um grafo t-transitivo é um grafo tal que o grupo de automorfismo atua transitivamente nos t-arcos, mas não nos (t+1)-arcos. Uma vez que os 1-arcos são simplesmente arestas, qualquer grafo simétrico de grau 3 ou superior tem que ser t-transitivo para algum t, e o valor de t pode ser usado para além disso classificar grafos simétricos. O cubo é 2-transitivo, por exemplo.[1]