Anhang

Übersicht - Begriffe der elementaren Graphentheorie

Adjazenzmatrix: Darstellung eines Graphen als Nachbarschaftstabelle, in der für jedes Paar von Knoten die Anzahl ihrer Verbindungskanten eingetragen wird. Adjazenzmatrizen und Adjazenzlisten werden u.a. genutzt, um Datenstrukturen als Graphen in den Computer eingeben- und weiterverarbeiten zu können.

Baum: zusammenhängender Graph, der keinen Kreis enthält (u.a. sind dann zwei beliebige Knoten immer nur durch genau einen Kantenzug verbunden)

Bewerteter (gewichteter) Graph: Graph, bei dem jeder Kante ein bestimmter Zahlwert zugeordnet ist.

Einfacher („schlichter“) Graph: Graph ohne Schlingen und Mehrfachkanten.

Eulergraph: Graph, der mindestens einen geschlossenen Eulerschen Kantenzug enthält.

Eulerscher Kantenzug (Eulerzug): Kantenzug, der alle Kanten eines Graphen genau einmal enthält. Knoten können dabei mehrmals durchlaufen werden. Man unterscheidet offene von geschlossenen Eulerschen Kantenzügen:

Geschlossener Eulerscher Kantenzug(auch Eulertour):¹ Eulerscher Kantenzug, der im Anfangsknoten endet.

Geschlossener Kantenzug: Kantenzug, bei dem Anfangs- und Endknoten übereinstimmen.

Graph: Besteht aus einer nichtleeren Menge von Knoten und einer Menge von Kanten. Jede Kante verbindet dabei zwei Knoten oder einen Knoten mit sich selbst.

Hamilton-Kreis: Kreis, der alle Knoten eines Graphen genau einmal enthält. Er muss dabei aber nicht alle Kanten des Graphen enthalten.

Hamiltongraph: Graph, der mindestens einen Hamilton-Kreis enthält.

Inzidenzmatrix: Darstellung eines Graphen als Matrix, bei der die Inzidenz von Knoten und Kanten dokumentiert wird. Inzidenzmatrizen dienen wie Adjazenzmatrizen der Eingabe und Weiterverarbeitung von Datenstrukturen.

Kantenzug: Eine Folge von aneinandergrenzenden Kanten (AB-BC-CD-…). Ein Kantenzug kann offen oder geschlossen sein, er kann Knoten und Kanten mehrmals enthalten.

Kreis: geschlossener Weg bzw. geschlossener Kantenzug, der jeden seiner Knoten genau einmal enthält (unter der Bedingung, dass man keinen Anfangsknoten auszeichnet, dieser wäre sonst zweimal enthalten, da der Kantenzug im Anfangsknoten endet). Durch das „Schließen des Kreises“ kann jeder der Knoten als Anfangsknoten betrachtet werden. Ein Kreis muss nicht alle Knoten eines Graphen enthalten, tut er es, so handelt es sich um einen Hamilton-Kreis.

Mehrfachkanten (Multikanten): parallele Kanten zwischen zwei Knoten

Multigraph: Graph, bei dem Mehrfachkanten zugelassen sind.

Offener Eulerscher Kantenzug: Eulerscher Kantenzug, bei dem Start- und Endknoten nicht identisch sind (z.B. Haus des Nikolaus“).

Offener Kantenzug: Kantenzug, bei dem Anfangs- und Endknoten verschieden sind.

Ordnung eines Knotens (Wertigkeit, Grad): Anzahl der Kantenenden, die in einem Knoten zusammentreffen (bei einer Schlinge zählen beide Kantenenden).

Planare („plättbare“) Graphen: Graph, der durch Umzeichnen so als ebener Graph dargestellt werden kann, dass sich seine Kanten nicht überschneiden. Die 5 platonischen Körper sind plättbare oder planare Graphen.

Tour: Ein Kantenzug, der aus lauter verschiedenen Kanten besteht. Im Gegensatz zu einem Weg darf eine Tour Knoten auch mehrmals enthalten.

Vollständiger Graph: Graph, bei dem jeder Knoten mit jedem anderen Knoten durch genau eine Kante verbunden ist.

Weg (Pfad): Kantenzug, der jeden seiner Knoten genau einmal enthält (Einzige Ausnahme: „geschlossener Weg“ → Kreis), es können somit keine Kanten doppelt vorkommen.²

Zusammenhängender Graph: Graph, bei dem es von jedem Knoten zu jedem anderen Knoten einen Kantenzug gibt, der die beiden verbindet. Ist das nicht der Fall, so kann man den Graphen in Komponenten (Teilgraphen) aufspalten, die keine Verbindung besitzen.

¹ Eine Eulertour wird fälschlicherweise auch als Eulerkreis, Eulerpfad oder Eulerweg bezeichnet. Ein Eulerzug darf Knoten mehrmals enthalten, was bei einem Kreis, Weg oder Pfad (mit Ausnahme des Startknotens) nicht der Fall ist. Falls das Problem im Unterricht auftritt, sollte man sich Zeit nehmen und es im Sinne der Aussagenlogik zur Abgrenzung nutzen: Jeder Eulerkreis ist eine Eulertour, aber nicht jede Eulertour ist ein Eulerkreis … .

² Der Begriff Weg wurde bei der Konzeption der Aufgabenblätter gemieden, da er in Quellen zu häufig in verschiedenen Bedeutungen verwendet wird, was im Unterricht nur zu unnötigen Überlagerungen führen würde.

Hintergrundinformationen: Herunterladen [odt][526 KB]

Hintergrundinformationen: Herunterladen [pdf][451 KB]

Weiter zu Unterrichtsverlauf