Potenzen der Adjazenzmatrix < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:56 Fr 07.11.2008 | | Autor: | fin129 |
| Aufgabe | Zu einem Graphen G = (V;E) sei seine Adjazenzmatrix A
gegeben. Hierbei sind die Zeilen und Spalten von A mit den Knoten des Graphen
indiziert. Alle Einträge sind 0 oder 1 und an Position (v;w) in A steht genau dann eine 1, wenn {v;w} [mm] \in [/mm] E ist, also eine Kante ist.
Zeigen Sie, dass für natürliche Zahlen k im Matrizenprodukt [mm] A^k [/mm] der Eintrag an Position (v;w) gleich der Anzahl der Wege der Länge k von v nach w ist. Hierbei ist die Länge eines Weges gleich der Anzahl an Kanten auf diesem Weg. |
Hallo,
ich versuche obige Aufgabenstellung durch vollständige Induktion über k zu beweisen.
Indukitonsanfang k=1
Ist offensichtlich, resultiert aus der Definition einer Adjazenzmatrix,
[mm]a_{v,w}=1 \gdw (v,w)\in E \gdw \exists[/mm] direkte Verbindung von v nach w, deren Länge 1 und das entspricht auch der Anzahl der Wege der Länge k=1 von v nach w.
Induktionsannahme:
für k=n stehen in [mm] A^k [/mm] jeweils die anzahl der wege der länge k=n von beliebigem v nach beliebigem w.
Induktionsschritt:
Hier komme ich nicht so recht weiter, ich habe bis jetzt:
Ist [mm]a_{v,w}\in A^n[/mm] die Anzahl der Wege v nach w, Länge n, so gilt für k=n+1:
#Wege = #Wege, die in n zu erreichen sind und von denen eine direkte Verbindung (=Länge 1) zu (v,w) existiert + #Wege, die in n-1 zu erreichen sind, und von denen aus man (v,w) in Länge 2 erreichen kann + ...
Mir ist soweit klar, dass die #Wege, die in n zu erreichen sind in [mm] A^n [/mm] stehen (Induktionsannahme) und die 1er Wege in A selber (Induktionsanfang), aber ich komme nicht auf die restlichen Glieder der Summe.
Kann mir jemand helfen, oder ist das der falsche Ansatz für diesen Beweis?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 19:37 Sa 08.11.2008 | | Autor: | fin129 |
Ok, ich glaube den Beweis erbracht zu haben, kann mal bitte jemand Korrekturlesen?
Sorry für die Formatierung, ich habe meinen Latex-Quelltext reinkopiert, dürfte zum Großteil aber gehen.
Danke!
Der Graph $G=(V,E)$ sei repr"asentiert durch eine Matrix [mm] $A\subset\{0,1\}^{n\times n}\subset\mathbb{N}^{n\times n}$\\
[/mm]
Sei [mm] \#W(a,b,c) [/mm] die Anzal der Wege von $a$ nach $b$ der L"ange $c$ und $a,b [mm] \in V$\\
[/mm]
[mm] \subsection*{3.1 Behauptung}
[/mm]
Die Anzahl der Wege von $v$ nach $w$ der L"ange $k$ entspricht dem Eintrag in Zeile $v$ und Spalte $w$ der $k$-ten Potenz der Adjazenzmatrix [mm] $A\subset\mathbb{N}^{n\times n}$. [/mm] Zu zeigen:
[mm] $$A^{k}(v,w) [/mm] = [mm] \#W(v,w,k)$$
[/mm]
[mm] \subsection*{3.2 Beweis durch vollst"andige Induktion}
[/mm]
[mm] \subsubsection{3.2.1 Induktionsanfang $k=1$}
[/mm]
Aus der Definition der Adjazenzmatrix [mm] folgt:\\
[/mm]
[mm] \begin{align*}
A(v,w) \Longleftrightarrow (v,w) \in E \Longleftrightarrow \exists\mbox{ direkte Verbindung von } v \text{ nach } w
\end{align*}
[/mm]
Die L"ange dieser Verbindung ist 1, da eine direkte Verbingung genau einer Kante entspricht. Es kann maximal einen m"oglichen Weg von $v$ nach $w$ der L"ange 1 [mm] geben.\\ [/mm] Gibt es keine Verbindung, so ist $A(v,w) = 0$. Folglich entspricht f"ur $k=1$ der Eintrag [mm] $A^k(v,w)$ [/mm] stets der Anzahl aller m"oglichen Wege von $v$ nach $w$ der L"ange [mm] $k$.\\
[/mm]
Es wurde gezeigt: [mm] $A^{1}(v,w) [/mm] = [mm] \#W(v,w,1)$\\
[/mm]
(Behauptung trifft f"ur Induktionsanfang $k=1$ zu)
[mm] \subsubsection{3.2.2 Induktionsannahme}
[/mm]
f"ur $k=i$ gilt: [mm] $A^k(v,w)$ [/mm] ist Anzahl aller Wege der L"ange $k$ von von $v$ nach $w$, [mm] $\forall [/mm] v,w [mm] \in [/mm] (1,n)$
[mm] \subsubsection{3.2.3 Induktionsschritt}
[/mm]
f"ur $k=i+1$ gilt [mm] allgemein:\\
[/mm]
[mm] $$\#W(v,w,i+1) [/mm] = [mm] \#W(j,w,1) \cdot \#W(v,j,i) \mbox{ mit } j=1,\ldots,n$$
[/mm]
D.h. die Anzahl der Wege der L"ange $i+1$ von $v$ nach $w$ ist gleich der Anzahl der Wege der L"ange $i$ von $v$ zu denjenigen Knoten $j$, die direkt mit $w$ verbunden [mm] sind.\\
[/mm]
Wissen, dass die Behauptung f"ur $k=1$ (Induktionsanfang) stimmt, sowie nehmen an, dass sie auch f"ur $k=i$ (Induktionsannahme) stimmt, daraus [mm] folgt:\\
[/mm]
[mm] $$\#W(v,w,i+1) [/mm] = [mm] \sum_{j=1}^{n} \left( A^1(j,w) \cdot A^i(v,j) \right)$$
[/mm]
[mm] $A^1(j,w)$ [/mm] und [mm] $A^i(v,j)$ $\in\mathbb{N}$, [/mm] Multiplikation in [mm] $\mathbb{N}$ [/mm] ist kommutativ:
[mm] $$\#W(v,w,i+1) [/mm] = [mm] \sum_{j=1}^{n} \left( A^i(v,j)\cdot A^1(j,w) \right)$$
[/mm]
Betrachtet man die Summe stellt man fest: Die Summe "uber alle $j$ von 1 bis $n$ der Produkte der $j$-ten Elemente der $w$-ten Spalte von [mm] $A^1$ [/mm] mit den $j$-ten Elementen der $v$-ten Zeile von [mm] $A^i$ [/mm] entspricht dem Eintrag [mm] $A^{i+1}(v,w)$ [/mm] der $(i+1)$-ten Potenz der Adjazenzmatrix [mm] $A$.\\
[/mm]
Folglich gilt:
[mm] $$\#W(v,w,i+1) [/mm] = [mm] A^{i+1}(v,w) \forall [/mm] v,w [mm] \in [/mm] (1,n) $$
Es wurde gezeigt: [mm] $A^{i}(v,w) [/mm] = [mm] \#W(v,w,i) \Longrightarrow A^{i+1}(v,w) [/mm] = [mm] \#W(v,w,i+1)$\\
[/mm]
(Induktionsannahme impliziert [mm] Induktionsschritt)\\
[/mm]
Damit ist die Induktion vollst"andig und der Beweis erbracht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:30 Mo 10.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Di 11.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
