Mathematik: Diskrete Mathematik: Graphentheorie

Hoch zu Diskrete Mathematik Inhaltsverzeichnis

Vorwort

Die Graphen, mit denen sich die Graphentheorie beschäftigt, sind eine interessante mathematische Struktur. Sie spielen einerseits eine Rolle bei den Markov-Ketten aus dem Bereich der Wahrscheinlichkeitstheorie, sind ein wichtiges Instrument in fast jeder Disziplin der Informatik - angefangen von Endlichen Automaten aus der Theoretischen Informatik bis hin zur Routenberechnung für Navigationssysteme in der Geoinformatik - und spiegeln dabei Denkstrukturen wieder, die auch im Alltag oft vorkommen. So stehen hinter schematischen Darstellungen von U-Bahnnetzwerken genauso Graphen, wie sie auch hinter einem Organigramm stehen, das die Hierarchie einer Organisation beschreibt. Und so mancher Rätselfreund musste - möglicherweise nach langem Tüfteln - feststellen, dass es vom K3,3 keine planare Darstellung gibt.

Graphentheorie

Definitionen

Graph

Ein Graph G ist eine mathematische Struktur, die aus einer Knotenmenge V und einer Kantenmenge E besteht. Dabei gilt, dass $V\neq\varnothing$ und $V < \infty$. Eine Kante verbindet zwei Knoten miteinander und $E\subseteq\tbinom{V}{2}$.

Schreibweise: G = (V,E)

Ein Beispiel:

Graph G

G = {V,E}

V = {1,2,3,4,5,6}

E = {(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)}

Nachbarschaft und Grad

Zwei Knoten $x,y\in{V}$ heißen benachbart (auch adjazent), wenn $\{x,y\}\in E$.

Im obigen Beispiel sind z.B. 1 und 2 benachbart, 1 und 3 aber nicht.

Die Menge $N_G(x)$ wird als Nachbarschaft des Punktes x im Graphen G bezeichnet. Es gilt $N_G(x)=\{y\in V:\{x,y\}\in E\}$.

Im obigen Beispiel ist z.B. $N_G(2)=\{1,3,5\}$.

Als Grad von x bezeichnet man $deg(x)=|N_G(x)|$.

Im obigen Beispiel ist somit $deg(2)=3$.

Ein Knoten x wird als isoliert bezeichnet, wenn $deg(x)=0$.

Ein Knoten x wird als Blatt bezeichnet, wenn $deg(x)=1$.

Isomorphe Graphen

Zwei Graphen $G_1=(V_1,E_1)$ und $G_2=(V_2,E_2)$ heißen isomorph, wenn es eine Bijektion $f: V_1 \rightarrow V_2$ gibt, so dass $\forall x,y \in V_1 : \Bigl\{\{x,y\} \in E_1 \Rightarrow \{f(x), f(y)\} \in E_2 \Bigr\}$.

Subgraph

Ein Graph H=(W,F) heißt Subgraph von G=(V,E), wenn $W \subseteq V$ und $F \subseteq E$.

Schreibweise $H \subseteq G$.

gerichtete Graphen

In vielen Anwendungen ist es notwendig, den Kanten eine Richtung zu geben. In der Darstellung stellt man diese Richtung durch einen kleinen Pfeil dar.

Hier ein Beispiel für die Darstellung eines gerichteten Graphen: (Graphik stammt aus Wiki-Commons)