zurück zu Grundbegriffe I

1.1 Definition eines Graph

Def.: Ein Graph G ist ein Paar (V,E) zweier endlicher Mengen – Menge 1 ist V (G), die Menge der Knoten (-punkte) und Menge 2 ist E(G), die Menge der Kanten, wobei jedem Element der Menge E(G) ein (un-) geordnetes Paar aus V(G) zugeordnet ist.

1.1.1 Zur Entstehung

Die Graphentheorie ist übrigens der Mathematik zugehörig und bedient sich der Notation der Mengenlehre.

Die Wurzel der Graphentheorie liegt in der Untersuchung topischer Probleme, die sich durch eine Anzahl von Ecken (Punkten) und Kanten (Verbindungen) zwischen ihnen geschreiben lassen. Beispiel ist das Königsberger Brückenproblem (siehe unter Euler’sche Linie).

1.2 Anwendung

Mit Graphen können Strukturen, Hirachien, Abläufe und dergleichen dargestellt und untersucht werden.

Z.B.: alle möglichen Netze (Verkehrs-, Telefonnetz…), Baumstruktur, Flußdiagramm, Organigramme, Netzpläne für Programmabläufe, Datenstrukturen, endl. Automaten, Organisationsformen Netzwerke…
Besonders in der Informatik lassen sich durch Graphen viele Probleme beschreiben und über Graphenalgorithmen lösen.

Die endlichen Graphen der Graphentheorie können wie folgt dargestellt werden:

• Straßennetz: Kreuzungen = Knoten und Straßen = Kanten
• Schaltnetze: Schalter bzw. Gatter = Knoten und Leitung = Kante
• Computernetwerk: Computer = Knoten und Verbindungskabel = Kante…

Ein Funktionsgraph aus der Mathematik hat hingegen unendlich viele Knoten:

Siehe auch GEDV: formale Sprachen; Syntax Homomorphismus; endlicher Automaten

1.3 Darstellung von Graphen

X= (V,E)

V steht für Vertex = Knoten

E für Edge = Kante

V und E sind Mengen mit endlich vielen Elementen;

• Aufzählung der Elemente V={1,2,3}
• Beschreibung
• graphische Darstellung (nur bei kleinen Graphen möglich)

1.4 Speicherung von Graphen

2 Methoden zur Speicherung von Graphen: Adjazenzmatrix-Darstellung und Adjazenzlisten-Darstellung.
Ein Knoten v heißt adjazent zu einem Knoten w, wenn eine Kante von v nach w führt.