Grafo antissimétrico
De Wikipedia, a enciclopédia encyclopedia
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.