Isomorfismo de grafos
Em teoria dos grafos, um isomorfismo dos grafos G e H é uma bijeção entre os conjuntos de vértices de G e H
Imagem: Kanijoman · BY · Openverse
Os dois grafos abaixo são isomorfos, apesar de suas representações diferentes.
A noção formal de "isomorfismo", por exemplo, de "isomorfismo gráfico", captura a noção informal de que alguns objetos têm "a mesma estrutura", se alguém ignora distinções individuais dos componentes de objetos "atômicos" em questão, consulte o exemplo acima. Sempre que a individualidade dos componentes "atômicos" (vértices e arestas, para grafos) é importante para a correta representação do que é modelado por grafos, o modelo é refinado pela imposição de restrições adicionais sobre a estrutura, e outros objetos matemáticos são utilizados: digrafos, grafos rotulados, grafos coloridos, árvores enraizadas e assim por diante. A relação de isomorfismo pode também ser definida para todas essas generalizações de grafos: o isomorfismo bijeção deve preservar os elementos da estrutura que define o tipo de objeto em questão: arcos, rótulos, cores de vértices/arestas, a raiz da árvore de raízes, etc.
Teorema de Whitney
O teorema de isomorfismo de grafos de Whitney, demonstrado por H. Whitney, afirma que dois grafos conexos são isomorfos se e somente se o seu grafos de linha são isomórficos, com uma única exceção: K3, o grafo completo em três vértices, e o grafo bipartido completo K1,3, que não são isomórficos, mas ambos têm K3 como seu grafo de linha. O teorema de grafos de Whitney pode ser estendido para hipergrafos.
Abordagem algorítmica
Enquanto isomorfismos de grafos podem ser estudados de forma clássica da Matemática, como exemplificado pelo teorema de Whitney, é reconhecido que é um problema a ser enfrentado com uma abordagem algorítmica. O problema computacional de determinar se dois grafos finitos são isomorfos é chamado o problema do isomorfismo de grafos. Suas aplicações práticas incluem principalmente quimioinformática, matemática química (identificação de compostos químicos), e automação de projeto eletrônico (verificação da equivalência das diferentes representações do desenho de um Circuito eletrônico Curiosamente, é também um dos poucos problemas em teoria computacional da complexidade pertencente à classe NP, mas não se sabe se pertence a nenhum de seus conhecidos subconjuntos (e, se P ≠ NP, disjuntos):P e NP-completo. É um de apenas dois, dos 12 totais, problemas listados em Garey e Johnson (1979) cuja complexidade está por se resolver. Ou seja, eles não foram provados ser incluídos, nem excluídos, das classes P ou NP-completo.
