In einem der Projekte, an denen ich gearbeitet habe, ist das Thema Isomorphismus gegen Monomorphismus kam .
Ein kleiner Hintergrund: Ich bin kein Experte für Graphentheorie und habe keine formale Ausbildung darin. Aber dieses Thema ist in der Chemie sehr wichtig, wo Chemiker erwarten, dass eine bestimmte Art von Subgraph-Matching in den von ihnen verwendeten Struktursuchsystemen stattfindet.
Wenn ein Zielgraph A n Knoten und m Kanten hat, würde ein Chemiker Untergraphenübereinstimmungen akzeptieren, in denen ein Abfragegraph B n Knoten und m-1 Kanten hat. Die einzige Anforderung wäre, dass jede Kante in B in A vorhanden sein sollte. Zum Beispiel sollte eine lineare Kette von 6 Knoten einem Zyklus von 6 Knoten entsprechen.
Ist diese Art von passendem Isomorphismus oder Monomorphismus? Vielleicht etwas ganz anderes?
Seien G1, G2 Graphen, die aus Mengen von Ecken und Kanten V1, V2 bzw. E1, E2 bestehen.
G2 ist zu einem Untergraphen von G1 isomorph, wenn es eine Eins-Eins-Abbildung zwischen jedem Eckpunkt von V2 und einem Eckpunkt in V1 und zwischen jeder Kante in E2 und einer Kante in E1 gibt. Um also isomorph zu sein, müssen Sie eine exakte Übereinstimmung haben, auch wenn der Graph mehr als eine Kante zwischen Knoten enthält.
G2 ist monomorph , wenn es eine solche Zuordnung zwischen den Scheitelpunkten gibt, und es existiert eine Kante zwischen allen Scheitelpunkten in V2, für die es in V1 eine entsprechende Kante gibt. Aber solange mindestens eine Kante existiert, reicht das.
Hier ist eine schöne Paketbeschreibung von comp.lang.python .
Monomorphismus.
Ein Monomorphismus von einem Graphen ("B") zu einem anderen Graphen ("A") ist äquivalent zu einem Isomorphismus von B zu einem Subgraphen von A.
Das Beispiel sagt, dass jeder n Vertex-Pfad ("Kette") monomorph zu einem n Vertex-Zyklus ist. Es wäre auch monomorph zu einem n + 1 Scheitelzyklus oder n + k für jedes k.
Ein ungerichteter Graph-Homomorphismus h: H - & gt; Man sagt, dass G ein Monomorphismus ist, wenn h an Vertices eine injektive Funktion ist. Ein Graph-Homomorphismus h bildet natürlich Kanten auf Kanten ab, aber es gibt keine Anforderung, dass eine Kante h (v0) -h (v1) in H reflektiert wird.
Der Fall von gerichteten Graphen ist ähnlich.
Es gibt hier eine Diskrepanz zwischen den Math- und CS-Termen. Aus Mathe erhalten Sie zwei Begriffe:
Untergraphen Isomorphie: Seien H = (VH, EH) und G = (V, E) Graphen. f: VH → V ist ein Untergraphen-Isomorphismus if (u, v) ∈ EH, dann (f (u), f (v)) E. H ist isomorph zu einem Teilgraphen von G
induzierter Subgraphisomorphismus: Seien H = (VH, EH) und G = (V, E) Graphen. f: VH → V ist ein induzierter Subgraph-Isomorphismus if (u, v) ∈ EH, dann (f (u), f (v)) E. Und wenn (u, v) nicht und Element von EH ist, dann ( f (u), f (v)) ist kein Element von E. H ist Isomorphim zu einem induzierten Teilgraphen von G
Definitionen von Ссылка . Sie entsprechen dem, was ich in "Ein erster Kurs in der Graphentheorie" gefunden habe.
Beachten Sie, dass es sich bei beiden um injektive Homomorphismen zwischen Graphen, einem Graph-Monomorphismus, handelt.
Wechsel zu CS und speziell das Subgraph-Isomorphie-Problem. Nach meinem besten Verständnis bestimmt ein Subgraph-Isomorphie-Algorithmus, ob eine Funktion existiert, die (2) von oben erfüllt.
Graph-Monomorphie passt zu (1).
Die CS-Definitionen stammen aus dem VF2-Algorithmus, ich weiß nicht, wie verbreitet diese Verwendung ist. Bei der Suche nach dem richtigen Algorithmus für ein Projekt scheint es immer noch Unklarheiten zu geben und nicht alle Projekte verwenden die gleichen Definitionen.
Nehmen Sie diese Antwort mit einem Körnchen Salz Ссылка listet Monomorphismus getrennt von Graph-Subgraph-Isomorphie in der Einleitung auf, aber in Abschnitt 2 definiert Graph-Subgraph-Isomorphie als konzeptionell identisch mit (1), was anzeigt, dass mir etwas fehlt.
Tags und Links subgraph isomorphism monomorphism