Mesclar gráficos semelhantes baseados unicamente na estrutura do gráfico?

5

Eu estou procurando (ou tentando projetar) uma técnica para combinar nós de gráficos muito similares baseados na estrutura do gráfico *. Nos exemplos abaixo, o gráfico superior tem 5 nós e o gráfico inferior tem 6 nós. Eu gostaria de combinar os nós do gráfico superior com os nós no gráfico inferior, de modo que os nós "0" correspondam, e os nós "1" correspondam, etc. Isso parece logicamente possível, porque eu posso fazer isso no meu cabeça para estes exemplos simples. Agora só preciso expressar minha intuição no código. Existem algoritmos ou padrões estabelecidos que eu possa considerar?

(* Quando digo com base na estrutura do gráfico, quero dizer que a solução não deve depender dos rótulos do nó; os rótulos numéricos nos nós são apenas para demonstração.)

ATUALIZAÇÃO: Foi corretamente apontado que usando apenas a estrutura, a maioria desses gráficos não pode ser resolvida com 100% de precisão. Eu adicionei alguns pensamentos a cada gráfico.

Também estou interessado no desempenho de qualquer solução potencial. Quão bem eles vão escalar? Posso mesclar gráficos com milhões de nós?

Em casos mais complexos, reconheço que a melhor solução pode estar sujeita a interpretação. Ainda assim, estou esperando uma maneira "boa" de mesclar gráficos complexos.

(Estes são gráficos direcionados; a parte mais espessa de uma aresta representa a cabeça.)

Estegráficoéumciclocom1nó"anexado ao exterior". Depois de anexar um segundo nó ao exterior, não é possível determinar se o novo nó (nó 5) está ligado ao nó 1 ou 3. Os 4 nós que compõem o ciclo também não podem ser perfeitamente combinados. Osnós1e5podemsertrocadosnográficoinferiorsemalteraraestrutura.Assim,vocêsópodeadivinharcomexatidão50/50,queéonovonó. Este gráfico tem simetria em duas dimensões e pode ser espelhado sem alterar a estrutura. Isso significa que você pode trocar vários nós sem alterar a estrutura. Este último gráfico é o único para o qual você pode identificar o novo nó com 100% de precisão.

Obrigado Kirk Broadhurst, por apontar isso.

    
por Buttons840 12.04.2012 / 06:11
fonte

1 resposta

8

Como outros salientaram, um site como cstheory pode ser mais útil. Pelo que eu entendo do seu problema, isso soa exatamente como o problema do isomorfismo do subgrafo :

Given two graphs G and H find a subgraph of H that is isomorphic to G.

O que você tentou expressar com "correspondência" 0 e 1, e assim por diante, é chamado de isomorfismo em uma configuração de teoria de gráfico. Este é o conceito matemático típico de isomorfismos e o isomorfismo geral de grafos é um problema interessante, para o qual ainda não está claro se é NP-completo.

A boa notícia é que esse problema é bem conhecido, bem pesquisado e existe um algoritmo recursivo que o resolve (o artigo está vinculado ao artigo wp).

A má notícia é que o algoritmo é exponencial (exceto em alguns casos especiais, que parecem não se aplicar ao seu problema) e, na verdade, o próprio problema é NP-completo. Sim, por mais lamentável que pareça, para o problema do isomorfismo gráfico não se sabe se é NP-completo, mas o problema do isomorfismo sub -graph definitivamente é NP-completo.

    
por 12.04.2012 / 10:07
fonte

Tags