Ungerichteten Grad sowie Ein- und Ausgangsgrad bestimmen
Wege und Kreise anhand vorhandener Kanten prüfen
Kantengewichte eines vorgegebenen Wegs addieren
Verständlich erklärt
Ein Graph beschreibt ausgewählte Objekte als Knoten und ihre Beziehungen als Kanten. Was ein Knoten oder eine Kante bedeutet, legt die Modellbeschreibung fest. In einem Ortsnetz können Knoten Orte und Kanten direkte Verbindungen sein; ein soziales Netz kann Personen und bestätigte Kontakte darstellen. Unsere Aufgaben verwenden einfache Graphen ohne Schleifen von einem Knoten zu sich selbst und ohne parallele Kanten. Ein isolierter Knoten gehört trotzdem zum Graphen, hat aber keine Verbindung zu einem anderen Knoten. Die Lage in der Zeichnung dient der Übersicht und ist ohne ausdrückliche Vereinbarung keine geografische Entfernung.
Eine ungerichtete Kante kann in beide Richtungen durchlaufen werden. Der Grad eines Knotens zählt in unseren schleifenfreien ungerichteten Graphen seine anliegenden Kanten. Eine gerichtete Kante ist ein Pfeil: A nach B erlaubt nicht automatisch B nach A. Der Eingangsgrad zählt ankommende, der Ausgangsgrad ausgehende Pfeile. Eine Zahl an der Kante ist ein Gewicht, etwa eine vereinbarte Fahrzeit in Minuten. Richtung und Gewicht sind unabhängige Eigenschaften: Auch ein ungerichteter Graph kann gewichtet sein. Bei Zeitgewichten ergibt die Summe der benutzten Kantengewichte die modellierte Zeit des Wegs, sofern keine weiteren Wartezeiten angesetzt werden.
Ein Weg folgt vorhandenen Kanten; bei gerichteten Graphen muss jeder Pfeil zur Laufrichtung passen. In diesem Kurs verwenden wir für einen einfachen Weg keine Knoten mehrfach. Ein einfacher Kreis führt zum Ausgangsknoten zurück und wiederholt sonst keinen Knoten; in unseren einfachen ungerichteten Graphen enthält er mindestens drei Knoten. Ob eine solche Folge möglich ist, prüfst du Kante für Kante. Weniger Kanten bedeuten in einem gewichteten Graphen nicht automatisch weniger Gesamtkosten. Für die Aufgaben genügt das Lesen und Vergleichen vorgegebener Wege; ein bestimmtes Such- oder Kürzeste-Wege-Verfahren wird nicht vorausgesetzt.
Graph
Knoten
Kante
gerichtet
ungerichtet
Gewicht
Grad
Eingangsgrad
Ausgangsgrad
Weg
Kreis
Beispiel
Ungerichtet: A--B, B--C, C--A, C--D
Grad(A) = 2; Grad(C) = 3.
A-B-C-D ist ein einfacher Weg.
A-B-C-A ist ein einfacher Kreis.
Gerichtet: A->B (4 min), B->C (7 min)
A->B->C kostet 11 min im Modell.
Aus diesen Pfeilen folgt kein Weg C->A.
Typische Fehler
Eine ungerichtete Kante beim Zählen doppelt zählen
Eingangs- und Ausgangsgrad vertauschen
Einen Pfeil ohne Begründung rückwärts benutzen
Zeichenabstände mit Kantengewichten verwechseln
Eine Rückkehrfolge ohne vorhandene Schlusskante als Kreis bezeichnen
Kurz zusammengefasst
Lies zuerst die Bedeutung der Knoten, Kanten und Gewichte. Prüfe danach Nachbarschaft, Richtung und jeden einzelnen Schritt eines Wegs.
Abi-Bezug
Begründe Ergebnisse mit konkreten Kanten. Nenne bei gerichteten Wegen die Laufrichtung und bei Gewichten die Einheit.
Jetzt selbst ausprobieren
Geschlossene Aufgaben prüfst du automatisch. Offene Antworten kontrollierst du anhand der angegebenen Kriterien und der Musterlösung selbst; eine automatische fachliche Bewertung findet dort nicht statt.
BPE 8J21 Punkteleicht
Objekte und Verbindungen unterscheiden
Noch nicht begonnen
Aufgabenstellung
Das Parkmodell zeigt Orte als Knoten und direkte Fußwege als ungerichtete Kanten. Welche Aussagen beschreibt die Darstellung tatsächlich? Wähle alle richtigen Antworten.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Ordne erst die beiden Begriffe Knoten und Kante der Modellbeschreibung zu.
Ein isolierter Ort verschwindet nicht aus der Knotenmenge. Zähle nur ausdrücklich eingezeichnete Verbindungen.
Lösung anzeigen
A und E bezeichnen Orte und sind Knoten. A–B ist ein eingezeichneter direkter Fußweg. E bleibt trotz fehlender Verbindung ein Knoten. Gewichte sind hier nicht angegeben; Nähe in der Zeichnung ergänzt keine Kante.
BPE 8J21 Punkteleicht
Ungerichtete Kanten zählen
Noch nicht begonnen
Aufgabenstellung
Wie viele ungerichtete Kanten hat das Parkmodell? Zähle jede Verbindung nur einmal, nicht einmal je Laufrichtung. Antworte mit einer ganzen Zahl.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Erstelle eine Liste aller verbundenen Knotenpaare.
A–B und B–A bezeichnen hier dieselbe Kante; der isolierte Knoten E fügt keine hinzu.
Lösung anzeigen
5. Die Kanten sind A–B, A–C, B–C, B–D und C–D. Eine ungerichtete Kante wird trotz beider möglicher Laufrichtungen nur einmal gezählt.
BPE 8J22 Punktemittel
Den Grad einer Brücke bestimmen
Noch nicht begonnen
Aufgabenstellung
Bestimme im ungerichteten Parkmodell den Grad von B. Antworte nur mit der Anzahl der an B liegenden Kanten.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Betrachte nur Verbindungen, deren eines Ende B ist.
Unterscheide direkte Nachbarn von Orten, die erst über mehrere Schritte erreichbar sind.
Lösung anzeigen
3. An B liegen die Kanten zu A, C und D. Dass ein Weg über B hinaus weitergeführt werden kann, erhöht seinen Grad nicht.
BPE 8J22 Punktemittel
Ein isolierter Ort bleibt ein Knoten
Noch nicht begonnen
Aufgabenstellung
Was gilt im Parkmodell für den Knoten E?
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Grad zählt Kanten, nicht Beschriftungen oder die Zugehörigkeit zum Graphen.
Prüfe, welche Kante als letzter Schritt eines Wegs nach E dienen könnte.
Lösung anzeigen
E ist ausdrücklich ein Knoten, aber keine Kante führt zu E. Deshalb hat E Grad 0 und es gibt von einem anderen Knoten aus keinen Weg dorthin.
BPE 8J22 Punktemittel
Einen einfachen Weg prüfen
Noch nicht begonnen
Aufgabenstellung
Welche Folge ist im Parkmodell ein einfacher Weg von A nach C, ohne einen Knoten doppelt zu benutzen?
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Prüfe jedes benachbarte Paar der vorgeschlagenen Folge einzeln.
Eine Folge ist nur dann ein Weg, wenn kein einziger benötigter Schritt fehlt.
Lösung anzeigen
A–B–D–C verwendet die vorhandenen Kanten A–B, B–D und D–C und wiederholt keinen Knoten. A–D ist nicht vorhanden; an E liegt gar keine Kante.
BPE 8J22 Punktemittel
Einen einfachen Kreis erkennen
Noch nicht begonnen
Aufgabenstellung
Welche Folge ist nach unserer Kurskonvention ein einfacher Kreis im Parkmodell: Rückkehr zum Start, mindestens drei Knoten und keine sonstige Knotenwiederholung?
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Prüfe sowohl die Rückkehr zum ersten Knoten als auch die Existenz aller Kanten.
Eine geschlossene Schreibweise allein erzeugt keine fehlende Verbindung.
Lösung anzeigen
A–B–C–A kehrt über drei vorhandene Kanten zum Start zurück und wiederholt nur den Start am Ende. A–B–D ist offen. Bei A–D–C–A fehlt A–D.
BPE 8J23 Punkteanspruchsvoll
Ankommende Nachrichten zählen
Noch nicht begonnen
Aufgabenstellung
Im gerichteten Kommunikationsmodell bedeutet ein Pfeil eine erlaubte direkte Senderichtung. Wie groß ist der Eingangsgrad von C? Antworte mit einer ganzen Zahl.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Beim Eingangsgrad zeigen die Pfeilspitzen auf den betrachteten Knoten.
Trenne die ankommenden Pfeile von dem Pfeil, der C verlässt.
Lösung anzeigen
2. Die Pfeile A→C und B→C enden in C. Der Pfeil C→D beginnt dagegen in C und gehört zu seinem Ausgangsgrad.
BPE 8J23 Punkteanspruchsvoll
Ausgehende Nachrichten zählen
Noch nicht begonnen
Aufgabenstellung
Wie groß ist der Ausgangsgrad von A im gerichteten Kommunikationsmodell? Antworte mit einer ganzen Zahl.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Zähle Pfeile, deren Start bei A liegt.
Die Verbindung von D nach A hat die entgegengesetzte Richtung zur gesuchten Zählweise.
Lösung anzeigen
2. A→B und A→C gehen von A aus. D→A kommt in A an und zählt nicht zum Ausgangsgrad.
BPE 8J23 Punkteanspruchsvoll
Pfeile auf einem Weg beachten
Noch nicht begonnen
Aufgabenstellung
Welche der folgenden Folgen ist im Kommunikationsmodell ein gerichteter Weg von D nach B?
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Beginne bei D und suche einen tatsächlich von dort ausgehenden Pfeil.
Ein vorhandener Pfeil kann nicht ohne zusätzliche Kante in Gegenrichtung benutzt werden.
Lösung anzeigen
D→A und A→B sind beide vorhanden. D→C würde C→D rückwärts verwenden, und eine direkte Kante D→B ist nicht modelliert.
BPE 8J23 Punkteanspruchsvoll
Gewichte eines vorgegebenen Wegs addieren
Noch nicht begonnen
Aufgabenstellung
Im ungerichteten Fahrzeitmodell stehen die Gewichte für Minuten ohne Wartezeit. Wie viele Minuten benötigt der ausdrücklich vorgegebene Weg A–B–C–D? Antworte nur mit der Summe, ohne Einheit.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Schreibe zu jedem benachbarten Knotenpaar sein Kantengewicht auf.
Hier ist die Summe der drei Zeiten gefragt, nicht die Anzahl der Verbindungen.
Lösung anzeigen
12 Minuten: A–B kostet 4, B–C kostet 3 und C–D kostet 5 Minuten. Die drei Gewichte werden addiert. Die Zahl der Kanten wäre dagegen 3.
Lektionsabschluss
Bearbeite Aufgaben, um deine Auswertung zu sehen.
Automatische Aufgaben und eigene Selbstkontrollen werden getrennt ausgewiesen.