Potenz einer Adjazenzmatrix ist die Anzahl der Wege eines Graphen?

14.06.2005, 13:30	Asgaroth	Auf diesen Beitrag antworten »
Potenz einer Adjazenzmatrix ist die Anzahl der Wege eines Graphen? Nochmal ne Frage ich dachte ich würde es selber hinbekommen aber irgendwie haben alle meine Ideen dazu nicht funktioniert. 3. Sei $\begin{eqnarray} A=(a_{ij})^n_{i,j=1} \end{eqnarray}$ die Adjazenzmatrix eines Graphen G mit n Ecken, d.h., wir stellen uns die Ecken von 1 bis n durchnumeriert vor und setzen $\begin{eqnarray} a_{ij}=1 \end{eqnarray}$ , falls die Ecken $\begin{eqnarray} i \end{eqnarray}$ und $\begin{eqnarray} j \end{eqnarray}$ durch eine Kante verbunden sind und $\begin{eqnarray} a_{ij} = 0 \end{eqnarray}$ sonst. Für $\begin{eqnarray} r\in \mathbb N \end{eqnarray}$ betrachten wir nun die r-te Potenz $\begin{eqnarray} A^r \end{eqnarray}$ von A. ( $\begin{eqnarray} A^0 \end{eqnarray}$ ist die Einheitsmatrix!). Wir schreiben $\begin{eqnarray} A^r =(a^{(r)}_{ij})^n_{i,j=1} \end{eqnarray}$ ). Zeige: $\begin{eqnarray} a^{(r)}_{ij} \end{eqnarray}$ ist die Anzahl der Wege (d.h. Kanten dürfen mehrmals durchlaufen werden) von Ecke $\begin{eqnarray} i \end{eqnarray}$ zu Ecke $\begin{eqnarray} j \end{eqnarray}$ der Länge $\begin{eqnarray} r \end{eqnarray}$ .) Ich dachte es würde reichen wenn man es für $\begin{eqnarray} AA=A² \end{eqnarray*}$ zeigt und danach dann zeigt das alle weiteren Potenzen das vielfache der Wege bedeutet d.h. Kanten werden dann statt einmal zweimal durchlaufen etc. aber irgendwie ging das nicht so ganz ! Mit freundlichen Grüßen Asgaroth
18.10.2008, 22:18	as	Auf diesen Beitrag antworten »
Hallo Asgaroth, versuch's mal mittels vollständiger Induktion über $\begin{eqnarray} r \end{eqnarray}$ .
19.04.2022, 14:56	HiBee123	Auf diesen Beitrag antworten »
Hallöchen Ich habe das gleiche Problem. Für 2x2Matrizen ist mir ungefähr klar was abgeht... aber wie kann ich das erweitern? Das es irgendwie mit Induktion geht scheint mir logisch, aber ich weiß noch nicht wie man praktisch dran geht...
19.04.2022, 15:11	Huggy	Auf diesen Beitrag antworten »
Siehe https://imsc.uni-graz.at/baur/lehre/SS2018/11-Seebacher.pdf Lemma 8.1.2
20.04.2022, 11:27	HiBee123	Auf diesen Beitrag antworten »
ok das hilft schonmal. Nur dass es sich bei meinem Graphen um keinen gerichteten handelt, aber dass dürfte ja egal sein,.. oder?
20.04.2022, 12:16	Huggy	Auf diesen Beitrag antworten »
Ein ungerichteter Graph ist ja nur ein spezieller gerichteter Graph, nämlich einer, bei dem, falls eine Kante vom Knoten $\begin{eqnarray} i \end{eqnarray}$ zum Knoten $\begin{eqnarray} j \end{eqnarray}$ führt, auch eine Kante vom Knoten $\begin{eqnarray} j \end{eqnarray}$ zum Knoten $\begin{eqnarray} i \end{eqnarray}$ führt. Das bedeutet, seine Adjazenzmatrix ist symmetrisch. Der Beweis macht nur von Matrixoperationen Gebrauch, die selbstverständlich auch für symmetrische Matrizen gelten.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »