4. Graphgrammatiken – Verarbeiten von Konzepten und Beziehungen

Abstraktion ist ein Grundprinzip in vielen Teilgebieten der Informatik und erlaubt es, die Komplexität eines Problems zu reduzieren. Anstelle eines einzelnen Objekts (Gegenstand, Person, Konzept etc.) werden Objektmengen (Mengen ähnlicher Objekte) und Beziehungsmengen zwischen diesen modellhaft beschrieben. Graphen, bestehend aus Knoten und Kanten, sind mächtige Generalisierungsverfahren und stehen bei vielen Anwendungen im Zentrum (Transportnetze, soziale Netze, Wissensgraph etc.). Graphgrammatiken sind Ersetzungssysteme, die Graphen durch Graphen ersetzen und Konsistenzregeln respektieren. Nach einer Kurzeinführung in die Graphentheorie wird die Mächtigkeit von Grammatiken über Graphen anhand des Königsberger Brückenproblems aufgezeigt, das von Leonhard Euler bereits 1736 allgemein gelöst wurde. Ein Anwendungsbeispiel zur Sicherung von Grundbesitz stammt aus der Parzellarvermessung; hier geht es um das konsistenzerhaltende Nachführen von Eigentumsverhältnissen. Soziogramme, als Beispiel für eine Schulklasse, können als Graphen oder äquivalente Matrizen dargestellt und studiert werden. Kurzum: Das Anwendungsfeld von Graphen reicht von technischen Problemstellungen bis hin zum Social Computing.