Was ist der Unterschied zwischen Subgraph Isomorphie und Subgraph Monomorphismus?

Question

In einem der Projekte, die ich gearbeitet habe, das Thema Isomorphismus gegen Monomorphie kam.

Ein wenig Hintergrund: Ich bin kein Experte auf Graphentheorie und haben keine formale Ausbildung in ihm. Aber dieses Thema ist sehr wichtig, in der Chemie, in dem Chemiker eine besondere Art von Subgraphen Matching erwarten zu finden in der Struktursuche Systemen, die sie verwenden.

Wenn ein Ziel Graph A n Knoten und m Kanten hat, dann wäre ein Chemiker akzeptieren Subgraphen einstimmt, in dem eine Abfrage Graph B n Knoten und m-1 Kante hatte. Die einzige Voraussetzung wäre, dass jede Kante in B sollte beispielsweise eine lineare Kette von 6 Knoten in A. vorhanden sein sollte, einen Zyklus von sechs Knoten entsprechen.

Ist diese Art Isomorphismus oder Monomorphie passender? Vielleicht ganz etwas anderes?

Answer 1

G1 Lassen, G2 Graphen wird, die aus Sätzen von Knoten und Kanten V1, V2 und E1, E2 ist.

G2 wird ein Subgraphen von G1 isomorph iff zwischen jedem Scheitel V2 und V1 in einem Scheitelpunkt und zwischen jeder Kante in E2 und E1 in irgendeiner Kante eine Eins-Eins-Zuordnung besteht. So werden isomorph, müssen Sie eine genaue Übereinstimmung haben, einschließlich, wenn der Graph mehr als eine Kante zwischen den Knoten.

G2 ist monomorphe iff es ist so eine Zuordnung zwischen Vertices, und es existiert eine Kante zwischen den Eckpunkten in V2 für die es eine entsprechende Kante in V1 ist. Aber solange mindestens eine Kante vorhanden ist, das ist ausreichend.

Hier ist ein schönes Paket Beschreibung von comp.lang.python .

Answer 2

Monomorphismus.

A Monomorphie aus einem Diagramm ( "B") zu einem anderen Graphen ( "A") entspricht einen Isomorphismus von B nach A Subgraph von a.

Das Beispiel ist zu sagen, dass jede n Scheitelstrecke ( „chain“) an einen n Eckpunkt Zyklus monomorphe ist. Es wäre auch monomorphic zu einem n + 1 Vertex Zyklus oder n + k für jeden k sein.

Answer 3

Ein ungerichteter Graph Homomorphismus h: H -> G gesagt wird ein Monomorphismus sein, wenn h auf Vertices eine injektive Funktion ist. Als Graph Homomorphismus h natürlich Karten Kanten Kanten aber es ist nicht erforderlich, dass eine Kante h (v0) -h (v1) in H reflektiert wird.

Der Fall gerichteten Graphen ist ähnlich.

Answer 4

Es gibt eine Diskrepanz zwischen Mathematik und CS Begriffe hier. Von Mathe bekommen Sie zwei Begriffe:

1. Subgraphen Isomorphismus: Sei H = (VH, EH), und G = (V, E) graphische Darstellungen sein. f: VH → V ist ein Subgraph Isomorphismus wenn (u, v) ∈ EH, dann (f (u), f (v)) ∈ E. H ist isomorph zu einem Untergraphen von G

2. Untergraph Isomorphismus: Sei H = (VH, EH), und G = (V, E) graphische Darstellungen sein. f: VH → V ist ein Untergraph Isomorphismus, wenn (u, v) ∈ EH, dann (f (u), f (v)) ∈ E. Und wenn (u, v) und ist nicht Bestandteil EH, dann ist ( f (u), f (v)) ist nicht ein Element der E. H ist isomorphim einer induzierten Teilgraph von G

Definitionen von http://theory.stanford.edu/~virgi/cs267/ lecture1.pdf . Sie entsprechen dem, was ich gefunden "A First Course in Graphentheorie."

Beachten Sie, dass diese beiden sind injektiv Homomorphismen zwischen Graphen aka einem Diagramm Monomorphismus.

Der Umzug in CS und speziell das Subgraphen Isomorphismus Problem. Um das Beste aus meinem Verständnis bestimmt ein Subgraphen Isomorphismus Algorithmus, wenn eine Funktion existiert, erfüllt (2) von oben.

Graph Monomorphie Streichhölzer (1).

Die CS Definitionen sind aus dem VF2 Algorithmus, ich weiß nicht, wie weit verbreitet, dass die Nutzung ist. Während für ein Projekt für den richtigen Algorithmus sucht es wie es scheint, sind immer noch einige Unklarheiten und nicht alle Projekte verwenden die gleichen Definitionen.

Nehmen Sie diese Antwort mit einem Körnchen Salz http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf Listen Monomorphismus von Graph-Subgraphen Isomorphismus in der Einleitung als separate, aber in Abschnitt 2 definiert Graph-Subgraphen Isomorphismus als konzeptionell identisch mit (1), die ich bin etwas fehlt an.