0 Daumen
44 Aufrufe

Hallo liebe Community,

ich fehlt glaube ich leider die nötige Kreativität für die folgende Aufgabe:

Zeigen Sie: Es gibt zwei untereinander nicht isomorphe und zu T nicht isomorphe Graphen G1 und G2 mit der Valenzsequenz (3, 2, 2, 1, 1, 1). Beweisen Sie die paarweise Nichtisomorphie der drei Graphen G1, G2 und T. Hinweis: Einer der beiden Graphen G1 und G2 ist ein Baum.

Graph T.png

Meine Gedanken: T ist ja auch ein Baum, aber alle anderen Bäume die ich mit der Valenzsequenz konstruiere, sind isomorph zu T. Ich hätte noch die Idee einen Graphen mit einem Kreis zu zeichnen, der wäre auf jeden Fall nicht isomorph zu T. Aber wie zeige ich am Ende formal die Nicht Isomorphie, wenn die Valenzsequenzen die gleichen sind?


Vielen lieben Dank vorab!

Avatar vor von

1 Antwort

0 Daumen

MLFoto.jpg

Hallo,

das sind die drei möglichen Graphen (bis auf Isomorphie).

Der rechte Graph ist nicht zusammenhängend, daher nicht isomorph zu einem der anderen.

In diesen Graphen ist jeweils der eine Punkt mit Grad 3 ausgezeichnet / eindeutig. Im linken Graphen hat dieser Punkt 2 Nachbarn mit Grad 2, im mittleren nur einen Nachbar mit Grad 2; daher sind die beiden linken nicht isomorph.

Avatar vor von 14 k

Vielen lieben Dank für deine Hilfe!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community