Satz von Berge
# Satz von Berge

In der Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Berge einer von mehreren Sätzen, die auf den französischen Mathematiker Claude Berge (1926–2002) zurückgehen. Berge publizierte den Satz im Jahre 1957 und gab damit eine Charakterisierung größtmöglicher Matchings in endlichen Graphen. In dieser Publikation gab Berge auch einen Algorithmus zur Bestimmung eines solchen Matchings.

## Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

    Ein Matching $M$ in einem endlichen Graphen $G$ ist von maximaler Mächtigkeit (und besteht damit aus genau $\nu (G)$ Kanten) dann und nur dann, wenn es in $G$ keinen $M$-erweiternden Weg gibt.

### Erklärungen

* In einem endlichen Graphen $G$ ist ein Matching $M\subseteq E(G)$ von maximaler Mächtigkeit genau dann, wenn in $G$ kein anderes Matching $M^{*}$ existiert mit $|M^{*}|>|M|$. Die Mächtigkeit eines solchen größtmöglichen Matchings nennt man die Matchingzahl von $G$ und bezeichnet sie mit $\nu (G)$.
* Ist ein Weg in $G$ gegeben, so wird $W$ als $M$-alternierend bezeichnet, falls die in $W$ vorkommenden Kanten abwechselnd zu $M$ und zu $E(G)\setminus M$ gehören.
* Inzidieren die durch einen $M$-alternierenden Weg $W$ verbundenen Endknoten mit keiner der in $M$ vorkommenden Kanten, so wird $W$ als $M$-erweiternd (oder als $M$-zunehmend) bezeichnet.
