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.
Conforme definido, por exemplo, por Goldberg e Karzanov (1996), 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: 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.
um grafo anti-simétrico pode de forma equivalente ser definido em termos de um grafo switch (para usar a terminologia de Cook, 2003), 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) 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 e pode ser modelado como a busca de um caminho comum em um grafo anti-simétrico.
