IMP 8 · Logik und Graphen

Graphen und Bäume

Ein Graph besteht aus Knoten und Kanten. Der Grad eines Knotens gibt an, wie viele Kanten dort enden. Ein Eulerscher Kantenzug läuft durch jede Kante genau einmal. Ein Baum ist ein zusammenhängender Graph ohne Kreise.

So gehst du vor

1Wähle ein Beispiel oder baue selbst: Tippe ins Leere für einen Knoten, ziehe von Knoten zu Knoten für eine Kante.
2Lies rechts ab, was für den Graphen gilt. Die kleine Zahl am Knoten ist sein Grad, Knoten mit ungeradem Grad sind gefärbt.
3Wähle „Nachfahren“ und tippe Knoten für Knoten an, ohne eine Kante doppelt zu nehmen.
4Bearbeite dann die Aufträge.

Königsberg 1736: A Norden, B Insel, C Süden, D Osten. Jede Kante ist eine der sieben Brücken über den Pregel.

Was macht dein Finger?

Beispiel

Das gilt für deinen Graphen

Knoten4

Kanten7

Summe der Grade14

Knoten mit ungeradem Grad4

zusammenhängendja

ohne Kreisenein

Baumnein

4 Knoten haben ungeraden Grad. Jeder Knoten außer Start und Ziel braucht aber gleich viele Wege hinein und hinaus: Es gibt keinen Eulerschen Kantenzug.

Kantenzug

Wähle „Nachfahren“ oder lass dir einen Kantenzug zeigen.

Bäume

Ein Baum mit n Knoten hat genau n − 1 Kanten. Ein Spannbaum verbindet alle Knoten eines Graphen mit so wenigen Kanten wie möglich.

Aufträge

Wähle Königsberg. Notiere die Grade und begründe, warum es keinen Rundgang über alle sieben Brücken gibt. Baue im Modus „Bauen“ eine achte Brücke so ein, dass ein Spaziergang über alle Brücken möglich wird. Wo beginnt und endet er?
Wähle das Haus vom Nikolaus. Fahre es im Modus „Nachfahren“ nach. Bei welchen Knoten kannst du beginnen? Was passiert, wenn du bei C startest?
Kann man einen Draht zu einem Kantenmodell eines Würfels biegen, ohne ein Stück doppelt zu legen? Begründe mit dem Graphen. Wie viele Kanten müsste man mindestens weglassen, damit es geht?
Baue mehrere eigene Graphen. Vergleiche die Summe der Grade mit der Anzahl der Kanten. Formuliere eine Regel und begründe sie. Warum ist die Anzahl der Knoten mit ungeradem Grad immer gerade?
Baue Bäume mit 3, 4, 5 und 6 Knoten. Notiere jeweils die Anzahl der Kanten. Was passiert, wenn du in einem Baum eine Kante ergänzt? Was, wenn du eine entfernst?
Die acht Ecken des Würfels sollen an ein Stromnetz. Jede Kante ist eine mögliche Leitung. Bestimme mit dem Spannbaum, wie viele Leitungen genügen und wie viele du einsparst.