Satz von Berge

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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[Bearbeiten | Quelltext bearbeiten]

Der Satz lässt sich angeben wie folgt:[1][2][3][4]

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

Erklärungen[Bearbeiten | Quelltext bearbeiten]

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

Anmerkungen[Bearbeiten | Quelltext bearbeiten]

  • In der englischsprachigen Graphentheorieliteratur spricht man von einem augmenting path. Daher ist der Satz von Berge hier auch als augmenting path theorem bekannt.[5][6]
  • Der Satz tritt auch schon in der Pionierarbeit Die Theorie der regulären Graphs des dänischen Mathematikers Julius Petersen aus dem Jahre 1891 auf.[6]
  • Oft wird (so etwa im Bronstein) ein Matching von maximaler Mächtigkeit auch kurz ein maximales Matching genannt, obwohl diese Benennung nicht dem sonst üblichen – von der Ordnungstheorie herrührenden – Maximalitätsbegriff entspricht.[4]

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Claude Berge: Graphs and Hypergraphs. 1973, S. 124.
  2. John Clark, Derek Allan Holton: Graphentheorie. 1994, S. 137.
  3. Lutz Volkmann: Fundamente der Graphentheorie. 1996, S. 117.
  4. a b I. N. Bronstein, K. A. Semendjajev u. a.: Taschenbuch der Mathematik. 2016, S. 420.
  5. Dieter Jungnickel: Graphs, Networks and Algorithms. 2008, S. 390 ff.
  6. a b Jonathan L. Gross, Jay Yellen (Hrsg.): Handbook of Graph Theory. 2004, S. 1105.