Der Isomorphismusgraph kann als ein Graph beschrieben werden, in dem ein einzelner Graph mehr als eine Form haben kann. Das bedeutet, dass zwei verschiedene Graphen die gleiche Anzahl an Kanten, Eckpunkten und die gleiche Kantenkonnektivität haben können. Diese Arten von Graphen werden als Isomorphismusgraphen bezeichnet. Das Beispiel eines Isomorphismusgraphen wird wie folgt beschrieben:
Die obige Grafik enthält die folgenden Dinge:
- Derselbe Graph wird in mehr als einer Form dargestellt.
- Daher können wir sagen, dass diese Graphen Isomorphismusgraphen sind.
Bedingungen für Graphisomorphismus
Zwei beliebige Graphen werden als Isomorphismus bezeichnet, wenn sie die folgenden vier Bedingungen erfüllen:
- In den gegebenen Diagrammen wird es eine gleiche Anzahl von Eckpunkten geben.
- In den gegebenen Diagrammen wird es eine gleiche Anzahl von Kanten geben.
- In den gegebenen Diagrammen wird es eine gleiche Menge an Gradfolgen geben.
- Wenn der erste Graph mit Hilfe der Eckpunkte {v1, v2, v3, …. einen Kreis der Länge k bildet. vk}, dann muss ein anderer Graph mit Hilfe der Knoten {v1, v2, v3, … ebenfalls denselben Kreis der gleichen Länge k bilden. vk}.
Hinweis: Die Gradfolge eines Diagramms kann als Gradfolge aller Eckpunkte in aufsteigender Reihenfolge beschrieben werden.
Wichtige Punkte
- Damit zwei beliebige Graphen ein Isomorphismus sind, sind die notwendigen Bedingungen die oben definierten vier Bedingungen.
- Es ist nicht notwendig, dass die oben definierten Bedingungen ausreichen, um zu zeigen, dass die gegebenen Graphen isomorph sind.
- Auch wenn zwei Graphen die oben definierten vier Bedingungen erfüllen, ist es nicht notwendig, dass die Graphen sicher isomorph sind.
- Wenn der Graph keine Bedingungen erfüllt, können wir sagen, dass es sich bei den Graphen sicherlich nicht um einen Isomorphismus handelt.
Ausreichende Bedingungen für den Graphisomorphismus
Wenn wir beweisen wollen, dass zwei beliebige Graphen isomorph sind, gibt es einige hinreichende Bedingungen, die uns garantieren, dass die beiden Graphen sicher isomorph sind. Wenn die beiden Diagramme alle oben genannten vier Bedingungen erfolgreich gelöscht haben, überprüfen wir erst dann diese Diagramme auf ausreichende Bedingungen, die wie folgt beschrieben werden:
- Wenn die Komplementgraphen beider Graphen Isomorphie sind, dann sind diese Graphen mit Sicherheit ein Isomorphismus.
- Wenn die benachbarten Matrizen beider Graphen gleich sind, handelt es sich bei diesen Graphen um einen Isomorphismus.
- Wenn die entsprechenden Diagramme zweier Diagramme durch Löschen einiger Scheitelpunkte eines Diagramms erhalten werden und ihre entsprechenden Bilder in anderen Bildern Isomorphien sind, handelt es sich bei diesen Diagrammen nur dann nicht um Isomorphien.
Wenn zwei Graphen eine der oben genannten Bedingungen erfüllen, können wir sagen, dass es sich bei diesen Graphen sicherlich um Isomorphie handelt.
Beispiele für Graphisomorphismus
Es gibt viele Beispiele für Graphisomorphismus, die wie folgt beschrieben werden:
Beispiel 1:
In diesem Beispiel haben wir gezeigt, ob die folgenden Diagramme isomorph sind.
Lösung: Dazu prüfen wir alle vier Bedingungen des Graphisomorphismus, die wie folgt beschrieben werden:
Bedingung 1:
- In Diagramm 1 gibt es insgesamt 4 Eckpunkte, d. h. G1 = 4.
- In Grafik 2 gibt es insgesamt 4 Eckpunkte, d. h. G2 = 4.
Hier,
In beiden Graphen G1 und G2 gibt es die gleiche Anzahl von Eckpunkten. Diese Diagramme erfüllen also Bedingung 1. Jetzt prüfen wir die zweite Bedingung.
Bedingung 2:
- In Diagramm 1 gibt es insgesamt 5 Kanten, d. h. G1 = 5.
- In Grafik 2 gibt es insgesamt 6 Kanten, d. h. G2 = 6.
Hier,
Es gibt nicht die gleiche Anzahl an Kanten in den beiden Graphen G1 und G2. Diese Diagramme erfüllen also nicht Bedingung 2. Jetzt können wir nicht alle verbleibenden Bedingungen überprüfen.
Da diese Graphen Bedingung 2 verletzen. Diese Graphen sind also kein Isomorphismus.
∴ Graph G1 und Graph G2 sind keine Isomorphismusgraphen.
Beispiel 2:
In diesem Beispiel haben wir gezeigt, ob die folgenden Diagramme isomorph sind.
Lösung: Dazu prüfen wir alle vier Bedingungen des Graphisomorphismus, die wie folgt beschrieben werden:
Bedingung 1:
Rückgabetyp in Java
- In Diagramm 1 gibt es insgesamt 4 Eckpunkte, d. h. G1 = 4.
- In Grafik 2 gibt es insgesamt 4 Eckpunkte, d. h. G2 = 4.
- In Grafik 3 gibt es insgesamt 4 Eckpunkte, d. h. G3 = 4.
Hier,
In allen Graphen G1, G2 und G3 gibt es die gleiche Anzahl von Eckpunkten. Diese Diagramme erfüllen also Bedingung 1. Jetzt prüfen wir die zweite Bedingung.
Bedingung 2:
- In Diagramm 1 gibt es insgesamt 5 Kanten, d. h. G1 = 5.
- In Diagramm 2 gibt es insgesamt 5 Kanten, d. h. G2 = 5.
- In Grafik 3 gibt es insgesamt 4 Kanten, d. h. G2 = 4.
Hier,
- In beiden Graphen G1 und G2 gibt es gleich viele Kanten. Diese Diagramme erfüllen also Bedingung 2.
- Allerdings gibt es in den Graphen (G1, G2) und G3 nicht die gleiche Anzahl an Kanten. Die Graphen (G1, G2) und G3 erfüllen also nicht die Bedingung 2.
Da die Graphen (G1, G2) und G3 die Bedingung 2 verletzen, können wir sagen, dass diese Graphen kein Isomorphismus sind.
∴ Graph G3 ist weder Isomorphismus mit Graph G1 noch mit Graph G2.
Da die Graphen G1 und G2 Bedingung 2 erfüllen, können wir sagen, dass diese Graphen ein Isomorphismus sein können.
∴ Die Graphen G1 und G2 können ein Isomorphismus sein.
Jetzt prüfen wir die dritte Bedingung für die Graphen G1 und G2.
So konvertieren Sie einen String in einen Integer-Java
Bedingung 3:
- Im Graphen 1 ist der Grad der Folge s {2, 2, 3, 3}, d. h. G1 = {2, 2, 3, 3}.
- Im Graphen 2 ist der Grad der Folge s {2, 2, 3, 3}, d. h. G2 = {2, 2, 3, 3}.
Hier
In beiden Graphen G1 und G2 gibt es gleich viele Gradfolgen. Diese Diagramme erfüllen also Bedingung 3. Jetzt prüfen wir die vierte Bedingung.
Bedingung 4:
Graph G1 bildet mit Hilfe der Eckpunkte {2, 3, 3} einen Kreis der Länge 3.
Auch Graph G2 bildet mit Hilfe der Eckpunkte {2, 3, 3} einen Kreis der Länge 3.
Hier,
Es zeigt, dass beide Graphen denselben Zyklus enthalten, da beide Graphen G1 und G2 mit Hilfe der Eckpunkte {2, 3, 3} einen Zyklus der Länge 3 bilden. Diese Diagramme erfüllen also Bedingung 4.
Daher,
- Die Graphen G1 und G2 erfüllen alle oben genannten vier notwendigen Bedingungen.
- G1 und G2 können also ein Isomorphismus sein.
Nun prüfen wir ausreichende Bedingungen, um zu zeigen, dass die Graphen G1 und G2 ein Isomorphismus sind.
Prüfung ausreichender Bedingungen
Wie wir gelernt haben, sind die beiden Graphen mit Sicherheit ein Isomorphismus, wenn die Komplementgraphen beider Graphen Isomorphie sind.
Wir zeichnen also die Komplementgraphen von G1 und G2, die wie folgt beschrieben werden:
In den obigen Komplementgraphen von G1 und G2 können wir sehen, dass beide Graphen Isomorphie sind.
∴ Die Graphen G1 und G2 sind Isomorphie.
Beispiel 3:
In diesem Beispiel haben wir gezeigt, ob die folgenden Diagramme isomorph sind.
Lösung: Dazu prüfen wir alle vier Bedingungen des Graphisomorphismus, die wie folgt beschrieben werden:
Bedingung 1:
Datei in Java öffnen
- In Diagramm 1 gibt es insgesamt 8 Eckpunkte, d. h. G1 = 8.
- In Grafik 2 gibt es insgesamt 8 Eckpunkte, d. h. G2 = 8.
Hier,
In beiden Graphen G1 und G2 gibt es die gleiche Anzahl von Eckpunkten. Diese Diagramme erfüllen also Bedingung 1. Jetzt prüfen wir die zweite Bedingung.
Bedingung 2:
- In Diagramm 1 beträgt die Gesamtzahl der Kanten 10, d. h. G1 = 10.
- In Grafik 2 beträgt die Gesamtzahl der Kanten 10, d. h. G2 = 10.
Hier,
In beiden Graphen G1 und G2 gibt es gleich viele Kanten. Diese Diagramme erfüllen also Bedingung 2. Jetzt prüfen wir die dritte Bedingung.
Bedingung 3:
- Im Diagramm 1 ist der Grad der Folge s {2, 2, 2, 2, 3, 3, 3, 3}, d. h. G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- Im Diagramm 2 ist der Grad der Folge s {2, 2, 2, 2, 3, 3, 3, 3}, d. h. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Hier
In beiden Graphen G1 und G2 gibt es gleich viele Gradfolgen. Diese Diagramme erfüllen also Bedingung 3. Jetzt prüfen wir die vierte Bedingung.
Bedingung 4:
- Graph G1 bildet mit Hilfe von Eckpunkten 3. Grades einen Kreis der Länge 4.
- Graph G2 bildet mithilfe von Eckpunkten keinen Kreis der Länge 4, da die Eckpunkte nicht benachbart sind.
Hier,
Die beiden Graphen G1 und G2 bilden nicht denselben Zyklus mit derselben Länge. Diese Diagramme verstoßen also gegen Bedingung 4.
Da die Graphen G1 und G2 Bedingung 4 verletzen. Aufgrund der Verletzung von Bedingung 4 sind diese Graphen also kein Isomorphismus.
∴ Die Graphen G1 und G2 sind kein Isomorphismus.