VF2 Algorithmus Schritte mit Beispiel

Ich werde versuchen, Ihnen meine frühere Antwort auf diese Frage kurz zu erklären:

Jedes Arbeitsbeispiel des VF2-Algorithmus?

Ich werde das gleiche Beispiel wie in meiner vorherigen Antwort verwenden:

Die 2 obigen Graphen sind V und V '(V' ist nicht in der Zeichnung, aber es ist die rechte)

Der VF2-Algorithmus ist in der Grafik beschrieben.

Schritt für Schritt

Ich möchte wissen, ob V und V 'isomorph sind.

Ich werde die folgenden Notationen verwenden: XV ist der Knoten X in V

Im VF2-Algorithmus werde ich versuchen, jeden Knoten in V mit einem Knoten in V 'abzugleichen.

Schritt 1:

Ich passe leeres V mit leerem V 'an: es funktioniert immer

Schritt 2: Ich kann 1V mit 1V ', 2V' oder 3V '

Ich passe 1V mit 1V ': es funktioniert immer

Schritt 3:

Ich kann 2V mit 2V 'oder 3V'

Ich passe 2V mit 2V 'an: es funktioniert, weil {1V 2V} und {1V' 2V} isomorph sind

Schritt 4:

Ich versuche 3V mit einem Knoten in V 'zu verbinden: Ich kann nicht! {es wäre möglich, wenn sie eine Kante zwischen Knoten 3 und 2 in V 'und keine Kante zwischen 3 und 1 wären)

Also gehe ich zurück zu Schritt 2

Schritt 5:

Ich passe 2V mit 3V '

Schritt 6:

wie Schritt 4

Ich gehe zurück zu Schritt 2. Es gibt keine Lösung in Schritt 2, ich gehe zurück zu Schritt 1

Schritt 7:

Ich passe 1V mit 2V '

Schritt 8:

Ich passe 2V mit 1V '

Schritt 9:

Ich passe 3V mit 3V '

es funktioniert Ich habe {1V 2V 3V} mit {2V '1V' 3V '}

Die Graphen sind isomorph.

Wenn ich die ganze Lösung teste und es nie funktioniert, wäre der Graph nicht isomorph.

Hoffe, das hilft

Über Sie sind Frage auf "übereinstimmend", sehen Sie sich den Wikipedia-Artikel auf Graph Isomorphis:

Ссылка

Dies ist ein gutes Beispiel für eine Funktion f, die mit Graphen G und H übereinstimmt:

Ich hoffe, Sie können diesen Algorithmus mit dieser Illustration besser verstehen.