k-faches Matrixprodukt / Adjazenzmatrix
Christoph Hermann
ich habe folgendes problem in einer Informatik Uebung (bin
erstsemester, und ich und meine mitkommilitonen kommen nicht weiter,
alle anderen Aufgaben bekommen wir hin nur hier haben wir (fast)
keinen Ansatz).
Wen es interessiert, das UAfgabenblatt ist hier:
http://www.in.tu-clausthal.de/~abruenin/WS00-01/ps/Info1/HausUeb4-Info
1.ps ) zu finden -> Aufgabe 17)1)
Es sei die folgende k-fache Matrix gegeben, Gerichteter Graph G =
(V,E)
(a11^k a12^k ... a1n^k )
(a21^k . ... a2n^k )
A^k= ( ... )
( ... )
(an1^k .... ann^k)
wobie ^k nicht als potenz sondern als k-faches Matrixprodukt einer
beliebigen Matrix gesehen werden soll.
und folgende Formel, die zur Berechnung einer Stelle der k-fachen
Matrix dient:
n
aij^k = E( ais^(k-1) asj^1 )
s=1
laut mir gibt diese Formel und auch das k-fache Matrix produkt an, wie
oft man mit k schritten (Pfadlänge k) man vom Knoten i zum Knoten j
kommt.
laut meinen Ausprobierereien funktioniert das auch, nur wie kann man
so etwas beweisen ?
auf _Tipps_ hoffend
mfg Christoph
Heiko Röglin
> ich habe folgendes problem in einer Informatik Uebung (bin
> erstsemester, und ich und meine mitkommilitonen kommen nicht weiter,
> alle anderen Aufgaben bekommen wir hin nur hier haben wir (fast)
> keinen Ansatz).
Im ersten Semester macht ihr das. Ist ja interessant, hier in Dortmund kam
das erst im dritten.
> laut mir gibt diese Formel und auch das k-fache Matrix produkt an, wie
> oft man mit k schritten (Pfadlänge k) man vom Knoten i zum Knoten j
> kommt.
> laut meinen Ausprobierereien funktioniert das auch, nur wie kann man
> so etwas beweisen ?
So habe ich die Aufgabe vor ein paar Wochen gelöst:
Behauptung: In A^k gilt aij = 1 genau dann, wenn ein Pfad, der aus genau k
Kanten besteht, vom i-ten nach j-ten Knoten existiert.
Beweis durch vollständige Induktion über k:
Induktionsanfang: Für k = 1 entspricht die Behauptung genau der Definition
der Adjazenzmatrix.
Induktionsschluss: Die Behauptung gelte für A^k. Nun betrachten wir A^(k+1)
= A^k * A
Der Übersicht halber bezeichnen im Folgenden cij die Komponenten von
A^(k+1), bij die Komponenten von A^k und aij die Komponenten von a.
cij = 1 <=> es gibt ein l aus {1,...,n} mit bil = 1 ^ alj = 1
Es gibt also laut Induktionsvoraussetzung einen Pfad vom i-ten Knoten zum
l-ten, der aus genau k Kanten besteht und eine Kante vom l-ten zum j-ten
Knoten. Fügt man die Kante an den Pfad an, so erhält man einen Pfad mit k+1
Kanten vom i-ten zum j-ten Knoten.
Gruß
Heiko