imported>Thomas Dresler: Tippfehler korrigiert

2025-10-19T22:08:19Z

Tippfehler korrigiert

Neue Seite

[[Datei:Graph K3 3.svg|gerahmt|K<sub>3,3</sub>: vollständig bipartiter Graph mit 3 [[Knoten (Graphentheorie)|Knoten]] pro [[Teilmenge]]]]
[[Datei:Simple-bipartite-graph.svg|mini|Ein einfacher, nicht vollständiger, bipartiter Graph mit Partitionsklassen <math> U </math> und <math> V </math>]]

Ein '''bipartiter''' oder '''paarer Graph''' ist ein [[mathematisches Modell]] für Beziehungen zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von [[Zuordnungsproblem]]en. Des Weiteren lassen sich für bipartite Graphen viele Grapheneigenschaften mit deutlich weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.

== Definitionen ==
Ein [[Einfacher Graph|einfacher]] [[Graph (Graphentheorie)|Graph]] <math>G=(V,E)</math> heißt bipartit oder paar, falls sich seine [[Knoten (Graphentheorie)|Knoten]] in zwei [[disjunkt]]e [[Teilmenge]]n ''A'' und ''B'' aufteilen lassen, sodass zwischen den Knoten innerhalb beider Teilmengen keine [[Kante (Graphentheorie)|Kanten]] verlaufen. Das heißt, für jede Kante <math>\{v,w\} \in E</math> gilt entweder <math>v \in A</math> und <math>w \in B</math> oder <math>v \in B</math> und <math>w \in A</math>. Die Menge <math>\{A,B\}</math> bezeichnet man dann als '''Bipartition''' des Graphen <math> G </math> und die Mengen <math> A,B </math> als '''Partitionsklassen'''. Vereinfacht dargestellt, ist ein bipartiter Graph ein [[Graph (Graphentheorie)|Graph]], in dem zwei Gruppen von Knoten existieren, innerhalb derer keine Knoten miteinander verbunden sind.

Der [[Graph (Graphentheorie)|Graph]] <math>G</math> heißt '''vollständig bipartit''', falls eine Bipartition <math>\{A,B\}</math> existiert, sodass jeder [[Knoten (Graphentheorie)|Knoten]] aus <math>A</math> mit jedem Knoten aus <math>B</math> verbunden ist. Einen solchen Graphen bezeichnet man auch als <math>K_{m,n}</math>, wobei <math>m</math> und <math>n</math> jeweils die Anzahl der Knoten von <math>A</math> und <math>B</math> sind. Ein vollständig bipartiter Graph, bei dem <math>m=1</math> oder <math>n=1</math> ist, heißt [[Sterngraph]].

== Eigenschaften ==
Für alle bipartiten Graphen gilt:

* Die [[Paarungszahl]] entspricht der [[Knotenüberdeckungszahl]].
* Die Partitionsklassen <math> A,B </math> sind schon nach Definition [[stabile Menge]]n.
* Der [[Chromatischer Index|chromatische Index]] entspricht seinem [[Maximalgrad]]. Eine gültige Kantenfärbung lässt sich in <math>O(n \cdot m)</math> bestimmen.
* Jeder bipartite Graph ist [[Färbung (Graphentheorie)#Knotenfärbungen|2-knotenfärbbar]]. Jede Partitionsklasse bekommt also eine Farbe zugewiesen. Umgekehrt ist auch jeder 2-färbbare Graph bipartit.
* Ein <math display="inline">k</math>-[[Regulärer Graph|regulärer]] bipartiter Graph besitzt <math display="inline">k</math> disjunkte perfekte [[Paarung (Graphentheorie)|Matchings]].
* Ein Graph ist genau dann bipartit, wenn er keinen [[Kreis (Graphentheorie)|Kreis]] ungerader Länge enthält.
* Die [[kantenchromatische Zahl]] entspricht seinem [[Maximalgrad]].
* Der [[Listenchromatischer Index|Listenchromatische Index]] ist gleich dem [[Chromatischer Index|chromatischen Index]]. Damit sind bipartite Graphen eine Klasse von Graphen, für welche die [[Listenfärbung#Eigenschaften|Listenfärbungsvermutung]] zutrifft.
* Es gilt <math> \chi_T (G) \leq \Delta (G) +2</math>, wobei <math> \chi_T (G) </math> die [[totalchromatische Zahl]] ist und <math> \Delta (G) </math> der [[Maximalgrad]]. Für bipartite Graphen gilt also die [[Totalfärbung]]svermutung.
* Alle bipartiten Graphen sind [[Perfekter Graph|perfekte Graphen]], somit stimmt für jeden [[Induzierter Teilgraph|induzierten Teilgraphen]] die [[Cliquenzahl]] mit der [[Chromatische Zahl|chromatischen Zahl]] überein.

Nach dem [[Satz von König (Graphentheorie)|Satz von König]] entspricht in bipartiten Graphen die Größe der minimalen [[Knotenüberdeckung]] der Größe des [[Matching (Graphentheorie)|maximalen Matchings]]. Eine alternative und äquivalente Form dieses Satzes besteht darin, dass die Größe der maximalen unabhängigen Menge plus die Größe des maximalen Matchings gleich der Anzahl der Knoten ist. In jedem [[Graph (Graphentheorie)|Graphen]] ohne isolierte [[Knoten (Graphentheorie)|Knoten]] entspricht die Größe der minimalen [[Kantenüberdeckung]] plus der Größe eines maximalen Matchings der Anzahl der Knoten. Aus der Kombination dieser Gleichung mit dem Satz von König folgt, dass in bipartiten Graphen die Größe der minimalen Kantenüberdeckung gleich der Größe der maximalen unabhängigen Menge ist und dass die Größe der minimalen Kantenüberdeckung plus der Größe der minimalen Knotenüberdeckung gleich der Anzahl der Knoten ist.

Außerdem gilt: Jeder bipartite Graph, das Komplement jedes bipartiten Graphen, der [[Kantengraph]] jedes bipartiten Graphen und das Komplement des Kantengraphen jedes bipartiten Graphen sind alle [[Perfekter Graph|perfekte Graphen]]. Dies war eines der Ergebnisse, die die Definition perfekter Graphen motivierten.<ref>{{cite journal
|title=Modern Graph Theory
|volume= 184
|journal= Graduate Texts in Mathematics
|author=Béla Bollobás
|publisher=Springer
|year= 1998
|language=en
|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165}}</ref>

Nach dem Satz der starken perfekten Graphen haben die perfekten Graphen eine verbotene Charakterisierung, die der von bipartiten Graphen ähnelt: Ein Graph ist genau dann bipartit, wenn er keinen ungeraden Zyklus als [[Teilgraph]] hat, und ein [[Graph (Graphentheorie)|Graph]] ist genau dann perfekt, wenn er keinen ungerader [[Zyklus (Graphentheorie)|Zyklus]] oder sein [[Komplementgraph]]en als induzierten Teilgraphen hat. Die bipartiten Graphen, [[Kantengraph]]en von bipartiten Graphen und ihre Komplementgraphen bilden vier der fünf Grundklassen perfekter Graphen, die für den Beweis des Satzes der starken perfekten Graphen verwendet werden.<ref>{{cite journal
| last1 = Chudnovsky | first1 = Maria
| last2 = Robertson | first2 = Neil
| last3 = Seymour | first3 = Paul
| last4 = Thomas | first4 = Robin
| doi = 10.4007/annals.2006.164.51
| issue = 1
| journal = [[Annals of Mathematics]]
| pages = 51–229
| title = The strong perfect graph theorem
| volume = 164
| year = 2006
| language = en
| arxiv = math/0212070}}</ref>

Für einen [[Knoten (Graphentheorie)|Knoten]] wird die Anzahl benachbarter Knoten als [[Grad (Graphentheorie)|Grad]] des Knoten bezeichnet und als <math> \deg(v) </math> bezeichnet. Die Gradsummenformel für einen bipartiten Graphen besagt, dass
:<math> \sum_{v \in A} \deg(v) = \sum_{u \in B} \deg(u) = |E| </math>

Die [[Gradfolge]] eines bipartiten Graphen ist das Paar von Listen, das jeweils die [[Knotengrad]]e der beiden Partitionsklassen <math> A </math> und <math> B </math> enthält. Beispielsweise hat der vollständige bipartiten Graph <math> K_{3,5} </math> die Gradfolge <math> (5, 5, 5), (3, 3, 3, 3, 3) </math>. [[Isomorphismus|Isomorphe]] bipartite Graphen haben die gleiche Gradfolge. Die Gradfolge identifiziert jedoch im Allgemeinen einen bipartiten Graphen nicht eindeutig. In einigen Fällen können nicht-isomorphe zweigliedrige Graphen die gleiche Gradfolge aufweisen.

== Kombinatorik ==
Die Anzahl der bipartiten Graphen steigt schneller als [[Exponentialfunktion|exponentiell]] mit der Anzahl <math>n</math> der [[Knoten (Graphentheorie)|Knoten]]. Die folgende [[Tabelle]] zeigt die mit Hilfe eines [[Computer]]s bestimmten Anzahlen für <math>n \leq 12</math>:<ref>{{OEIS|A033995}}</ref><ref>{{OEIS|A005142}}</ref>
{| class="wikitable" style="text-align:right"
! colspan="3" |Anzahl der bipartiten Graphen
|-
!n
!alle
!zusammenhängend
|-
!1
|1
|1
|-
!2
|2
|1
|-
!3
|3
|1
|-
!4
|7
|3
|-
!5
|13
|5
|-
!6
|35
|17
|-
!7
|88
|44
|-
!8
|303
|182
|-
!9
|1119
|730
|-
!10
|5479
|4032
|-
!11
|32303
|25598
|-
!12
|251135
|212780
|}

== Algorithmen ==
{{Siehe auch|Graphpartitionierung}}
Mit dem [[Algorithmus von Hopcroft und Karp]] lässt sich in der [[Laufzeit (Informatik)|Laufzeit]] <math>O(m\sqrt{n})</math> ein [[maximales Matching]] finden und darüber auch die [[Stabilitätszahl]] bestimmen.

Mit einem einfachen [[Algorithmus]], der auf [[Tiefensuche]] basiert, lässt sich in linearer [[Laufzeit (Informatik)|Laufzeit]] bestimmen, ob ein [[Graph (Graphentheorie)|Graph]] bipartit ist, und eine gültige Partition bzw. 2-[[Färbung (Graphentheorie)|Färbung]] ermitteln. Dabei wird einem beliebigen [[Knoten (Graphentheorie)|Knoten]] eine Farbe, und seinen Kindern die jeweils komplementäre Farbe zugewiesen. Wird beim Färben festgestellt, dass zwei benachbarte Knoten die gleiche Farbe haben, ist der Graph nicht bipartit.

Die Hauptidee besteht darin, jedem [[Knoten (Graphentheorie)|Knoten]] die Farbe zuzuweisen, die sich von der Farbe des übergeordneten Knotens in der [[Tiefensuche]] unterscheidet, und Farben in der Hauptreihenfolge der Tiefensuche zuzuweisen. Dies führt zwangsläufig zu einer 2-[[Färbung (Graphentheorie)|Färbung]] des [[Aufspannender Baum|aufspannenden]] Waldes, der aus den [[Kante (Graphentheorie)|Kanten]] besteht, die die Knoten mit ihren übergeordneten Knoten verbinden, aber möglicherweise werden einige Kanten, die nicht zum Wald gehören, nicht richtig gefärbt. Einer der beiden Endknoten jeder Kante, die nicht zum Wald gehört, ist ein Vorfahr des anderen Endknotens. Wenn bei der Tiefensuche eine Kante dieses Typs entdeckt wird, sollte überprüft werden, ob diese beiden Knoten unterschiedliche Farben haben. Wenn dies nicht der Fall ist, bildet der Pfad im Wald vom Vorfahren zum Nachkommen zusammen mit der falsch gefärbten Kante einen ungeraden [[Zyklus (Graphentheorie)|Zyklus]], der vom [[Algorithmus]] zusammen mit dem Ergebnis zurückgegeben wird, dass der Graph nicht bipartit ist. Wenn der Algorithmus jedoch beendet wird, ohne einen ungeraden Zyklus dieses Typs zu finden, muss jede Kante richtig gefärbt sein, und der Algorithmus gibt die Färbung zusammen mit dem Ergebnis zurück, dass der Graph bipartit ist.<ref>{{cite journal
| last = Sedgewick | first = Robert
| pages = 109–111
| journal = Addison-Wesley
| title = Algorithms in Java, Part 5: Graph Algorithms
| language = en
| year = 2004}}</ref>

Alternativ kann ein ähnlicher [[Algorithmus]] mit [[Breitensuche]] anstelle der Tiefensuche verwendet werden. Wiederum erhält jeder [[Knoten (Graphentheorie)|Knoten]] die entgegengesetzte Farbe zu seinem übergeordneten Knoten im [[Suchbaum]] in der Reihenfolge der Breitensuche. Wenn beim Färben eines Knotens eine [[Kante (Graphentheorie)|Kante]] vorhanden ist, die ihn mit einem zuvor gefärbten Knotens mit derselben Farbe verbindet, bildet diese Kante zusammen mit den [[Pfad (Graphentheorie)|Pfaden]] im Suchbaum der Breitensuche ihrer beiden Endpunkte mit ihrem letzten gemeinsamen Vorfahren einen ungeraden [[Zyklus (Graphentheorie)|Zyklus]]. Wenn der Algorithmus beendet wird, ohne auf diese Weise einen ungeraden Zyklus zu finden, muss er eine korrekte Färbung gefunden haben und kann daraus schließen, dass der Graph bipartit ist.<ref>{{cite journal
| last1 = Kleinberg | first1 = Jon
| last2 = Tardos | first2 = Éva
| pages = 94–97
| journal = Addison-Wesley
| title = Algorithm Design
| language = en
| year = 2006}}</ref>

Für die Schnittgraphen mit <math>n</math> Strecken oder andere einfache Formen in der [[Euklidische Ebene|euklidischen Ebene]] ist es möglich, mit einer [[Laufzeit (Informatik)|Laufzeit]] von <math>\mathcal{O}(n \cdot \log(n))</math> zu testen, ob der [[Graph (Graphentheorie)|Graph]] bipartit ist und entweder eine 2-[[Färbung (Graphentheorie)|Färbung]] oder einen ungeraden [[Zyklus (Graphentheorie)|Zyklus]] zu finden, obwohl der Graph selbst bis zu <math>\mathcal{O}(n^2)</math> [[Kante (Graphentheorie)|Kanten]] haben kann.<ref>{{cite journal
| last = Eppstein | first = David
| arxiv = cs.CG/0307023
| doi = 10.1145/1497290.1497291
| issue = 2
| journal = ACM Transactions on Algorithms
| pages = Art. 15
| title = Testing bipartiteness of geometric intersection graphs
| language = en
| volume = 5
| year = 2009}}</ref>

=== Matchings ===
{{Hauptartikel|Matching (Graphentheorie)}}Ein [[Matching (Graphentheorie)|Matching]] in einem [[Graph (Graphentheorie)|Graphen]] ist eine [[Teilmenge]] seiner [[Kante (Graphentheorie)|Kanten]], von denen keine zwei einen [[Knoten (Graphentheorie)|Knoten]] gemeinsam haben. [[Algorithmus|Algorithmen]] mit [[Polynomieller Algorithmus|polynomieller]] [[Laufzeit (Informatik)|Laufzeit]] sind für viele Anwendungen mit Matchings bekannt, einschließlich [[Maximales Matching|maximaler Matchings]], dem Maximum Weight Matching und dem [[Stable Marriage Problem]].<ref>{{cite journal
| last1 = Ahuja | first1 = Ravindra K.
| last2 = Magnanti | first2 = Thomas L.
| last3 = Orlin | first3 = James B.
| pages = 461–509
| journal = Prentice Hall
| title = Network Flows: Theory, Algorithms, and Applications
| language = en
| year = 1993}}</ref>
In vielen Fällen sind Matching-Probleme für bipartite Graphen einfacher zu lösen als für nicht bipartite Graphen, und viele Matching-Algorithmen wie der [[Algorithmus von Hopcroft und Karp]] für maximale Matchings funktionieren nur für bipartite Graphen korrekt.<ref>{{cite journal
| first1 = John E. | last1 = Hopcroft
| first2 = Richard M. | last2 = Karp
| title = An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs
| language = en
| journal = SIAM Journal on Computing
| volume = 2
| issue = 4
| pages = 225–231
| year = 1973
| doi = 10.1137/0202019}}</ref>

Nehmen wir als einfaches Beispiel an, dass eine Gruppe <math>P</math> von Personen Jobs aus einer Menge <math>J</math> von Jobs sucht, wobei nicht alle Personen für alle Jobs geeignet sind. Diese Situation kann als bipartiter Graph <math>(P, J, E)</math> modelliert werden, bei dem eine Kante jeden Arbeitssuchenden mit jedem geeigneten Job verbindet. Ein [[perfektes Matching]] beschreibt eine Möglichkeit, alle Arbeitssuchenden gleichzeitig zufrieden zu stellen und alle Jobs zu besetzen. Der [[Heiratssatz]] liefert eine Charakterisierung der bipartiten Graphen, die ein perfektes Matching ermöglichen. Das [[National Resident Matching Program]] in den Vereinigten Staaten verwendet Matching-Algorithmen, um dieses Problem für Medizinstudenten und Jobs in Krankenhäusern zu lösen.

== Verallgemeinerung ==
Ein [[k-partiter Graph]] ist ein Graph, dessen Knotenmenge in <math>k</math> Partitionen unterteilt werden kann, sodass es keine Kante zwischen zwei Knoten einer Partition gibt.

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C-Sharp|C#]] zeigt die Implementierung eines [[Algorithmus]], der prüft, ob ein [[ungerichteter Graph]] bipartit ist. Der ungerichtete Graph wird als [[Feld (Datentyp)#Dimensionen|zweidimensionales Array]] für die [[Adjazenzmatrix]] deklariert. Der Algorithmus weist [[Benachbart|benachbarten]] Knoten alternierende Farben zu. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''Main'' verwendet, die das Ergebnis auf der Konsole ausgibt.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/bipartite-graph/ Check whether a given graph is Bipartite or not]</ref><syntaxhighlight lang="c#">
using System;
using System.Collections.Generic;

class BipartiteGraph
{
// Diese Methode gibt true zurück, wenn der Graph bipartit ist, sonst false. Benachbarten Knoten werden alternierende Farben zugewiesen.
private static bool IsBipartite(int[,] graph, int startIndex, int[] coloredVertices)
{
coloredVertices[startIndex] = 1; // Weist dem Startknoten eine Farbe zu
Queue<int> queue = new Queue<int>(); // Deklariert eine Queue für die Knotenindexe
queue.Enqueue(startIndex); // Fügt den Startknoten der Queue hinzu
while (queue.Count != 0) // Solange die Queue nicht leer ist
{
int index = queue.Peek(); // Index des vordersten Knotens
queue.Dequeue(); // Entfernt den vordersten Knoten
if (graph[index, index] == 1) // Wenn der Graph eine Schleife enthält, wird false zurückgegeben
{
return false;
}
for (int i = 0; i < coloredVertices.Length; i++) // for-Schleife, die die Knoten durchläuft
{
if (graph[index, i] == 1 && coloredVertices[i] == -1) // Wenn die Knoten verbunden sind und der Zielknoten nicht gefärbt ist
{
coloredVertices[i] = 1 - coloredVertices[index]; // Weist dem benachbarten Knoten die alternierende Farbe zu
queue.Enqueue(i); // Fügt den Knoten der Queue hinzu
}
else
{
if (graph[index, i] == 1 && coloredVertices[i] == coloredVertices[index]) // Wenn die Knoten verbunden sind und dieselbe Farbe haben, wird false zurückgegeben
{
return false;
}
}
}
}
return true; // Wenn alle benachbarten Knoten alternierende Farben haben, wird true zurückgegeben
}

// Diese Methode gibt true zurück, wenn der Graph bipartit ist, sonst false
private static bool IsBipartite(int[,] graph, int numberOfVertices)
{
int[] coloredVertices = new int[numberOfVertices]; // Deklariert ein Array für die Farben der Knoten
for (int i = 0; i < numberOfVertices; i++) // for-Schleife, die die Knoten durchläuft
{
coloredVertices[i] = -1; // Initialisiert die Knoten mit -1, sodass die Knoten am Anfang nicht gefärbt sind
}
// Prüfung für die Komponenten des Graphen
for (int i = 0; i < numberOfVertices; i++) // for-Schleife, die die Knoten durchläuft
{
if (coloredVertices[i] == -1 && !IsBipartite(graph, i, coloredVertices)) // Wenn der Knoten noch nicht gefärbt ist und die Komponente mit diesem Startknoten nicht bipartit ist, wird false zurückgegeben
{
return false;
}
}
return true; // Wenn alle Komponenten bipartit sind, wird true zurückgegeben
}

// Hauptmethode, die das Programm ausführt
public static void Main(String[] args)
{
// Deklariert und initialisiert ein zweidimensionales Array für die Adjazenzmatrix eines ungerichteten Graphen mit 4 Knoten
int[,] graph = {{ 0, 1, 0, 1 },
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0},
};
int numberOfVertices = (int) graph.GetLongLength(0); // Variable für die Anzahl der Knoten
if (IsBipartite(graph, numberOfVertices)) // Aufruf der Methode
{
Console.WriteLine("Der Graph ist bipartit."); // Ausgabe auf der Konsole
}
else
{
Console.WriteLine("Der Graph ist nicht bipartit."); // Ausgabe auf der Konsole
}

Console.ReadLine();
}
}
</syntaxhighlight>

== Siehe auch ==
* [[Matching (Graphentheorie)]]
* [[Petri-Netz]]
* [[Sekretärinnenproblem]]

== Literatur ==
* Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: ''Exakte Algorithmen für schwere Graphenprobleme'', Springer-Verlag, Berlin Heidelberg, 2010, ISBN 978-3-642-04499-1.
* Sven Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen, Vieweg+Teubner Verlag, 2012, ISBN 978-3-8348-1849-2.

== Weblinks ==

{{Wikiversity|Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 20|Eine Vorlesung über bipartite Graphen im Rahmen eines Kurses zur diskreten Mathematik}}
{{Commonscat|Bipartite graphs|Bipartiter Graph}}
* [https://www.spektrum.de/lexikon/mathematik/bipartiter-graph/2289 ''Bipartiter Graph.''] In: ''Springer Lexikon der Mathematik.''

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4145661-0}}
[[Kategorie:Bipartiter Graph| ]]
[[Kategorie:Graphenklasse]]

Bipartiter Graph - Versionsgeschichte

imported>Thomas Dresler: Tippfehler korrigiert