Qual é a diferença entre subgráfico Isomorfismo e subgráfico monomorfismo?

Question

Em um dos projetos em que já trabalhei, objecto de isomorfismo contra monomorphism surgiu .

Um pouco de fundo: Não sou especialista em teoria dos grafos e não têm nenhum treinamento formal na mesma. Mas este tema é muito importante em química, onde os químicos esperar um determinado tipo de correspondência subgráfico a ter lugar nos sistemas de busca da estrutura que eles usam.

Se um gráfico alvo A tem n nodos em arestas, em seguida, um químico iria aceitar partidas subgráfico em que um gráfico de consulta B tinha n nós e m-1 arestas. O único requisito seria que cada margem em B devem estar presentes no A. Por exemplo, uma cadeia linear de 6 nodos deve corresponder a um ciclo de 6 nodos.

É este o tipo de correspondência de isomorfismo ou monomorphism? Talvez algo completamente diferente?

Answer 1

Let G1, G2 ser gráficos compostos por conjuntos de arestas e vértices V1, V2 e E1, E2, respectivamente.

G2 é isomorfa a um subgráfico de G1 sse existe um mapeamento um-um entre cada vértice de V2 e um vértice em V1, e entre cada bordo e em E2 alguma vantagem em E1. Assim, para ser isomorphic, você precisa ter uma correspondência exata, incluindo se o gráfico inclui mais de uma aresta entre os nós.

G2 é monomórfica sse há um tal mapeamento entre os vértices, e existe uma aresta entre todos os vértices no V2 para o qual existe um bordo correspondente em V1. Mas enquanto existir pelo menos uma borda, isso é suficiente.

Aqui está uma descrição do pacote agradável de comp.lang.python .

Answer 2

monomorfismo.

Um monomorfismo a partir de um gráfico ( "B") para um outro gráfico ( "A") é equivalente a um isomorfismo de B para um subgráfico de A.

O exemplo é dizer que qualquer caminho n vértice ( "cadeia") é monomórfico de um ciclo n vértice. Seria também monomórfica para um ciclo n + 1 vértice, ou n + k para qualquer k.

Answer 3

Um não-dirigido gráfico homomorphism h: H -> G é dito ser um monomorfismo quando h em vértices é uma função injetivo. Como um gráfico homomorphism h de curso mapeia bordas a bordas mas não há nenhuma exigência de que uma borda h (v0) -h (v1) reflecte-se em H.

O caso de grafos dirigidos é semelhante.

Answer 4

Há uma discrepância entre matemática e CS termos aqui. De matemática você tem dois termos:

1. isomorfismo subgráfico: Seja H = (VH, EH) e L = (V, E) ser gráficos. f: VH ? V é um isomorfismo subgráfico se (u, v) ? EH, em seguida, (f (u), F (v)) ? E. H é isomorfa a um subgráfico de G

2. induzida isomorfismo subgráfico: Seja H = (VH, EH) e L = (V, E) ser gráficos. f: VH ? V é um isomorfismo subgráfico induzida se (u, v) ? EH, em seguida, (f (u), F (v)) ? E. E se (u, v) e não elemento de EH é, em seguida, ( f (u), F (v)), não é um elemento de E. H é isomorphim para um subgráfico induzida de G

Definições de http://theory.stanford.edu/~virgi/cs267/ lecture1.pdf. Eles são equivalentes ao que eu encontrei em "Um primeiro curso em Teoria dos Grafos."

Note-se que ambos são homomorphisms injetivas entre gráficos aka um monomorphism gráfico.

Mover-se para CS e, especificamente, o problema subgráfico isomorfismo. Para o melhor da minha compreensão de um algoritmo subgráfico isomorfismo determina se existe uma função que satisfaz (2) de cima.

Gráfico partidas monomorfismo (1).

As definições CS são do algoritmo VF2, eu não sei como generalizada de que o uso é. Embora a pesquisa para o algoritmo correto para um projeto que parece que ainda há alguma ambiguidade e nem todos os projetos usam as mesmas definições.

Tome esta resposta com um grão de sal http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf listas monomorphism como separado do isomorfismo de grafos-subgrafo na introdução, mas na seção 2 define gráfico-subgrafo isomorfismo como conceitualmente idêntico ao (1) que indica que eu estou faltando alguma coisa.