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

$f\colon V(G)\to V(H)\,\!$

de tal forma que quaisquer dois vértices u e v de G são adjacentes em G se e somente se ƒ(u) e ƒ(v) são adjacentes em H. Este tipo de bijeção é comumente chamado de "bijeção com preservação de arestas", de acordo com a noção geral de isomorfismo sendo uma bijeção de preservação-de-estrutura.

Na definição acima, os grafos são entendidos como grafos não dirigidos, não-rotulados e não ponderados. No entanto, a noção de isomorfismo pode ser aplicada a todas as outras variantes da noção de grafo, somando os requisitos necessários para preservar os elementos adicionais correspondentes da estrutura: as direções do arco, os pesos das arestas, etc, com a seguinte exceção. Quando se fala em rótulo com rótulos exclusivos, geralmente tirados do intervalo inteiro 1 ,...,n, onde n é o número dos vértices do grafo, dois grafos rotulados são ditos isomórficos se os grafos subjacentes correspondentes não rotulados são isomórficos.

Se um isomorfismo existe entre dois grafos, então os grafos são chamados de isomorfos e nós denotamos por $G\simeq H$. No caso, quando a bijeção é um mapeamento de um grafo em si mesmo, ou seja, quando G e H são um e o mesmo grafo, a bijeção é chamada de automorfismo de G.

O isomorfismo de grafos é uma relação de equivalência em grafos e, como tal, particiona as classes de todos os grafos em classes de equivalência. Um conjunto de grafos isomorfos entre si é chamado de classe de isomorfismo de grafos.

Exemplo

Os dois grafos abaixo são isomorfos, apesar de suas representações diferentes.

Grafo G	Grafo H	Um isomorfismo entre G e H
		ƒ(a) = 1 ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7

Motivação

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.

A noção de "isomorfismo de grafos" permite-nos distinguir as propriedades de grafos inerentes às estruturas dos próprios grafos das propriedades associadas com as representações do grafo: desenho dos grafos, estruturas de dados para grafos, rótulos de grafos, etc. Por exemplo, se um grafo tem exatamente um ciclo, em seguida, todos os grafos da sua classe de isomorfismo também têm exatamente um ciclo. Por outro lado, no caso comum quando os vértices de um grafo são (representados por) inteiros 1, 2, ... N, então a expressão

$\sum _{v\in V(G)}v\cdot {\text{deg }}v$

pode ser diferente para dois grafos isomorfos.

Reconhecimento de isomorfismo de grafos

Teorema de Whitney

A exceção do teorema de Whitney: estes dois grafos não são isomórficos, mas tem grafos de linha isomórfica.

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: K₃, o grafo completo em três vértices, e o grafo bipartido completo K_1,3, que não são isomórficos, mas ambos têm K₃ 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.

Sua generalização, o problema do isomorfismo de subgrafos, é sabido ser NP-Completo.

As principais áreas de pesquisa para o problema é o projeto de algoritmos rápidos, tanto para o problema geral quanto para classes especiais de grafos, e investigações teóricas de sua complexidade computacional.

Ver também

• Homomorfismo de grafos
• Problema do isomorfismo de subgrafos
• Automorfismo de grafos