Graphentheorie

aus www.iwiki.de, der freien Wissensdatenbank

Ein Graph beschreibt das mathematische Modell für ein Netzwerk wie beispielsweise ein Stromleitungsnetz, ein Verkehrsnetz oder auch ein Beziehungsgeflecht zwischen Personen. Alle diese [Netzwerke] besitzen eine ähnliche Struktur: in irgendeiner Form werden Punkte oder auch Knoten(englisch: nodes oder vertices) über Verknüpfungen oder auch Kanten(englisch: edges) miteinander verbunden.

Beispiel für einfache Graphen

Die Linien repräsentieren die Kanten, die Punkte stellen die Knoten dar. Am Beispiel eines Computernetzwerkes würde das bedeuten, die Punkte stehen für die einzelnen angeschlossenen PC’s während die Kanten das Abbild der Netzwerk-Kabel sind.

[bearbeiten]

Regeln für Graphen

Nicht an jeder Kreuzung zweier Kanten muss zwangsläufig ein Knoten vorhanden sein. Das ist auf die zweidimensionale Abbildung eines dreidimensionalen Gebildes zurückzuführen. So können die Kabel eines Computernetzwerkes durchaus übereinander liegen ohne dass an dieser Stelle unbedingt ein Computer stehen muss. Da Graphen aber nur eine schematische beziehungsweise mathematische Darstellung der Realität sind, können und sollen sie so angepasst werden, dass diese Überlappungen vermieden werden.

Im Regelfall ist das sehr sinnvoll um Übersichtlichkeit zu erhalten.

Die Kanten eines Graphen müssen nicht zwangsweise gerade sein. Bei komplexeren Graphen ist es durchaus üblich geschwungene Kanten zu verwenden da oftmals sonst eine Kreuzung der Kanten nicht verhindert werden kann.

Zur besseren Übersicht werden die Knoten nummeriert.

[bearbeiten]

Graphentypen

Graph (ungerichtet, schlicht) ungerichtet: die Richtung der Verbindung ist unwichtig schlicht: das selbe Knotenpaar wird nicht durch mehr als einen Kanten verbunden, ein Knoten verbindet sich nicht mit sich selbst. Ist ein Paar(V, E) aus der Menge V, deren Elemente als Knoten bezeichnet werden, und einer Menge E, deren Elemente als Kanten bezeichnet werden. Dabei gilt: Jedes Element aus E hat die Form

e={v, w} für geeignete v, w $\in$ V.

oder auch: e ist die Kante, die den Knoten v mit dem Knoten w verbindet

Jede Kante muss mit einem Punkt beginnen und enden. Es gibt keine Kanten ohne End- beziehungsweise Anfangspunkte. Es besteht jedoch die Möglichkeit von Punkten, die keine Verbindung haben.

Graph (gerichtet) Beschreibt nicht nur die Verbindung zwischen zwei Punkten, sondern auch die Richtung dieser Verbindung. Für elektrische Netzwerke ist diese Beschreibung unbedeutend und wird deshalb auch in der Vorlesung nicht weiter behandelt

Graph (endlich) Sie sind für die Praxis am bedeutendsten. Sie bestehen aus einer endlichen Knoten- und Kantenmenge und lassen sich teilweise gut durch Matrizen erfassen.

[bearbeiten]

Adjazenzmatrix

Zwei Knoten heißen adjazent(benachbart) wenn sie durch mindestens eine Kante verbunden sind. Die Matrix beschreibt wie viele Kanten zwischen zwei gegebenen Knoten existieren.

Mathematisch interessant ist aber vor allem die Möglichkeit durch die Potenzierung einer Adjazenzmatrix (A) eine neue Matrix zu erhalten, welche als Aussage alle möglichen Verbindungen zwischen benachbarten und auch nicht benachbarten Knoten enthält. Dabei beschreibt die Höhe der Potenz die Anzahl der Kanten. Das bedeutet: die mit $A 2$ berechnete Matrix beschreibt alle Verbindungen zwischen allen Punkten, die zwei Kanten enthalten. Also beschreibt diese Matrix für jeden Punkt des Graphen auf wie vielen Wegen man von diesem zu einem anderen Punkt gelangen kann wobei jeder Weg aus zwei Kanten besteht.

Beispiel:

Beispiel für einen Graphen

$\begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 0 & 2 \\ 0 & 1 & 2 & 1 \end{pmatrix}^2 =$

$\begin{pmatrix} 1+1+1+0 & 1+2+1+0 & 1+1+0+0 & 0+1+2+0 \\ 1+2+1+0 & 1+4+1+1 & 1+2+0+2 & 0+2+2+1 \\ 1+1+0+0 & 1+2+0+2 & 1+1+0+4 & 0+1+0+2 \\ 0+1+2+0 & 0+2+2+1 & 0+1+0+2 & 0+1+4+1 \end{pmatrix}=$