Quelle est la différence entre l'isomorphisme de sous-graphe et le monomorphisme de sous-graphe?

Question

Dans l'un des projets sur lesquels j'ai travaillé, le sujet de l'isomorphisme et le monomorphisme sont apparus .

Un peu d’arrière-plan: je ne suis pas un expert en théorie des graphes et n’ai aucune formation formelle dans ce domaine. Mais ce sujet est très important en chimie, où les chimistes s’attendent à ce qu’un type particulier de correspondance de sous-graphes ait lieu dans les systèmes de recherche de structure qu’ils utilisent.

Si un graphe cible A a n nœuds et m arêtes, un chimiste acceptera les correspondances de sous-graphe dans lesquelles un graphe de requête B aura n nœuds et m-1 arêtes. La seule condition requise serait que chaque arête de B soit présente dans A. Par exemple, une chaîne linéaire de 6 nœuds doit correspondre à un cycle de 6 nœuds.

Ce type d’isomorphisme ou de monomorphisme correspond-il? Peut-être quelque chose d'autre tout à fait?

Answer 1

Soit G1, G2 des graphes composés d’ensembles de sommets et d’arêtes V1, V2 et E1, E2 respectivement.

G2 est isomorphe à un sous-graphe de G1 ssi il existe une correspondance one-one entre chaque sommet de V2 et un sommet de V1, et entre chaque arête de E2 et une arête de E1. Donc, pour être isomorphe, vous devez avoir une correspondance exacte, y compris si le graphique inclut plusieurs arêtes entre les nœuds.

G2 est monomorphe si et seulement si un tel mappage existe entre les sommets et qu'il existe un bord entre tous les sommets de V2 pour lequel il existe un bord correspondant dans V1. Mais tant qu’il existe au moins un bord, c’est suffisant.

Voici une belle description de package tirée de comp.lang.python .

Answer 2

Monomorphisme.

Un monomorphisme d’un graphe ("B") à un autre graphe ("A") équivaut à un isomorphisme de B en un sous-graphe de A.

L'exemple dit que tout chemin de sommet de n sommet ("chaîne") est monomorphe à un cycle de sommet de n sommet. Il serait également monomorphe à un cycle de sommet n + 1, ou n + k pour tout k.

Answer 3

Homomorphisme de graphe non dirigé h: H - > G est dit être un monomorphisme lorsque h sur les sommets est une fonction injective. Comme homomorphisme de graphe h, bien sûr, mappe les arêtes sur les arêtes, mais il n’est pas nécessaire qu’une arête h (v0) -h (v1) soit reflétée dans H.

Le cas des graphes dirigés est similaire.

Answer 4

Il existe une différence entre les termes mathématiques et CS. En maths, vous obtenez deux termes:

1. isomorphisme de sous-graphe: Soit H = (VH, EH) et G = (V, E) des graphes. f: VH & # 8594; V est un isomorphisme de sous-graphe si (u, v) & # 8712; EH, alors (f (u), f (v)) & # 8712; E. H est isomorphe à un sous-graphe de G

2. Isomorphisme de sous-graphe induit: Soit H = (VH, EH) et G = (V, E) des graphes. f: VH & # 8594; V est un isomorphisme de sous-graphe induit si (u, v) & # 8712; EH, alors (f (u), f (v)) & # 8712; E. Et si (u, v) n’est pas un élément de EH, alors (f (u), f (v)) n’est pas un élément de E. H est isomorphim à un sous-graphe induit de G

Définitions de http://theory.stanford.edu/~virgi/cs267/ lecture1.pdf . Ils sont équivalents à ce que j’ai trouvé dans "Un premier cours en théorie des graphes".

Notez que ces deux formes sont des homomorphismes injectifs entre graphes ou monomorphismes de graphes.

Passage à CS et plus précisément au problème d’isomorphisme de sous-graphes. Autant que je sache, un algorithme d'isomorphisme de sous-graphes détermine s'il existe une fonction qui satisfait (2) d'en haut.

Représente le monomorphisme (1).

Les définitions CS proviennent de l’algorithme VF2, je ne sais pas dans quelle mesure cet usage est répandu. Lors de la recherche du bon algorithme pour un projet, il semble qu'il reste une ambiguïté et que tous les projets n'utilisent pas les mêmes définitions.

Prenez cette réponse avec un grain de sel http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.10.10.5342&rep=rep1&type=pdf répertorie le monomorphisme comme étant distinct de l'isomorphisme graphe-sous-graphe dans l'introduction, mais dans la section 2, l'isomorphisme graphe-sous-graphe est conceptuellement identique à (1), ce qui indique qu'il me manque quelque chose.