Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 19/latex
\setcounter{section}{19}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller51.jpg} }
\end{center}
\bildtext {Zuerst war sie kurz etwas beleidigt über ihre unvorteilhaften Startbedingungen.} }
\bildlizenz { Waeller51.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
\zwischenueberschrift{Graphen und Matrizen}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {G1kevohuong.png} }
\end{center}
\bildtext {} }
\bildlizenz { G1kevohuong.png } {} {Nguyễn Huỳnh Ngân Hà} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Zu einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
versteht man unter der
\definitionswort {Adjazenzmatrix}{}
diejenige
$V \times V$-\definitionsverweis {Matrix}{}{,}
deren Einträge durch
\mavergleichskettedisp
{\vergleichskette
{a_{u,v}
}
{ =} { \begin{cases} 1,\, \text{falls } \{u,v\} \in E, \\ 0\, \text{ sonst}, \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben sind.
}
Die Adjazenzmatrix ist eine quadratische Matrix, und zwar eine $V \times V$-Matrix. Es ist sinnvoll, hier Matrizen zu beliebigen endlichen Indexmengen zuzulassen. Wenn man allerdings die Matrix tabellarisch aufschreiben möchte, so muss man die Indexmenge \zusatzklammer {also die Knotenmenge} {} {} mit $1$ bis $n$ durchnummerieren und erhält dann eine $n \times n$-Matrix. Wie bei jeder quadratischen Matrix kann man von der Adjazenzmatrix ihre \definitionsverweis {Determinante}{}{,} ihr \definitionsverweis {charakteristisches Polynom}{}{,} ihre \definitionsverweis {Eigenwerte}{}{} bestimmen, man kann ihre Potenzen ausrechnen, u.s.w., und sich überlegen, was diese Strukturen der linearen Algebra für den Ausgangsgraphen bedeuten.
\inputbeispiel{}
{
Zum
\definitionsverweis {vollständigen Graphen}{}{}
$K_n$ ist die
\definitionsverweis {Adjazenzmatrix}{}{}
gleich
\mathdisp {\begin{pmatrix} 0 & 1 & \ldots & 1 & 1 \\ 1 & 0 & 1 & \ldots & 1 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 1 & \ldots & 1 & 0 & 1 \\ 1 & 1 & \ldots & 1 & 0 \end{pmatrix}} { . }
}
\inputbeispiel{}
{
Zu einem \definitionsverweis {kantenfreien Graphen}{}{} ist die \definitionsverweis {Adjazenzmatrix}{}{} die Nullmatrix.
}
\inputbeispiel{}
{
Zum
\definitionsverweis {vollständigen bipartiten Graphen}{}{}
$K_{r,s}$ ist die
\definitionsverweis {Adjazenzmatrix}{}{}
eine
\definitionsverweis {Blockmatrix}{}{}
der Form
\mathdisp {\begin{pmatrix} 0 & \ldots & 0 & 1 & \ldots & 1 \\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
0 & \ldots & 0& 1 & \ldots & 1 \\
1 & \ldots & 1 & 0 & \ldots & 0 \\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots\\
1 & \ldots & 1 & 0 & \ldots & 0
\end{pmatrix}} { , }
wobei die Blöcke aber nicht quadratisch sein müssen.
}
\inputfaktbeweis
{Adjazenzmatrix/Erste Eigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {Die
\definitionsverweis {Adjazenzmatrix}{}{}
$A$ eines
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}}
\faktuebergang {besitzt die folgenden Eigenschaften.}
\faktfolgerung {\aufzaehlungvier{Für Knotenpunkte
\mavergleichskette
{\vergleichskette
{u,v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{ { e_u^{ \text{tr} } } A e_v
}
{ =} { \begin{cases} 1, \text{wenn } \{u,v \} \in E \, , \\ 0 \text{ sonst} \, .\end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{$A$ ist
\definitionsverweis {symmetrisch}{}{.}
}{Die Diagonaleinträge von $A$ sind $0$.
}{Der
\definitionsverweis {Knotengrad}{}{}
zum Punkt
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist die Summe der Einträge der $v$-ten Zeile
\zusatzklammer {oder Spalte} {} {}
von $A$.
}}
\faktzusatz {}
\faktzusatz {}
}
{
Diese Aussagen folgen alle unmittelbar aus der Definition der Adjazenzmatrix und dem Matrizenkalkül.
In einem Graphen gibt es zwischen zwei Knotenpunkten \mathkor {} {u} {und} {v} {} im Allgemeinen mehrere \definitionsverweis {Wege}{}{} einer vorgegebenen \definitionsverweis {Länge}{}{} $\ell$. Deren Anzahl kann man mit Hilfe der Potenzen der Adjazenzmatrix berechnen.
\inputfaktbeweis
{Adjazenzmatrix/Potenzen/Interpretation/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
mit zugehöriger
\definitionsverweis {Adjazenzmatrix}{}{}
$A$.}
\faktfolgerung {Dann ist die Anzahl der
\definitionsverweis {Wege}{}{}
von
\mathkor {} {u} {nach} {v} {}
der
\definitionsverweis {Länge}{}{}
$\ell$ gleich dem Eintrag an der Stelle
\mathl{(u,v)}{} zur
\definitionsverweis {Matrixpotenz}{}{}
$A^\ell$.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir beweisen die Aussage durch Induktion über $\ell$, wobei der Induktionsanfang für
\mavergleichskette
{\vergleichskette
{\ell
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
unmittelbar aus der Definition der Adjazenzmatrix folgt, da ja die Kanten die einzigen Wege der Länge $1$ sind
\zusatzklammer {bei
\mavergleichskettek
{\vergleichskettek
{\ell
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stimmt die Aussage ebenfalls, da es nur die konstanten kantenleeren Wege der Länge $0$ gibt und die $0$-te Potenz der Matrix als Einheitsmatrix zu interpretieren ist} {} {.}
Ein Weg der Länge $\ell +1$ von $u$ nach $v$ startet mit einer Kante
\mathl{\{u,w\}}{} gefolgt von einem Weg von $w$ nach $v$ der Länge $\ell$. Es gilt also unter Verwendung der Induktionsvoraussetzung
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ { \# \left( \text{ Weg von } u \text{ nach } v \text{ der Länge } \ell +1 \} \right) }
}
{ =} { \sum_{ \{ u, w\} \in E } { \# \left( \text{ Weg von } w \text{ nach } v \text{ der Länge } \ell \} \right) }
}
{ =} { \sum_{ \{ u, w\} \in E } { \left( A^\ell \right) }_{ (w,v)}
}
{ =} { \sum_{w \in V} A_{( u, w)} { \left( A^\ell \right) }_{ (w,v)}
}
{ =} { { \left( A \cdot A^\ell \right) }_{ (u,v)}
}
}
{
\vergleichskettefortsetzungalign
{ =} { { \left( A^{\ell+1} \right) }_{ (u,v)}
}
{ } {}
{ } {}
{ } {}
}
{}{}
Es gibt auch naheliegende Varianten für Adjazenzmatrizen einschließlich der vorstehenden Aussage für gerichtete Graphen und für Multigraphen.
\inputbeispiel{}
{
Wir betrachten den
\definitionsverweis {Rundgang}{}{}
zur Vertexmenge
\mathl{a,b,c,d,e}{} in dieser Reihenfolge. Die
\definitionsverweis {Adjazenzmatrix}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{A
}
{ =} { \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Wege der Länge $2$ kann man direkt so bestimmen: Es gibt zwei Wege von jedem Punkt zu sich selbst, nämlich zu den beiden Nachbarn und dann zurück. Zum Nachbarn gibt es keinen Weg der Länge $2$, zum übernächsten Punkt gibt es jeweils einen Weg der Länge $2$. Entsprechend ist
\mavergleichskettealign
{\vergleichskettealign
{A^2
}
{ =} { \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}
}
{ =} { \begin{pmatrix} 2 & 0 & 1 & 1 & 0 \\ 0 & 2 & 0 & 1 & 1 \\ 1 & 0 & 2 & 0 & 1 \\ 1 & 1 & 0 & 2 & 0 \\ 0 & 1 & 1 & 0 & 2 \end{pmatrix}
}
{ } {
}
{ } {
}
}
{}
{}{.}
Ab der Länge $3$ muss man bei der kombinatorischen Abzählung berücksichtigen, dass Wege mit unterschiedlichem Umlaufsinn sich überlagern und das gleiche Ergebnis haben können. Mit der Matrixregel aus
Lemma 19.6
muss man einfach nur multiplizieren, es ist
\mavergleichskettealign
{\vergleichskettealign
{A^3
}
{ =} { \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} 2 & 0 & 1 & 1 & 0 \\ 0 & 2 & 0 & 1 & 1 \\ 1 & 0 & 2 & 0 & 1 \\ 1 & 1 & 0 & 2 & 0 \\ 0 & 1 & 1 & 0 & 2 \end{pmatrix}
}
{ =} { \begin{pmatrix} 0 & 3 & 1 & 1 & 3 \\ 3 & 0 & 3 & 1 & 1 \\ 1 & 3 & 0 & 3 & 1 \\ 1 & 1 & 3 & 0 & 3 \\ 3 & 1 & 1 & 3 & 0 \end{pmatrix}
}
{ } {
}
{ } {
}
}
{}
{}{.}
}
\zwischenueberschrift{Das charakteristische Polynom zu einem Graphen}
\inputdefinition
{}
{
Zu einem \definitionsverweis {Graphen}{}{} nennt man das \definitionsverweis {charakteristische Polynom}{}{} der \definitionsverweis {Adjazenzmatrix}{}{} das \definitionswort {charakteristische Polynom}{} von $G$.
}
Entsprechende nennt man die Eigenwerte \zusatzklammer {Eigenvektoren, Eigenräume u.s.w.} {} {} der Adjazenzmatrix auch die Eigenwerte des Graphen.
\inputbeispiel{}
{
Das
\definitionsverweis {charakteristische Polynom}{}{}
zur
\definitionsverweis {Adjazenzmatrix}{}{}
des
\definitionsverweis {vollständigen Graphen}{}{}
$K_n$ ist nach Definition die
\definitionsverweis {Determinante}{}{}
von
\mathdisp {\begin{pmatrix} x & -1 & \ldots & -1 & -1 \\ -1 & x & -1 & \ldots & -1 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ -1 & \ldots & -1 & x & -1 \\ -1 & -1 & \ldots & -1 & x \end{pmatrix}} { . }
In diesem Fall ist es einfacher, direkt die
\definitionsverweis {Eigenräume}{}{}
zu berechnen. Für
\mavergleichskette
{\vergleichskette
{x
}
{ = }{-1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
steht hier überall $-1$ und der Kern besitzt die
\definitionsverweis {Basis}{}{}
\mathdisp {\begin{pmatrix} 1 \\-1\\ 0\\ \vdots\\ 0\\ 0 \end{pmatrix} , \, \begin{pmatrix} 0 \\1\\ -1\\ \vdots\\ 0\\ 0 \end{pmatrix} , \ldots , \begin{pmatrix} 0 \\0\\ 0\\ \vdots\\ 1\\ -1 \end{pmatrix}} { . }
Somit ist $-1$ ein Eigenwert mit
\definitionsverweis {geometrischer Vielfachheit}{}{}
$n-1$. Für
\mavergleichskette
{\vergleichskette
{x
}
{ = }{n-1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ergibt sich die Matrix
\mathdisp {\begin{pmatrix} n-1 & -1 & \ldots & -1 & -1 \\ -1 & n-1 & -1 & \ldots & -1 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ -1 & \ldots & -1 & n-1 & -1 \\ -1 & -1 & \ldots & -1 & n-1 \end{pmatrix}} { }
und der Kern davon ist
\mathdisp {\R \begin{pmatrix} 1 \\1\\ \vdots\\1\\ 1 \end{pmatrix}} { . }
Somit ist $n-1$ ein Eigenwert mit geometrischer Vielfachheit $1$. Da die Summe der geometrischen Vielfachheiten bereits die Dimension $n$ ist, handelt es sich jeweils auch um die
\definitionsverweis {algebraischen Vielfachheiten}{}{}
und das charakteristische Polynom ist
\mathdisp {(x+1)^{n-1} (x-n+1)} { . }
}
\inputbemerkung
{}
{
Für einen
\definitionsverweis {Graphen}{}{}
liegt folgende Interpretation nahe: Ein Knotenpunkt ist der mögliche Aufenthaltsort eines Gerüchtes, einer Information, eines Virus. Wenn eine Kante zwischen zwei Punkten
\mathkor {} {u} {und} {v} {}
besteht, so bedeutet dies, dass in einem bestimmten Zeitabschnitt das Gerücht von $u$ nach $v$ hinüber- oder zurückwechselt. Die Gesamtverteilung des Gerüchtes ist ein Spaltenvektor
\mathdisp {{ \left( c_v \right) }_{ v \in V}} { }
der für jeden Punkt angibt, wie stark im Ort $v$ das Gerücht verbreitet ist. Der Gesamtübergang in dem erwähnten Zeitintervall wird dann durch Multiplikation der
\definitionsverweis {Adjazenzmatrix}{}{}
$A$ mit der Gesamtverteilung beschrieben. Wenn beispielsweise zu Beginn das Gerücht nur in einem Knotenpunkt $u$ mit der Stärke $1$ präsent ist, so ist es nach dem Zeitintervall in den zu $u$ benachbarten Knoten jeweils mit der Stärke $1$ präsent, und dies ist gerade der $u$-te Spaltenvektor der Adjazenzmatrix
\zusatzklammer {da wir ohne Schleifen arbeiten, vergisst man in diesem Modell das Gerücht, indem man es weitererzählt, es liegt eine gedächtnislose Weitergabe vor; man kann die Weitergabe auch abschwächen, wenn man die Adjazenzmatrix mit einem Faktor skaliert} {} {.}
Die Gerüchtverteilung nach $\ell$ Durchläufen zur Anfangsgerüchtverteilung wird dann durch
\mathl{A^\ell ( c_v)}{} beschrieben. Eine Eigenverteilung, also ein
\definitionsverweis {Eigenvektor}{}{}
der Adjazenzmatrix, ist durch die Eigenschaft gekennzeichnet, dass sich bei einem Durchlauf ein bestimmtes Vielfaches dieser Verteilung selbst ergibt. Der gemeinsame Faktor, der an jeder Stelle den Übergang beschreibt, ist der Eigenwert.
}
Im vollständigen Graphen gibt es nach
Beispiel 19.9
die beiden Eigenwerte $n-1$ und $-1$. Die Gerüchtverteilung
\mathl{\begin{pmatrix} 1 \\1\\ \vdots\\1 \end{pmatrix}}{}
\zusatzklammer {an jeder Stelle wird mit der gleichen Intensität $1$ das Gerücht geglaubt} {} {}
wird durch einen Weitergabevorgang in die Gerüchtverteilung
\mathl{\begin{pmatrix} n-1 \\n-1\\ \vdots\\n-1 \end{pmatrix}}{} überführt, jeder hört das Gerücht $n-1$ mal. Die Gerüchtverteilung
\mathl{\begin{pmatrix} 1 \\-1\\ 0\\\vdots\\ 0 \end{pmatrix}}{,} wobei $-1$ so zu verstehen ist, dass das Gerücht an dieser Stelle mit der gleichen Intensität nicht geglaubt wird, wird durch den Vorgang in die Verteilung
\mathl{\begin{pmatrix} -1 \\1\\ 0\\\vdots\\ 0 \end{pmatrix}}{} überführt. Die beiden nichtneutralen Personen übernehmen wechselseitig ihre Einstellung zum Gerücht und alle anderen Personen hören es einmal in positiver und einmal in negativer Weise, was sich aufhebt.
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Unter der
\definitionswort {Inzidenzmatrix}{}
zu $G$ verstehen wir die
$V \times E$-\definitionsverweis {Matrix}{}{,}
deren Einträge durch
\mavergleichskettedisp
{\vergleichskette
{ b_{v,e}
}
{ \defeq} { \begin{cases} 1,\, \text{falls } v \in e, \\ 0 \text{ sonst}\, , \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben sind.
}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Unter der
\definitionswort {Gradmatrix}{}
zu $G$ verstehen wir die
$V \times V$-\definitionsverweis {Diagonalmatrix}{}{,}
deren Diagonaleintrag an der Stelle
\mathl{(v,v)}{} durch den
\definitionsverweis {Grad}{}{}
im Knotenpunkt $v$ gegeben ist.
}
\zwischenueberschrift{Laplace-Matrix und Spannbäume}
Für einen \definitionsverweis {Multigraphen}{}{} definieren wir die Adjazenzmatrix und die Gradmatrix entsprechend wie im einfachen Fall.
\inputdefinition
{}
{
Zu einem
\definitionsverweis {Multigraphen}{}{}
$G$ versteht man unter der
\definitionswort {Laplace-Matrix}{}
$L$ die Differenz
\mavergleichskettedisp
{\vergleichskette
{L
}
{ =} { D-A
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
aus
\definitionsverweis {Gradmatrix}{}{}
$D$ und
\definitionsverweis {Adjazenzmatrix}{}{}
$A$.
}
Mit Hilfe der Laplace-Matrix kann man die Anzahl von Spannbäumen berechnen, wozu wir zuerst ein Beispiel geben.
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Graph with all its spanning trees.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Graph with all its spanning trees.svg } {} {Andreschulz} {Commons} {CC-by-sa 3.0} {}
Wir betrachten den \stichwort {Diamantgraphen} {} mit den Knoten
\mathl{a,b,c,d}{,} bei dem
\mathl{\{1,4\}}{} die einzige Nichtkante ist. Die
\definitionsverweis {Adjazenzmatrix}{}{}
ist
\mavergleichskette
{\vergleichskette
{A
}
{ = }{ \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die
\definitionsverweis {Gradmatrix}{}{}
ist
\mavergleichskette
{\vergleichskette
{ D
}
{ = }{ \begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 2 \end{pmatrix}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die
\definitionsverweis {Laplace-Matrix}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{ L
}
{ =} { \begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 2 \end{pmatrix} - \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}
}
{ =} { \begin{pmatrix} 2 & -1 & -1 & 0 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \end{pmatrix}
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Determinante der Streichungsmatrix zur ersten Zeile und ersten Spalte ist
\mavergleichskettedisp
{\vergleichskette
{ \det \begin{pmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\-1 & -1 & 2 \end{pmatrix}
}
{ =} { 8
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Zahl stimmt mit der Anzahl der Spannbäume des Diamantgraphen, die in
Beispiel 18.13
berechnet wurde, überein.
}
Der folgende Satz heißt \stichwort {Satz von Kirchhoff} {} und formuliert einen direkten Zusammenhang zwischen der Anzahl der Spannbäume und der Determinante von Streichungsmatrizen der Laplace-Matrix.
\inputfaktbeweis
{Ungerichteter Graph/Spannbäume/Kirchhoff/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $G$ ein
\definitionsverweis {Multigraph}{}{}
und sei $L$ die
\definitionsverweis {Laplace-Matrix}{}{}
zu $G$. Es sei $L'$ die
\definitionsverweis {Streichungsmatrix}{}{}
von $L$ bezüglich eines Knotenpunktes.}
\faktfolgerung {Dann ist die Anzahl der
\definitionsverweis {Spannbäume}{}{}
von $G$ gleich der
\definitionsverweis {Determinante}{}{}
von $L'$.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir führen Induktion über die Anzahl der Knoten. Bei einem einzigen Knoten gibt es einen Spannbaum und die Determinante der leeren Matrix ist $1$. Bei zwei Knoten und $m$ verbindenden Kanten gibt es $m$ Spannbäume. Die Adjazenzmatrix ist
\mathl{\begin{pmatrix} 0 & m \\ m & 0 \end{pmatrix}}{} und die Gradmatrix ist
\mathl{\begin{pmatrix} m & 0 \\ 0 & m \end{pmatrix}}{.} Daher ist die Laplace-Matrix gleich
\mathl{\begin{pmatrix} m & -m \\ -m & m \end{pmatrix}}{.} Streicht man die erste Zeile und erste Spalte
\zusatzklammer {oder die zweite Zeile und zweite Spalte} {} {.}
so hat die Streichungsmatrix die Determinante $m$. Es sei nun die Aussage für alle Multigraphen mit höchstens $n-1$ Knoten bewiesen, und sei eine Multigraph $G$ mit $n$ Knoten gegeben. Wir führen nun
\zusatzklammer {eine innere} {} {}
Induktion über die Anzahl $m$ der Kanten. Wenn es gar keine Kante gibt, so gibt es keinen Spannbaum und die Laplace-Matrix und die Streichungsmatrix davon ist die Nullmatrix mit Determinante $0$. Es sei also die Aussage auch für alle Graphen mit $n$ Knoten und mit weniger als $m$ Kanten bewiesen, und $G$ habe $n$ Knoten und $m$ Kanten. Wir überlegen uns, was passiert, wenn man eine Kante herausnimmt bzw. kontrahiert. Ohne Einschränkung werden die Kanten zwischen
\mathkor {} {1} {und} {2} {}
kontrahiert, wovon es
\mavergleichskette
{\vergleichskette
{a_{12}
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt. Die Laplace-Matrix von $G$ sei
\mathdisp {\begin{pmatrix} d_1 & -a_{12} & -a_{13} & \ldots & -a_{1 n} \\ -a_{12} & d_2 & -a_{23} & \ldots & -a_{2 n} \\ -a_{13} & -a_{23} & d_3 & \ldots & -a_{3 n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -a_{1 n} & -a_{2 n} & -a_{3n} & \ldots & d_{ n} \end{pmatrix}} { . }
Die Laplace-Matrix von $G \setminus \{e\}$ ist
\mathdisp {\begin{pmatrix} d_1-1 & -a_{12}+1 & -a_{13} & \ldots & -a_{1 n} \\ -a_{12}+1 & d_2-1 & -a_{23} & \ldots & -a_{2 n} \\ -a_{13} & -a_{23} & d_3 & \ldots & -a_{3 n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -a_{1 n} & -a_{2 n} & - a_{3n} & \ldots & d_{ n} \end{pmatrix}} { }
und die Laplace-Matrix zur Kontraktion $G/e$ ist die
\mathl{(n-1) \times (n-1)}{-}Matrix
\mathdisp {\begin{pmatrix} d_1+d_2-2a_{12 } & -a_{13} - a_{23} & \ldots & -a_{1 n} - a_{2 n} \\ -a_{13} -a_{23} & d_3 & \ldots & -a_{3 n} \\ \vdots & \vdots & \ddots & \vdots \\ -a_{1 n}-a_{2 n} & -a_{3n} & \ldots & d_{ n} \end{pmatrix}} { . }
Die Streichungsmatrizen zur jeweils ersten Zeile und ersten Spalte hiervon sind der Reihe nach
\mathdisp {\begin{pmatrix} d_2 & -a_{23} & \ldots & -a_{2 n} \\ - a_{23} & d_3 & \ldots & -a_{3 n} \\ \vdots & \vdots & \ddots & \vdots \\ -a_{2 n} & -a_{3n} & \ldots & d_{ n} \end{pmatrix}} { , }
\mathdisp {\begin{pmatrix} d_2 -1 & -a_{23} & \ldots & -a_{2 n} \\ -a_{23} & d_3 & \ldots & -a_{3 n} \\ \vdots & \vdots & \ddots & \vdots \\ -a_{2 n} & -a_{3n} & \ldots & d_{ n} \end{pmatrix}} { }
\mathdisp {\begin{pmatrix} d_3 & \ldots & -a_{3 n} \\ \vdots & \ddots & \vdots \\ -a_{3n} & \ldots & d_{ n} \end{pmatrix}} { . }
Entwicklung nach der ersten Spalte
\zusatzklammer {für die beiden ersten Matrizen} {} {}
zeigt, dass die Determinante der ersten Matrix die Summe der Determinanten der beiden folgenden Matrizen ist. Somit folgt die Aussage mit
Lemma 18.12
aus den beiden Induktionsvoraussetzungen.