Akademik

Graph

 

[griech. graphein »schreiben«, »zeichnen«] der, anschauliches mathematisches Modell zur Beschreibung von Problemen, die durch Punkte und Verbindungslinien beschrieben werden können, z. B. Verwandtschaftsbeziehungen. Dabei stehen die Punkte (Knoten) für die Objekte und die Linien (Kanten) für Beziehungen zwischen den Objekten. Die Verbindungslinien dürfen Schleifen bilden und sich überkreuzen (Letzteres ist meist unerwünscht und wird deshalb etwa durch andere Anordnung oder zusätzliche Knoten möglichst vermieden). Die Aneinanderhängung von benachbarten Kanten nennt man einen Weg. Nicht alle Knoten eines Graphen müssen durch Wege verbunden sein. Sind alle Beziehungen gerichtet, d. h. durch Pfeile als Verbindungslinien darstellbar, spricht man von einem gerichteten Graphen. Ein Baum ist ein spezieller Graph.

 

Mit Graphen lassen sich sehr allgemeine Probleme anschaulich darstellen. Praktische Anwendung finden Graphen z. B. in der Theorie der Netzwerkplanung, in der Netzplantechnik sowie in der Darstellung von hierarchischen Strukturen, wofür Bäume besonders geeignet sind.

Graph,

 

1) das, -s/-e, allgemein: Schriftzeichen, kleinste (nicht bedeutungsunterscheidende) Einheit in schriftlichen Äußerungen (z. B. der Buchstabe D als Majuskel oder Minuskel).

 

 2) der, -en/-en, Mathematik: 1) Struktur, die der Graphentheorie, einem Teilgebiet der Kombinatorik, zugrunde liegt. Ausgangspunkt sind Probleme, die durch Punkte und Verbindungslinien veranschaulicht werden können. Beispiel: Gegeben seien Werke A, B und Abnehmer C, D, E. Geschäftsbeziehungen (Transporte oder Ähnliches) stelle man durch eine Verbindungslinie dar, solche »mit sich selbst« durch eine geschlossene Linie (Schlinge) von einem Punkt zu diesem selbst. Die Lage der Punkte und die Gestalt der Verbindungslinien sind unerheblich. - Abstrakt ist ein Graph ein Tripel G = (E(G), K(G), Ψ_G), bestehend aus einer Menge E(G) von Ecken oder Knoten (den Punkten), einer zu E(G) elementfremden Menge K(G) von Kanten (den Verbindungslinien zwischen jeweils zwei Ecken) und einer Funktion Ψ_G, die jeder Kante ein Paar von Ecken zuordnet. In der Graphentheorie werden Graphen untersucht, die zusätzliche Eigenschaften haben, z. B. deren Kanten gerichtet oder bewertet sind. Praktische Anwendung finden Graphen z. B. in der Theorie der Netzplanung (Netzplantechnik), in der Elementarteilchenphysik (Feynman-Graphen) oder Chemie. Für die Entwicklung der Graphentheorie spielte das Vierfarbenproblem eine wichtige Rolle.

 

2) bildliche Darstellung von Relationen in Form von Punktmengen, bei denen gewisse Punktpaare durch Kurven verbunden sind. 3) bei Funktionen synonym für die Funktionskurve beziehungsweise -fläche.

 

Literatur:

 

R. Halin: Graphentheorie (²1989);

 K. Wagner u. R. Bodendiek: Graphentheorie, 3 Bde. (1989-93);

 J. Clark: Graphentheorie. Grundlagen u. Anwendungen (a. d. Engl., 1994);

 R. Bodendiek u. R. Lang: Lb. der Graphentheorie, 2 Bde. (1995-96).