52 lines
2.2 KiB
TeX
52 lines
2.2 KiB
TeX
\begin{definition}
|
|
Ein \textit{Graph} ist ein Paar (V,E) von Ecken (Vertices) und Kanten
|
|
(Edges),
|
|
wobei Kanten zwischen zwei Ecken verlaufen.
|
|
\end{definition}
|
|
|
|
\begin{definition}
|
|
Ein Graph heißt \textit{bipartit}, wenn wir $V = V_1 \sqcup V_2$ als
|
|
disjunkte
|
|
Vereinigung zweier Knotenmengen schreiben können, sodass die Teilgraphen auf
|
|
$V_1$ und $V_2$ jeweils keine Kanten besitzen.
|
|
\end{definition}
|
|
|
|
\begin{definition}
|
|
Ein Weg in einem Graphen $G=(V,E)$ ist eine Folge von Knoten $V_1,\ldots,V_n$
|
|
sodass es für $1\leq i\leq n-1$ jeweils eine Kante zwischen $V_i$ und
|
|
$V_{i+1}$ gibt.
|
|
Ein Weg mit $V_1=V_n$ heißt auch \textit{Kreis}.
|
|
\end{definition}
|
|
|
|
\begin{definition}
|
|
Ein Graph ist zusammenhängend, wenn es für je zwei Knoten $v_1,v_2$ einen Weg
|
|
von $v_1$ nach $v_2$ gibt.
|
|
Für einen Knoten $v\in V$ ist die Zusammenhangskomponenten von $v$ die Menge
|
|
aller Knoten, die von $v$ durch Wege erreichbar sind.
|
|
Jeder Graph zerfällt auf diese Weise in Zusammenhangskomponenten.
|
|
\end{definition}
|
|
|
|
\begin{lemma}
|
|
Ein Graph ist bipartit, genau dann, wenn er keine Zyklen ungerader Länge
|
|
enthält.
|
|
\end{lemma}
|
|
|
|
\begin{proof}
|
|
Ist der Graph bipartit und sei ein Zyklus gegeben, so wechseln wir mit jeder
|
|
Kante die 'Hälfte', wir können also nur nach gerade vielen Kanten wieder am
|
|
Ausgangspunkt sein, und somit ist jeder Zyklus gerade.
|
|
\\
|
|
Sei nun $G$ ein Graph, der nur gerade Zyklen enthält.
|
|
OBdA sei $G$ zusammenhängend, wir wählen $v_0$ und setzen $v_0 \in A$.
|
|
Für einen Knoten $v$ betrachte einen Weg von $v_0$ nach $v$, hat dieser gerade
|
|
Länge, definiren $v\in A$, hat dieser ungerade Länge, definiere $v\in B$.
|
|
Dies ist wohldefiniert, da sonst weg von $v_0$ nach $v$ mit ungerader und
|
|
gerader Parität existiert, also zusammen ungerader Zyklus.
|
|
Damit sind die Teilmengen $A,B$ definiert.
|
|
Angenommen, es gibt nun eine Kante in $A$ von $v_1$ nach $v_2$, so betrachte
|
|
Wege von $v_0$ nach $v_1,v_2$ mit jeweils gerader Länge, dann ist aber
|
|
$v_0\ldots v_1 - v_2 \ldots v_0$ ungerader Zyklus.
|
|
Analoge Argumentation für $B$.
|
|
Also ist der Graph mit den konstruierten Mengen $A,B$ bipartit.
|
|
\end{proof}
|