Abrir menu principal
Translation Latin Alphabet.svg
Este artigo ou seção está a ser traduzido. Ajude e colabore com a tradução.
Um grafo antissimé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.

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 Cayleyanti-simétricoassimétrico

Grafos antissimétricos foram primeiramente introduzidos sob o nome de "dígrafos antissimétricos" por Tutte, 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çãoEditar

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 grafico 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 bipartidosEditar

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, W. T. (1967). «Antisymmetrical digraphs». Canadian Journal of Mathematics. 19. pp. 1101–1117 
  2. a b GOLDBERG, Andrew V.; KARZANOV, Alexander V. (1996). «Path problems in skew-symmetric graphs». Combinatorica. 16 (3). pp. 353–382. doi:10.1007/BF01261321 
  3. COOK, Matthew (2003). "Still life theory", New Constructions in Cellular Automata. [S.l.]: Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. p. 93–118 
  4. HUI, Peter; SCHAEFER, Marcus; ŠTEFANKOVIČ, Daniel (2004). «Train tracks and confluent drawings». Proc. 12th Int. Symp. Graph Drawing. Col: Lecture Notes in Computer Science. 3383. [S.l.]: Springer-Verlag. p. 318–328 
  5. EDMONDS, Jack; JOHNSON, Ellis L. (1970). «Combinatorial Structures and their Applications: Proceedings of the Calgary Symposium, June 1969». New York: Gordon and Breach  |capítulo= ignorado (ajuda). Reimpresso em Combinatorial Optimization — Eureka, You Shrink!, Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, pp. 27–30, DOI:10.1007/3-540-36478-1 3.