i

Fachkonzept - Graph

Beschreibung vernetzter Strukturen

Ein Straßennetz besteht aus einer Vielzahl von Straßenabschnitten, die jeweils bestimmte Orte miteinander verbinden. Die folgende Karten zeigt einen Ausschnitt aus dem Straßennetz in Deutschland.

Kartenausschnitt
Quelle: OpenStreetMap

Will man die Information über ein solches Straßennetz beschreiben, so konzentriert man sich auf die relevanten Fakten und lässt alles andere erst einmal weg. Ist man z.B. nur an den Autobahnverbindungen um Ludwigshafen / Mannheim interessiert, so könnte eine abstrahierende Beschreibung des Autobahnnetzes wie folgt aussehen:

Autobahnnetz

Hier sind nur Autobahnabfahrten und Kreuzungspunkte verschiedener Autobahnen als Knoten und die Verbindungsstücke als Kanten dargestellt. Eine solche Darstellung modelliert nur die Information, die für den Modellnutzer relevant ist.

Graphen

Vernetzte Strukturen werden abstrahierend mit Hilfe von Graphen beschrieben.

Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten (die jeweils zwei Knoten miteinander verbinden).

Die Knoten repräsentieren die Objekte des Anwendungsbereichs, die Kanten die Beziehungen zwischen den Objekten.

Graphen sind ein wichtiges und häufig benutztes Modellierungsmuster in der Informatik, das in ganz unterschiedlichen Anwendungsbereichen zum Einsatz kommt (vgl. auch Abschnitt Exkurs - Graphen in Anwendungssituationen).

Hinweis zur Darstellung von Graphen

Eine ansprechende Darstellung von Graphen lässt sich recht schnell mit dem Software-Werkzeug yEd erzeugen.

Suche

v
2.3.5.1.2
www.inf-schule.de/algorithmen/standardalgorithmen/graphen/vernetztestrukturen/konzept_graph
www.inf-schule.de/2.3.5.1.2
www.inf-schule.de/@/page/Pbv0F21QdViKCOs2

Rückmeldung geben