Graphentheorie (isormoph), Bijektion

Question

Text erkannt:

Bi; hav
2
2
\( l \)
\( v \)

Aufgabe: Überprüfung, ob die Graphen isomorph sind.

Meine Frage:

(1): Müssen die Kanten und Knoten im Rahmen eines Vergleichs IMMER identisch sein? Also wenn der eine z.B. 8 Kanten und der andere nur 7 Kanten hat aber die Graphen sonst quasi "gleich aussehen" - kann ich trotzdem dann eine isomorphie ausschließen?

Vielen Dank und LG!

Answer 1

Also wenn der eine z.B. 8 Kanten und der andere nur 7 Kanten hat

Dann sind die Graphen nicht isomorph.

Müssen die Kanten und Knoten im Rahmen eines Vergleichs IMMER identisch sein?

Nein. Der Graph mit den Knoten a und b kann isomorph zu dem Graphen mit den Knoten c und d sein, obwohl der zweite Graph nicht zu dem ersten Graph identische Knoten hat.

Die Anzahl der Knoten muss aber in beiden Graphen identisch sein und die Anzahl der Kanten muss in beiden Graphen identisch sein.