Eulersche und hamiltonische Graphen

Weg & Eigenschaften

Sei $G=\left(E,K\right)$ ein Graph, und $v,e\in E$.

Ein Weg von $v$ nach $w$ ist eine Folge von Ecken $\left(v=v_{1},v_{2},\ldots,v_{m}=w\right)$ mit der Eigenschaft, dass alle $\left\{ v_{i},v_{i+1}\right\} \in K$ (Kanten von $G$) sind. Der Weg heißt geschlossen (bzw. offen), falls $v=w$ (bzw. $v\neq w$).

Der Weg heißt (Kanten-)einfach, falls alle Kanten $\left\{ v_{i},v_{i+1}\right\}$ paarweise verschieden sind.

Der Weg heißt eckeneinfach, falls alle Ecken $v_{i}$ paarweise verschieden sind (für $i=1,\ldots,m-1$).

Die Länge eines Weges, ist die Anzahl der Kanten, die er enthält.

• eckeneinfach $\Rightarrow$ kanteneinfach

Abstand & Durchmesser

Bei einem zusammenhängenden Graphen ist der Abstand zweier Ecken die Länge des kürzesten Weges, der diese Ecken verbindet.

Der Durchmesser ist der maximale Abstand zweier Ecken.

eulerscher Graph

$G$ heißt eulerscher Graph, falls es in $G$ einen geschlossenen (Kanten-)einfachen Weg gibt, der jede Kante von $G$ enthält. Diesen Weg nennen wir eulersche Linie.

• $G$ ist eulerscher Graph $\Leftrightarrow$ jede Ecke von $G$ hat geraden Grad und $G$ ist zusammenhängend
• Problem der Königsberger Brücken

zusammenhängend

Ein Graph $G$ heißt zusammenhängend, falls je $2$ verschiedene Ecken durch einen (offenen) eckeneinfachen Weg verbunden werden können.

Kreis

Sei $G=\left(E,K\right)$ ein Graph. Ein geschlossener eckeneinfacher Weg in $G$ heißt Kreis.

Teilgraph

Sei $G=\left(E_{G},K_{G}\right)$ ein Graph. Ein Graph $H=\left(E_{H},K_{H}\right)$ heißt Teilgraph von $G$, falls $E_{H}\subseteq E_{G}$ und $K_{H}\subseteq K_{G}$.

hamiltonischer Graph

Sei $G$ ein Graph. Falls es in $G$ einen Kreis gibt, der alle Ecken von $G$ enthält, so heißt $G$ ein hamiltonischer Graph und der Kreis heißt Hamiltonkreis.

• Ist $G$ ein hamiltonischer Graph, so besitzt $G$ einen Teilgraphen $H$ mit:
  • $E_{H}=E_{G}$
  • $H$ ist zusammenhängend
  • $\left\vert E_{H}\right\vert=\left\vert K_{H}\right\vert$
• Traveling Salesman Problem

Adjazenzmatrix

Die Adjazenzmatrix zu einem Graphen mit $v_{1},\ldots,v_{n}$ ist die $n\times n$-Martix $M=\left(a_{ij}\right)$, wobei $a_{ij}$die Anzahl der Kanten zwischen der Ecke $v_{i}$ und $v_{j}$ ist. $M^{k}=\left(b_{ij}\right)$ gibt mit $b_{ij}$ an, wie viele Wege der Länge $k$ es zwischen $i$ und $j$ gibt.