Einführung in die Graphentheorie

Begriffserklärung

Ein Graph ist ein Netzwerk aus Knoten und verbindenden Strecken, den so genannten Kanten. Die Knoten (Kreise) stellen Orte, Bauteile oder Aktivitäten dar. Die Kanten (Linien) verbinden die Knoten untereinander und charackterisieren Entfernungen, zeitliche Abstände, oder Stückzahlen.

Kann ein Graph nur in einer Richtung durchlaufen werden, so spricht man von einem gerichteten Graphen. Die Kanten werden in diesem Fall als Pfeile dargestellt.

Vollständige Graphen zeichnen sich dadurch aus, dass alle Knoten direkt miteinander verbunden sind; andernfalls spricht man von unvollständigen Graphen.

Ein planarer Graph ist dadurch gekennzeichnet, dass sich alle Kanten überschneidungsfrei zeichnen lassen. Somit kann z.b. ein vollständiger Graph mit mehr als 4 Knoten niemals planar sein. Er wird als nichtplanar bezeichnet.

Des Weiteren wird ein Graph als Baum bezeichnet, wenn jeder Knoten des Graphen von jedem anderen aus über genau einen Weg zu erreichen ist.

Beispiele

• Dies ist ein vollständiger Graph mit 5 Knoten. Jeder Knoten ist direkt mit allen anderen Knoten verbunden. Da sich die Kanten überschneiden ist er nichtplanar.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1

• Dies ist ein gerichteter Graph mit 6 Knoten. Die Kanten überschneiden sich nicht, somit ist er planar, allerdings unvollständig.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2

Teile eines Graphen

Graphen können wiederum in verschiedene Einzelteile untergliedert werden (vgl. HMM 7.1):

• Kette: Der Graph ist ungerichtet und linear angeordnet (siehe Abbildung 3.1).
• Pfad: Der Graph ist gerichtet und linear angeordnet (siehe Abbildung 3.2).
• Masche: (siehe Abbildung 3.3).
• Schleife: (siehe Abbildung 3.4).

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 3

Die Anzahl der Kanten (m) eines Graphen ergeben sich bei einem Baum zu: m = n-1 Ein vollständiger Graph hat m = n*(n-1) / 2 Kanten. (mit n = Anzahl der Knoten)

Vorlesungsmittschnitte

Zur Vertiefung dieses Themengebietes können Sie sich Vorlesungsmittschnitte der Vorlesung Operations Research anschauen. Für die Vorlesung Einführung in die Betriebswirtschaftslehre sind jedoch nicht alle dieser Vorlesungsinhalte relevant.

Wintersemester 2007/2008

Vorlesungsmitschnitt zum Thema Graphentheorie aus dem Wintersemester 2007/2008
Vorlesungsmitschnitt zum Thema Graphentheorie/Gointograph aus dem Wintersemester 2007/2008