Einstieg in das Thema
Was brauchst du als Basiswissen?
Du brauchst kein Basiswissen.
Worum geht es?
Graphen bilden Zusammenhängen zwischen
Objekten auf eine ganz einfache Art ab. Sie konzentrieren
sich darauf, welche Objekte mit welchen wie
verbunden sind.
So sind Städte durch Wege miteinander
verbunden, Strommasten durch Leitungen,
Bauelemente durch Kabel usw.
Zu diesen Graphen gibt es Algorithmen, um
die Verbindungen zu analysieren und auch zu verbessern.
Was ist das Ziel?
Du weißt am Ende, was Graphen sind und kannst die
ersten Graphen zu Sachverhalten zeichnen.
Erarbeitung
Aufgaben
Aufgabe 1
Zeichne vier Knoten. Knoten 1 soll mit einem, Knoten zwei mit zwei Knoten verbunden sein. Mit wie vielen Knoten kann Knoten drei verbunden sein?
Aufgabe 2
Zeichne fünf Knoten, die ungefähr gleichverteilt auf einem (unsichtbaren) Kreis liegen. Verbinde nun jeden Knoten mit den zwei anderen Knoten, die am weitesten entfernt sind. Welche Figur entsteht?
Aufgabe 3
Wie viele Kanten sind entstanden?
Aufgabe 4
Eine Person möchte von einem beliebigen Knoten zu einem anderen Knoten in diesem Graphen. Was ist der längste Weg?
In einer Gruppe von 6 Personen kennt jede Person einige der anderen.
Anna kennt Ben und Clara, Ben kennt David und Anna, Clara kennt Anna,
David kennt Ben, Eva kennt niemanden, Felix kennt Clara.
Aufgabe 5
Stelle die Beziehungen mit einem Graphen dar. Verbinde Personen mit einer Kante, wenn sie sich kennen.
Aufgabe 6
Wer kennt direkt die meisten Personen? Finde ein Beispiel, wo eine Person eine andere nur über eine weitere Person kennt (bzw. erreichen kann).
Aufgabe 7
Die siehst im Bild oben eine Landkarte. Bitte erstelle ein Abbild. Dörfer sind Knoten, Straßen sind Kanten.
Aufgabe 8
Man bezeichnet Knoten gern mit Großbuchstaben, um z.B. Wege leicht angeben zu können. Vergib Buchstabennamen.
Aufgabe 9
Gib einen Weg an, um vom Dorf ganz links zum Dorf ganz rechts zu kommen.
Schleifen sind Kanten, die zu ihrem Knoten zurück gehen.
Wir brauchen Schleifen eher selten, wollen sie aber nicht
ignorieren.
Aufgabe 10
Nehmen wir an, Knoten sind Dörfer und Kanten sind Straßen. Was ist dann eine Schleife?
Aufgabe 11
Wenn ein Knoten nur eine Schleife hat, wie hoch ist sein Grad?
Gerichtete Graphen
Bis jetzt waren die Kanten immer nur eine Linie zwischen
zwei Knoten. Der Weg von Knoten A zu B war gleichwertig zum s
Weg von B nach A. Nun bekommt die Kante eine Richtung
und wird einfach als Pfeil gezeichnet.
Aufgaben
Aufgabe 12
Was kann eine solche gerichtete Kante in einer Straßenkarte sein?
Aufgabe 13
Ist eine gerichtete Kante in einem Stromnetz sinnvoll?
Aufgabe 14
Welche Aussage ist richtig? "Ein gerichteter Graph hat genau eine gerichtete Kante", "Ein gerichteter Graph hat mindestens eine gerichtete Kante" oder "Ein gerichteter Graph hat nur gerichtete Kanten"?
Aufgabe 15
Würde eine Kante mit zwei Pfeilspitzen (also einer an jedem Ende) Sinn ergeben?
Bei Soziogrammen sind Beziehungen gerichtet. Wenn Person A Person B kennt,
dann kennt (normalerweise) B auch A. Aber wenn A die Person B mag,
heißt das nocht nicht, dass B auch A mag.
In einer Schulklasse gibt es sieben Schülerinnen und Schüler:
A, B, C, D, E, F und G.
Hier sind die Beziehungen zwischen den Schülern:
A kann gut mit B und C zusammenarbeiten.
B arbeitet gerne mit D und E.
C kommt gut mit F und G klar.
D hat bereits erfolgreich mit E und F zusammengearbeitet.
E hat keine Probleme mit der Zusammenarbeit mit F.
F und G können nicht miteinander arbeiten.
Aufgabe 16
Zeichne den Graphen.
Aufgabe 17
Wie viele Paare gibt es, die gut miteinander arbeiten können?
Aufgabe 18
Gibt es Dreiergruppen, die gut zusammenarbeiten können.
Aufgabe 19
Gib eine Gruppe von mindestens drei Personen an, wo die Zusammenarbeit sicher nicht klappen wird.
Zusammenfassung
Was muss man wissen/können?
Du
- weißt, dass man gewisse Sachverhalte auf Graphen reduzieren kann,
- erkennst Graphen, wenn du sie siehst und
- kannst selbst Graphen zu (noch) einfachen Sachverhalten erstellen.
Was können anschließende Themen sein?
Wir müssen noch etwas Ordnung in das System bringen.
Du wirst also ein paar neue Fachbegriffe kennenlernen.
