Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 20/latex
\setcounter{section}{20}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller6.jpg} }
\end{center}
\bildtext {Doch dann hat sie das Beste daraus gemacht. Vermutlich hängt ihre Zugänglichkeit und Menschenbezogenheit auch mit ihren frühen Erfahrungen zusammen.} }
\bildlizenz { Waeller6.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
\zwischenueberschrift{Bipartite Graphen}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Star graphs.svg} }
\end{center}
\bildtext {Ein \stichwort {Sterngraph} {} ist ein vollständiger bipartiter Graph der Form $K_{1,s}$.} }
\bildlizenz { Star graphs.svg } {} {Koko 90} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Ein
\definitionsverweis {Graph}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {bipartit}{,}
wenn es eine disjunkte Zerlegung
\mavergleichskettedisp
{\vergleichskette
{V
}
{ =} {A \uplus B
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
derart gibt, dass es nur Kanten zwischen
\mathkor {} {A} {und} {B} {}
gibt.
}
Die Zerlegung
\mavergleichskettedisp
{\vergleichskette
{V
}
{ =} {A \uplus B
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
nennt man dann auch eine bipartite Unterteilung. Bei einem bipartiten Graphen gibt es im Allgemeinen mehrere Möglichkeiten für eine solche Zerlegung, man denke etwa an eine disjunkte Vereinigung von einzelnen Kanten. Wenn aber der Graph zusammenhängend ist, so ist die bipartite Unterteilung eindeutig bestimmt, siehe
Aufgabe 20.1.
\inputbeispiel{}
{
Bei einem Fußballspiel möchte man wissen, wer gegen wen im Verlauf des Spieles einen Zweikampf geführt hat, und dies durch einen \definitionsverweis {Graphen}{}{} darstellen. Da man innerhalb seiner Mannschaft keinen Zweikampf führt, ergibt sich ein \definitionsverweis {bipartiter Graph}{}{,} es ergeben sich nur Kanten zwischen den Spielern der einen und der anderen Mannschaft.
}
\inputbeispiel{}
{
In einer heteronormativen Welt besteht die erwachsene Menschheit aus Männern und Frauen und nur diese haben miteinander Sex. Deshalb ergibt die Frage, wer mit wem schon einmal Sex hatte, einen \definitionsverweis {bipartiten Graphen}{}{.}
}
\inputbeispiel{}
{
In Vorbereitung auf einen Schulaustausch zwischen einer Klasse in Osnabrück und einer Klasse in Málaga werden Brieffreundschaften geschnürt, wobei man mehrere Brieffreunde haben kann, aber nur mit Leuten aus der anderen Stadt. Mit den beiden Klassen
\mathkor {} {A} {und} {B} {}
ergibt sich ein
\definitionsverweis {bipartiter Graph}{}{}
auf
\mavergleichskette
{\vergleichskette
{V
}
{ = }{A \uplus B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
bei dem eine Person aus $A$ mit einer Person aus $B$ verbunden wird, wenn eine Brieffreundschaft zwischen ihnen besteht.
}
\inputbeispiel{}
{
Es seien
\mathkor {} {A} {und} {B} {}
disjunkte Mengen und sei $R$ eine
\definitionsverweis {Relation}{}{}
zwischen
\mathkor {} {A} {und} {B} {.}
Dann erhält man auf
\mavergleichskettedisp
{\vergleichskette
{V
}
{ \defeq} { A \uplus B
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
einen
\definitionsverweis {bipartiten Graphen}{}{,}
indem man
\mathl{\{a,b\}}{} als Kante erklärt, falls
\mavergleichskette
{\vergleichskette
{(a,b)
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt. Dadurch entsteht auf $V$ eine symmetrische Relation allein dadurch, dass $A$ und $B$ feste Rollen in der Relation $R$ haben. Dies muss man sich klar machen, um vor Missverständnissen geschützt zu sein. Wenn beispielsweise $A$ eine Menge von Männern und $B$ eine Menge von Frauen ist und
\mavergleichskette
{\vergleichskette
{(a,b)
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bedeutet, dass $a$ Person $b$ nett findet, so bedeutet die Kante
\mathl{\{a,b\}}{} genau dies, dass $a$ die Person $b$ nett findet, nicht, dass sie sich gegenseitig nett finden. Dies gilt auch, wenn man die Kante als $\{b,a\}$ schreibt.
}
\inputbeispiel{}
{
Der Würfelgraph aus
Beispiel 15.11
ist
\definitionsverweis {bipartit}{}{,}
eine Einteilung erhält man, indem man $A$ als die Menge der $d$-Tupel
\mathl{(\pm , \ldots , \pm)}{} mit einer geraden Anzahl an $+$ und $B$ als die Menge der $d$-Tupel mit einer ungeraden Anzahl an $+$ ansetzt.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Graph K3-3.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Graph K3-3.svg } {} {w:cs:User:-xfi-} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Der
\definitionswort {vollständige bipartite Graph}{}
$K_{m,n}$ ist derjenige
\definitionsverweis {Graph}{}{,}
dessen Knotenmenge aus der disjunkten Vereinigung einer $m$-elementigen Menge $A$ und einer $n$-elementigen Menge $B$ besteht und dessen Kantenmenge durch
\mavergleichskettedisp
{\vergleichskette
{E
}
{ =} { { \left\{ \{a,b\} \mid a \in A , \, b \in B \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben ist.
}
\inputfaktbeweis
{Ungerichteter Graph/Bipartit/Gerade Kreise/Fakt}
{Satz}
{}
{
\faktsituation {Ein
\definitionsverweis {Graph}{}{}}
\faktfolgerung {ist genau dann
\definitionsverweis {bipartit}{}{,}
wenn jeder
\definitionsverweis {Kreis}{}{}
in ihm geradzahlig ist.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei
\mavergleichskette
{\vergleichskette
{V
}
{ = }{ A \uplus B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine bipartite Zerlegung eines bipartiten Graphen. In jedem
\definitionsverweis {Weg}{}{}
in einem bipartiten Graphen gehören die Knoten abwechselnd zu $A$ oder zu $B$. Die Existenz eines Kreises mit ungerader Anzahl führt daher direkt zu einem Widerspruch.
Es sei nun umgekehrt die Kreisbedingung erfüllt. Wir können annehmen, dass $G$
\definitionsverweis {zusammenhängend}{}{}
ist. Es sei
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein fixierter Punkt. Wir definieren
\mavergleichskettedisp
{\vergleichskette
{A
}
{ =} { { \left\{ x \in V \mid \text{ es gibt einen geradzahligen Weg von } v \text{ nach } x \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{B
}
{ =} { { \left\{ x \in V \mid \text{ es gibt einen ungeradzahligen Weg von } v \text{ nach } x \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wegen der Zusammenhangseigenschaft ist
\mavergleichskettedisp
{\vergleichskette
{V
}
{ =} { A \cup B
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Nehmen wir an, dass
\mathkor {} {A} {und} {B} {}
nicht disjunkt sind, sagen wir
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{ A \cap B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es gibt dann Wege
\mavergleichskettedisp
{\vergleichskette
{v
}
{ =} {v_0
}
{ \sim} {v_1
}
{ \sim \ldots \sim} { v_r
}
{ =} {y
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{v
}
{ =} {v_0
}
{ \sim} {u_1
}
{ \sim \ldots \sim} { u_s
}
{ =} {y
}
}
{}{}{}
mit $r$ gerade und $s$ ungerade. Indem man die beiden Wege zusammensetzt, erhält man einen Zyklus mit ungerade vielen Knoten. Wenn es in ihm Wiederholungen gibt, so kann man daraus zwei kleinere Zyklen herausarbeiten, von denen einer ebenfalls eine ungerade Anzahl besitzt. Somit erhält man auch einen ungeraden Kreis im Widerspruch zur Voraussetzung. Die beiden Mengen sind also disjunkt. Wenn es eine Kante innerhalb von $A$ geben würde, so würden die daran beteiligten Punkte sofort auch zu $B$ gehören im Widerspruch zur gezeigten Disjunktheit.
Insbesondere ist jeder Baum und jeder Wald bipartit.
\zwischenueberschrift{Paarungen}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Toepfe_fcm.jpg} }
\end{center}
\bildtext {Die Töpfe und die Deckel in einem Haushalt bildet einen bipartiten Graphen, wobei ein Topf und ein Deckel durch eine Kante verbunden werden, wenn sie zueinander passen. Für das große Kochen muss man jetzt noch eine Paarung vornehmen, so dass möglichst viele Töpfe mit Deckel entstehen.} }
\bildlizenz { Toepfe_fcm.jpg } {Frank C. Müller} {Victor Korniyenko} {Commons} {CC-by-sa 2.5} {}
\inputbeispiel{}
{
Es steht nun in Anschluss an Beispiel 20.4 der Schüleraustausch zwischen der Klasse $A$ aus Osnabrück und der Klasse $B$ aus Málaga an. Dabei besuchen die Kinder aus Osnabrück zuerst Málaga und jedes Kind soll bei einem Kind unterkommen, mit dem es bereits durch eine Brieffreundschaft verbunden ist. Es soll also innerhalb des vorgegebenen Brieffreundschaftsgraphen eine Paarung vorgenommen werden. Naheliegende Fragen sind: Wann ist das möglich? Auf wie viele Arten ist es möglich? Wie findet man eine solche Paarung?
}
\inputdefinition
{}
{
Eine
\definitionswort {Paarung}{}
in einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist eine Kantenmenge
\mavergleichskette
{\vergleichskette
{P
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei die Kanten aus $P$ zueinander disjunkt sind.
}
Mit disjunkt meint man hier natürlich knotendisjunkt, bei einer Paarung ist jeder Punkt höchstens zu einer Kante der Paarung inzident. In einer Skizze eines Graphen kann man eine Paarung dadurch kenntlich machen, dass man die beteiligten Kanten dicker
\zusatzklammer {oder bunt} {} {}
malt. Statt Paarung sagt man auch \stichwort {Matching} {} oder man spricht von einer Menge von unabhängigen Kanten.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Blossom Counter.svg} }
\end{center}
\bildtext {Eine maximale Paarung, aber keine optimale Paarung.} }
\bildlizenz { Blossom Counter.svg } {} {0g1o2i3k4e5n6} {Commons} {gemeinfrei} {}
\inputdefinition
{}
{
Wir sagen, dass eine
\definitionsverweis {Paarung}{}{}
$P$ in einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen Knotenpunkt
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionswort {abdeckt}{,}
wenn es eine Kante aus $P$ gibt, zu der $v$ gehört.
}
\inputdefinition
{}
{
Eine
\definitionsverweis {Paarung}{}{}
\mavergleichskette
{\vergleichskette
{P
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in einem
\definitionsverweis {Graphen}{}{}
$G$ heißt
\definitionswort {Paarung für}{}
eine Teilmenge
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wenn jeder Knoten aus $S$ von einer Kante aus $P$
\definitionsverweis {abgedeckt}{}{}
wird.
}
\inputdefinition
{}
{
Eine
\definitionsverweis {Paarung}{}{}
\mavergleichskette
{\vergleichskette
{P
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in einem
\definitionsverweis {Graphen}{}{}
$G$ heißt
\definitionswort {perfekt}{,}
wenn die Kanten der Paarung jeden Knoten des Graphen
\definitionsverweis {abdecken}{}{.}
} Eine perfekte Paarung ist somit eine Paarung für die gesamte Knotenmenge.
\inputbeispiel{}
{
Im vollständigen bipartiten Graphen
\mathl{K_{s,s}}{} gibt es eine Vielzahl an
\definitionsverweis {perfekten Paarungen}{}{.}
Man muss einfach nur für jeden Knoten der einen Teilmenge der Partition nacheinander mit einem Knoten der anderen Teilmenge verbinden.
}
Eine perfekte Paarung gibt es im Allgemeinen nicht, deshalb betrachtet man auch die folgenden Konzepte.
\inputdefinition
{}
{
Eine
\definitionsverweis {Paarung}{}{}
\mavergleichskette
{\vergleichskette
{P
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in einem
\definitionsverweis {Graphen}{}{}
heißt
\definitionswort {maximal}{,}
wenn jedes $P'$ mit
\mavergleichskette
{\vergleichskette
{P
}
{ \subset }{P'
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
}
{}{}{}
keine Paarung ist.
}
\inputdefinition
{}
{
Eine
\definitionsverweis {Paarung}{}{}
\mavergleichskette
{\vergleichskette
{P
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in einem
\definitionsverweis {Graphen}{}{}
$G$ heißt
\definitionswort {optimal}{,}
wenn sie unter allen Paarungen von $G$ die größtmögliche Anzahl von Kanten enthält.
}
Man beachte, dass hier der Sprachgebrauch nicht einheitlich ist. Wir verwenden maximal ordnungstheoretisch, wobei wir Kantenmengen und insbesondere Paarungen über die Inklusion miteinander vergleichen. Eine maximale Paarung liegt also genau dann vor, wenn jede Hinzunahme einer weiteren Kante die Disjunktheit der Kanten zerstört. Es kann aber durchaus \anfuehrung{völlig}{} andere Paarungen geben, die mehr Kanten als eine vorliegende maximale Paarung enthalten. Optimal bezieht sich hingegen auf die Anzahl der beteiligten Kanten.
\inputdefinition
{}
{
Die
\definitionswort {Paarungszahl}{}
eines
\definitionsverweis {bipartiten Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{A \uplus B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist die größtmögliche Anzahl von Kanten in einer
\definitionsverweis {Paarung}{}{}
von $G$.
}
Es geht also um die Anzahl der Kanten in einer optimalen Paarung.
\zwischenueberschrift{Paarungen in bipartiten Graphen}
Der folgenden Satz heißt \stichwort {Paarungssatz} {} oder \stichwort {Heiratssatz} {.} Wir formulieren ihn zuerst als eine numerische Bedingung für die Existenz einer injektiven Abbildung, später folgen graphentheoretische Interpretationen.
\inputfaktbeweis
{Endliche Menge/Numerische Bedingung/Injektive Abbildung/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $M$ eine Menge, es sei $I$ eine endliche Indexmenge und zu jedem
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sei eine Teilmenge
\mavergleichskette
{\vergleichskette
{M_i
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben. Zu einer Teilmenge
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
setzen wir
\mavergleichskettedisp
{\vergleichskette
{M_J
}
{ =} { \bigcup_{j \in J} M_j
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktvoraussetzung {Für jede Teilmenge
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{} gelte
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( M_J \right) }
}
{ \geq} { { \# \left( J \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktfolgerung {Dann gibt es eine
\definitionsverweis {injektive Abbildung}{}{}
\maabbdisp {f} {I} {M
} {}
mit
\mavergleichskette
{\vergleichskette
{f(i)
}
{ \in }{M_i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir führen Induktion über die Anzahl von $I$, bei
\mavergleichskette
{\vergleichskette
{ I
}
{ = }{ \{ i \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist nach Voraussetzung
\mavergleichskette
{\vergleichskette
{M_i
}
{ \neq }{ \emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und man kann ein beliebiges Element aus $M_i$ als Wert an der Stelle $i$ festlegen.
Es sei nun $I$ $n$-elementig und sei die Aussage für jede kleinere Indexmenge
\zusatzklammer {und jede Mengenfamilie, die die numerische Bedingung erfüllt} {} {}
bewiesen. Wir betrachten zwei Fälle. Erster Fall. Für alle Teilmengen
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{J
}
{ \neq }{ \emptyset, I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
gelte sogar die stärkere Bedingung
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( M_J \right) }
}
{ \geq} { { \# \left( J \right) } +1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir wählen ein Element
\mavergleichskette
{\vergleichskette
{i_0
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{m_0
}
{ \in }{ M_{i_0}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und betrachten
\mavergleichskette
{\vergleichskette
{I'
}
{ \defeq }{ I \setminus \{i_0\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{M'
}
{ = }{M \setminus \{ m_0 \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{M_i'
}
{ = }{ M_i \setminus \{ m_0 \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Da stets nur das Element $m_0$ herausgenommen wird, gilt die numerische Bedingung für diese neue Situation und wir können darauf die Induktionsvoraussetzung anwenden. Es gibt also eine injektive Abbildung
\maabbdisp {g} {I'} {M'
} {}
mit
\mavergleichskette
{\vergleichskette
{g(i)
}
{ \in }{M_i'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Diese Abbildung können wir durch
\mathl{i_0 \mapsto m_0}{} zu einer injektiven Abbildung von $I$ nach $M$ fortsetzen. Zweiter Fall. Es gibt nun eine echte Teilmenge
\mavergleichskette
{\vergleichskette
{ \emptyset
}
{ \subset }{J
}
{ \subset }{I
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( J \right) }
}
{ =} { { \# \left( M_J \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Für $J$ gilt die numerische Bedingung nach wie vor. Wir betrachten
\mavergleichskettedisp
{\vergleichskette
{K
}
{ \defeq} {I \setminus J
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{N
}
{ \defeq} { M \setminus M_J
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und setzen
\mavergleichskettedisp
{\vergleichskette
{N_k
}
{ \defeq} { M_k \cap N
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{K
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Für jede Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{K
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \bigcup_{ k \in T \cup J} M_k
}
{ =} { { \left( { \left( \bigcup_{ k \in T} M_k \right) } \setminus { \left( \bigcup_{ k \in J} M_k \right) } \right) } \cup { \left( \bigcup_{ k \in J } M_k \right) }
}
{ =} { { \left( \bigcup_{ k \in T } N_k \right) } \uplus { \left( \bigcup_{ k \in J} M_k \right) }
}
{ =} { { \left( \bigcup_{ k \in T } N_k \right) } \uplus M_J
}
{ } {
}
}
{}
{}{.}
Nach Voraussetzung hat diese Menge zumindest
\mathl{{ \# \left( T \right) } + { \# \left( J \right) }}{} Elemente und $M_J$ hat genau ${ \# \left( J \right) }$ Elemente. Deshalb besitzt
\mathl{\bigcup_{ k \in T } N_k}{} zumindest ${ \# \left( T \right) }$ Elemente. D.h. dass $K$ und die
\mathbed {N_k} {}
{k \in K} {}
{} {} {} {,}
ebenfalls die numerische Bedingung erfüllen. Wir können die Induktionsvoraussetzung auf $J$ einerseits und auf $K$ andererseits
\zusatzklammer {mit den zugehörigen Zielmengen} {} {}
anwenden und erhalten injektive Abbildungen
\maabbdisp {g} {J} {M_J
} {}
mit
\mavergleichskette
{\vergleichskette
{g(j)
}
{ \in }{M_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\maabbdisp {h} {K } {N
} {}
mit
\mavergleichskette
{\vergleichskette
{h(k)
}
{ \in }{ N_k
}
{ \subseteq }{M_k
}
{ }{
}
{ }{
}
}
{}{}{.}
Da
\mathkor {} {M_J} {und} {N} {}
disjunkt sind, setzen sich diese beiden Abbildungen zu einer injektiven Abbildung
\maabb {f} {I} {M
} {}
mit
\mavergleichskette
{\vergleichskette
{ f(i)
}
{ \in }{M_i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zusammen.
\inputdefinition
{}
{
Es sei $G$ ein
\definitionsverweis {bipartiter Graph}{}{}
mit einer Bipartition
\mavergleichskette
{\vergleichskette
{V
}
{ = }{A \uplus B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und sei
\mavergleichskette
{\vergleichskette
{C
}
{ \subseteq }{A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Man sagt, dass $C$ die
\definitionswort {Paarungsbedingung}{}
erfüllt, wenn für jede Teilmenge
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{C
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Beziehung
\mavergleichskette
{\vergleichskette
{ { \# \left( S \right) }
}
{ \leq }{ { \# \left( N(S) \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
Statt Paarungsbedingung sagt man auch \stichwort {Heiratsbedingung} {.} Man beachte, dass die Paarungsbedingung eine Ansammlung von rein numerischen Bedingungen ist. Besonders wichtig ist der Fall
\mavergleichskette
{\vergleichskette
{C
}
{ = }{A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\inputfaktbeweis
{Bipartiter Graph/Zerlegung/Numerische Paarungsbedingung/Fakt}
{Satz}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {bipartiter Graph}{}{}
mit einer bipartiten Zerlegung
\mavergleichskette
{\vergleichskette
{V
}
{ = }{A \uplus B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktuebergang {Dann sind die folgenden Eigenschaften äquivalent.}
\faktfolgerung {\aufzaehlungvier{$G$ enthält eine
\definitionsverweis {Paarung}{}{}
für $A$.
}{Die
\definitionsverweis {Paarungszahl}{}{}
von $G$ ist gleich
\mathl{{ \# \left( A \right) }}{.}
}{Es gilt die
\definitionsverweis {Paarungsbedingung}{}{}
für $A$, d.h. zu jeder Teilmenge
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{ { \# \left( S \right) }
}
{ \leq }{ { \# \left( N(S) \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Es gibt eine injektive Abbildung
\maabbdisp {\varphi} {A} {B
} {}
mit
\mavergleichskette
{\vergleichskette
{(a, \varphi(a))
}
{ \in }{ E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
Von (1) nach (2). Da es eine Paarung für $A$ gibt, ist die Paarungszahl zumindest ${ \# \left( A \right) }$. Größer kann die Paarungszahl aber auch nicht sein, da ja jede Paarung Bezug auf die beiden Teile
\mathkor {} {A} {und} {B} {}
nimmt. Von (2) nach (1) ist klar. Da man aus einer Paarung für $A$ eine injektive Abbildung von $A$ nach $B$ mit der beschriebenen Kantenbedingung und aus einer solchen Abbildung umgekehrt direkt eine Paarung machen kann, sind (1) und (4) äquivalent. Von (3) nach (4) folgt direkt aus
Satz 20.18,
wenn man
\mavergleichskette
{\vergleichskette
{N(S)
}
{ = }{ \bigcup_{s \in S} N(s)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
berücksichtigt. Von (4) nach (3) ist trivial.