Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon: Erläuterung zu

Zusammenhang zwischen zweikantengefärbeten Graphen und den Teilmengen von endlichen Mengen

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Die Menge $ K \subseteq \{1,\dots, n\}$ wird bijektiv auf einen Teilgraphen des folgenden zweikantengefärbten Graphen $ G(n)$ abgebildet.

\includegraphics{zweikanten_graph1}

Das Bild von $ K$ in $ G(n)$ wird folgendermaßen konstruiert:
Man durchläuft den Graphen $ G(n)$ von unten nach oben bis zur Ebene $ n$. Beim Schritt von der Ebene $ i-1$ zur Ebene $ i$ wählt man eine blaue Kante, falls $ i \in K$ gilt, anderenfalls eine rote. Auf diese Weise erhält man z.B. für $ n=3$ und $ K = \{1,3\}$ in $ G(3)$ den Weg:

\includegraphics{zweikanten_graph2}

Mit Hilfe dieser Abbildung lässt sich zeigen:

Die Anzahl der $ k$-elementigen Teilmenge einer Menge mit $ n$ Elementen ist

$\displaystyle \displaystyle \binom{n}{k}\,.$

Bei einer $ n$-elementigen Menge kann man ohne Einschränkung von der Menge $ \{1, \ldots,n\}$ ausgehen. Die oben definierte Abbildung von $ K$ nach $ G$ zeigt, dass die Anzahl der $ k$-elementigen Teilmengen $ \{1, \ldots,n\}$ die gleiche ist, wie die Anzahl der Wege in $ G$ bis zur Ebene $ n$ mit $ k$ blauen Kanten. Man beweist also:
Die Anzahl der Wege in $ G$ bis Ebene $ n$ die genau $ k$ blaue Kanten besitzen ist $ \binom{n}{k}$. Den Beweis führt man mit Induktion nach $ n$ für ein festes $ k$.

Induktionsanfang: Die Aussage macht nur für $ n\geq k$ Sinn. Sei also $ n=k$. Es gilt $ \binom{n}{n}=1$ und es gibt genau einen Weg bis zur Ebene $ n$, der $ k=n$ blaue Kanten besitzt.

Induktionsvoraussetzung: Bis zur Ebene $ n$ gibt es $ \binom{n}{k}$ Wege die genau $ k$ blaue Kanten besitzen.

Induktionsschritt: Wir suchen die Wege bis zur Ebene $ n+1$ von $ G(n+1)$, die genau $ k$ blaue Kanten enthalten. Dazu betrachtet man in $ G$ die beiden Bereiche $ A$ und $ B$

\includegraphics{zweikanten_graph3}

Die Teile des Graphen $ G(n+1)$ die in $ A$, bzw. $ B$ liegen, entsprechen jeweils dem Graphen $ G(n)$. Ein Weg in $ G(n+1)$ verläuft nun stets entweder durch $ A$ oder durch $ B$.

Bei jedem Weg mit $ k$ blauen Kanten von $ G(n+1)$ der teilweise durch $ A$ verläuft müssen alle $ k$ blauen Kanten bereits in $ A$ liegen, denn zwischen den Ebenen 0 und $ 1$ von $ G(n+1)$ wird der Weg durch eine rote Kante vervollständigt. Nach Induktionsvoraussetzung gibt es in $ A$ genau $ \binom{n}{k}$ Wege mit $ k$ blauen Kanten.

Bei jedem Weg der teilweise durch $ B$ verläuft müssen $ k-1$ blaue Kanten in $ B$ liegen, denn zwischen den Ebenen 0 und $ 1$ von $ G(n+1)$ wird der Weg durch eine blaue Kante vervollständigt. Nach Induktionsvoraussetzung gibt es in $ B$ genau $ \binom{n}{k-1}$ Wege mit $ k-1$ blauen Kanten.

Die Anzahl der Wege in $ G(n+1)$ mit $ k$ blauen Kanten ist also

$\displaystyle \binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k} \,, $

und die Aussage ist bewiesen.
(Aus: Vorkurs Mathematik)
[Zurück zur Aussage]
  automatisch erstellt am 26.  2. 2007