Grafo antissimétrico

Um grafo antissimétrico.
Famílias de grafos definidos por seus automorfismos
distância-transitivodistância-regularfortemente regular
simétrico (arco-transitivo)t-transitivo, t ≥ 2.

(se conectado)
transitivo nos vértices e nas arestasaresta-transitivo e regulararesta-transitivo
vértice-transitivoregular
grafo de Cayleyantissimétricoassimétrico


No campo da matemática da teoria dos grafos, um grafo antissimétrico é um grafo orientado que é isomórfico ao seu próprio grafo transposto, o grafo formado pela inversão de todas as suas arestas. O isomorfismo necessita ser uma involução sem nenhum ponto fixo.

Grafos antissimétricos foram primeiramente introduzidos sob o nome de "dígrafos antissimétricos" por W.T. Tutte em 1967.[1] Eles surgiram quando da modelagem da busca de caminhos alternados e ciclos alternados em algoritmos para encontrar acoplamentos em grafos, em testes se um padrão still life no jogo da vida, desenvolvido pelo matemático britânico John Horton Conway, pode ser dividido em componentes mais simples, em desenho de grafos, e em grafos de implicação usados para resolver eficientemente o problema da 2-satisfatibilidade.

Definição

Conforme definido, por exemplo, por Goldberg e Karzanov (1996)[2], um grafo antissimétrico G é um grafo direcionado, junto com uma função σ mapeando vértices de G a outros vértices de G, satisfazendo as seguintes propriedades:

  1. Para cada vértice v, σ(v) ≠ v
  2. Para cada vértice v, σ(σ(v)) = v
  3. Para cada aresta (u,v), (σ(v),σ(u)) também deve ser uma aresta.

Pode-se usar a terceira propriedade para estender σ para uma função de inversão de orientação das arestas de G.

O grafo transposto de G é o grafo formado pela inversão de todas as arestas de G, e σ define um isomorfismo de grafos de G para a sua transposição. No entanto, em um gráfico anti-simétrico, é adicionalmente necessário que o isomorfismo forme pares de cada vértice com um vértice diferente, ao invés de permitir a um vértice ser mapeado para si pelo isomorfismo ou agrupar mais de dois vértices em um ciclo de isomorfismos.

Um caminho ou um ciclo em um grafo anti-simétrico é dito ser regular se, para cada vértice v do caminho ou do ciclo, o vértice correspondente σ(v) não faz parte do caminho ou do ciclo.

Grafos switch e grafos bipartidos

um grafo anti-simétrico pode de forma equivalente ser definido em termos de um grafo switch (para usar a terminologia de Cook, 2003[3]), um grafo não direcionado em que as arestas incidentes a cada vértice são divididas em dois subgrupos. Cada vértice do grafo switch corresponde a dois vértices do grafo antissimétrico, e cada aresta do grafo alternado corresponde a duas arestas do grafo antissimétrico. Esta equivalência é a utilizada por Goldberg e Karzanov (1996)[2] para modelar problemas de acoplamento em termos de grafos antissimétricos; nesta aplicação, os dois subconjuntos de arestas em cada vértice são as arestas não acopladas e as arestas acopladas. Cook visualiza os vértices de um grafo switch como pontos onde várias faixas de um trilho de trem se reúnem: se um trem entra em um switch através de um trilho que vem de uma direção, deve sair através de um trilho na outra direção.

O problema de se encontrar curvas suaves que não se auto-interceptam entre os pontos dados em um trilho de trem vem em testar se determinados tipos de desenhos de grafos são válidos[4] e pode ser modelado como a busca de um caminho comum em um grafo anti-simétrico.

Um conceito relacionado é o de grafo bidirecionado de Edmonds e Johnson, 1969[5], um grafo em que cada uma das duas extremidades de cada aresta pode ser tanto uma cabeça ou uma cauda, independentemente do outro lado.

Referências

  1. ↑ Tutte 1967.
  2. ↑ a b Goldberg & Karzanov 1996.
  3. ↑ Griffeath & Moore 2003, pp. 93-118.
  4. ↑ Hui et al. 2007.
  5. ↑ Calgary 1970, pp. 27-30.

Bibliografia