Qual è la differenza tra l'isomorfismo del sottografo e il monomorfismo del sottografo?

Question

In uno dei progetti a cui ho lavorato, l'argomento di isomorfismo contro monomorfismo è emerso .

Un po 'di storia: non sono un esperto di teoria dei grafi e non ho una formazione formale. Ma questo argomento è molto importante in chimica, dove i chimici si aspettano che un particolare tipo di corrispondenza dei sottografi abbia luogo nei sistemi di ricerca della struttura che usano.

Se un grafico di destinazione A ha n nodi e bordi m, un chimico accetterebbe corrispondenze dei sottografi in cui un grafico di query B aveva n nodi e bordi m-1. L'unico requisito sarebbe che ogni fronte in B fosse presente in A. Ad esempio, una catena lineare di 6 nodi dovrebbe corrispondere a un ciclo di 6 nodi.

È questo tipo di abbinamento isomorfismo o monomorfismo? Forse qualcos'altro del tutto?

Answer 1

Sia G1, G2 grafici di insiemi di vertici e bordi rispettivamente V1, V2 ed E1, E2.

G2 è isomorfo a un sottografo di G1 se esiste una mappatura one-one tra ciascun vertice di V2 e un vertice in V1, e tra ciascun bordo in E2 e un bordo in E1. Quindi, per essere isomorfo, devi avere una corrispondenza esatta, anche se il grafico include più di un bordo tra i nodi.

G2 è monomorfo se esiste una tale mappatura tra vertici e esiste un bordo tra tutti i vertici in V2 per il quale esiste un bordo corrispondente in V1. Ma finché esiste almeno un bordo, è sufficiente.

Ecco una bella descrizione del pacchetto da comp.lang.python .

Answer 2

monomorfismo.

Un monomorfismo da un grafico ("B") a un altro grafico ("A") equivale a un isomorfismo da B a un sottografo di A.

L'esempio sta dicendo che qualsiasi percorso di n vertici ("catena") è monomorfo a un ciclo di n vertici. Sarebbe anche monomorfo per un ciclo di vertici n + 1 o n + k per qualsiasi k.

Answer 3

Un omomorfismo grafico non orientato h: H - > Si dice che G sia un monomorfismo quando h sui vertici è una funzione iniettiva. Come un omomorfismo grafico, ovviamente h mappa i bordi ai bordi ma non è necessario che un bordo h (v0) -h (v1) si rifletta in H.

Il caso dei grafici diretti è simile.

Answer 4

C'è una discrepanza tra i termini matematici e CS qui. Dalla matematica si ottengono due termini:

1. isomorfismo del sottografo: Sia H = (VH, EH) e G = (V, E) grafici. f: VH & # 8594; V è un isomorfismo del sottografo se (u, v) & # 8712; EH, quindi (f (u), f (v)) & # 8712; E. H è isomorfo a un sottografo di G

2. isomorfismo del sottografo indotto: Sia H = (VH, EH) e G = (V, E) grafici. f: VH & # 8594; V è un isomorfismo del sottografo indotto se (u, v) & # 8712; EH, quindi (f (u), f (v)) & # 8712; E. E se (u, v) non è ed elemento di EH, allora (f (u), f (v)) non è un elemento di E. H è isomorfo a un sottografo indotto di G

Definizioni da http://theory.stanford.edu/~virgi/cs267/ lecture1.pdf . Sono equivalenti a quello che ho trovato in "Un primo corso di teoria dei grafi". & Quot;

Si noti che entrambi questi sono omomorfismi iniettivi tra grafici alias monomorfismo grafico.

Passaggio a CS e in particolare al problema dell'isomorfismo del sottografo. Per quanto ne so, un algoritmo di isomorfismo del sottografo determina se esiste una funzione che soddisfa (2) dall'alto.

Grafico delle corrispondenze di monomorfismo (1).

Le definizioni CS provengono dall'algoritmo VF2, non so quanto sia diffuso tale utilizzo. Durante la ricerca dell'algoritmo corretto per un progetto sembra che ci sia ancora qualche ambiguità e non tutti i progetti utilizzano le stesse definizioni.

Prendi questa risposta con un granello di sale http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf elenca il monomorfismo come separato dall'isomorfismo grafico-subgrafo nell'introduzione, ma nella sezione 2 definisce l'isomorfismo grafico-subgrafo concettualmente identico a (1) che indica che mi manca qualcosa.