0 Daumen
356 Aufrufe

Ein Graph G1 = (V1,E1) ist isomorph zu einem anderen Graphen G2 = (V2,E2), wenn es eine
bijektion f : V1 → V2 gibt, sodass {u, v} ∈ E1 genau dann, wenn {f (u), f (v)} ∈ E2 ist.

Prüfen Sie welche Paare der unten an gegebene Graphen isomorph sind.



Bild_2024-02-10_175929373.png

Avatar von

1 Antwort

0 Daumen

Der Sinn solcher Aufgaben ist, den Isomorphie-Begriff zu verstehen. Das passiert aber nicht beim Lesen von Lösungen.

Es gibt auch keinen vernünftigen Algorithmus dafür, aber natürlich - Du hast hoffentlich in die Unterlagen geschaut - ein paar Anhaltspunkte.

Z.B. müssen die Knoten a und f(a) denselben Grad haben (hier ist f der Isomorphismus). Damit kann man schonmal einen drei Graphen aus dem Rennen schicken.

Bei den verbleibenden zwei denke daran, dass "isomorph" einfach "strukturgleich" heißt, d.h. durch gewisse Verformungen geht der eine Grad in den anderen über (wenn sie isomorph sind).

Fang also mal an. Wenn ein Versuch nichts bringt, heißt das nichts. Weitermachen. Das gehört dazu,

Avatar von 10 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community