Testbeispiele

(Last Updated On: 19. Oktober 2012)

zurück zu Allgemeines

Testbeispiele

1 a) Wie ist die Isomorphie zwischen zwei Graphen definiert?

A: Eine bijektive Abbildung von V1 auf V2 heißt Isomorphismus von X1 auf X2, wenn gilt:

[x,y] ⇔ [ρ(x), ρ(y)] ∈ E2

Untersuchen sie folgenden Graphen paarweise auf Isomorphie.

Existiert zwischen zwei Graphen ein Isomorphismus, so geben Sie diesen an, andernfalls formulieren Sie eine Begründung, warum kein Isomorph ismus existiert.

A: Der Knoten 3 weist Grad 5 auf, weshalb der 1. und der zweite bzw. der 1. und der 3. Graph nicht isomorph sind.

Der 3. und 4. Graph kann auch nicht isomorph sein da die Anzahl der Knoten gleichen Grades unterschiedlich ist.

2) Gegeben sind die beiden Graphen X und Y:

X: V(X) = {1,2,3,4,5,6,7,8}          E(X) = {[x,y]| y teilt x}

X: V(Y) = 1,3,4,5}                      E(Y) = {[x,y] y größer x}

a)     Zeichnen sie die beiden Graphen und bilden Sie deren Vereinigung und Durchschnitt.

b)     Das Komplement Zc eines Graphen ist wie folgt definiert:

V(Zc) = V(Z)

E(Zc) = {[x,y] | x ¹ y, [x,y] Î E(Z)}

Stelle das Komplement des Graphen X dar.

 

3) Bestimmen Sie (algorithmisch) alle Blöcke, Artikulationen und Brücken des Graphen X.

Bestimmen Sie den durchmesser der von K(4) aufgespannten Komponente von X und skizzieren Sie außerdem alle Teilgraphen von X – {5,6,7,8,9,10,11,12,13,14}.

nach oben

(431)


History

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert