Arbeitsblatt Graphentheorie mit Lösungen

Ein 4-regulärer Graph hat 8 Knoten (jeder Knoten hat den Grad 4). Wie viele Kanten |E| hat er?

Ein Baum hat 25 Kanten. Wie viele Knoten |V| hat er?

Hat der zusammenhängende Graph einen Euler-Kreis, einen Euler-Weg, der kein Kreis ist, oder keines von beiden? Klicke deine Antwort an.

1. 1Euler-Kreis
2. 2Euler-Weg, kein Kreis
3. 3keines von beiden

Ein Baum hat 3 Knoten vom Grad 3, 4 Knoten vom Grad 4, 4 Knoten vom Grad 2, und alle seine anderen Knoten sind Blätter (Grad 1). Wie viele Blätter L hat er?

Der Prim-Algorithmus baut einen minimalen aufspannenden Baum auf, beginnend bei Knoten A. Klicke die Kante an, die er als Kante Nummer 3 hinzufügt.

1. 1Kante AB
2. 2Kante AC
3. 3Kante BC
4. 4Kante BD
5. 5Kante CE
6. 6Kante DE
7. 7Kante BE

Der Kruskal-Algorithmus baut einen minimalen aufspannenden Baum auf. Klicke die Kante an, die er als Kante Nummer 2 hinzufügt; übersprungene Kanten zählen nicht.

1. 1Kante AB
2. 2Kante AC
3. 3Kante BC
4. 4Kante CE
5. 5Kante DE
6. 6Kante DF
7. 7Kante GB
8. 8Kante GC
9. 9Kante GD
10. 10Kante GE