[
OT]
Wenn wir jetzt hergehen und für A, B, C, D weitere Matrizen aufstellen, z. B. für A, E, F, G:
Code:
A E F G
+--------
A | 0 0 0 1
E | 0 0 1 0
F | 0 1 0 1
G | 1 0 1 0
Desgleichen noch für B, C, D und weitere Orte, so kann ich mich hier quasi von Matrix zu Matrix hangeln, um letztlich einen Weg von z. B. D nach G zu finden, der hier also über A führt, wo ich aber umsteigen muss.
Wenn ich jetzt die beiden Matrizen zusammenfasse (heißt das so?) käme dann das dabei raus?
Code:
A B C D E F G
+--------------
A | 0 1 0 1 0 0 0
B | 1 0 0 1 0 0 0
C | 0 0 0 1 0 0 0
D | 1 1 1 0 0 0 1
E | 0 0 0 0 0 0 0
F | 0 0 0 0 0 0 0
G | 0 0 0 1 0 0 0
Also schaue ich in A stehend wohin ich kann. Das sind B und D. Nun schaue ich für B nach, wohin ich kann, das sind A und D. das passt mir nicht. Jetzt schaue ich für D nach, wohin ich kann, das sind A, B, C und G. Und schon habe ich meine Route
(Da meldet sich im Hintergrund eine Stimme, die mich dran erinnert:
Da war mal was mit Matrizenmultiplikation! - gehört das hierhin?)[/
OT]
Ja, wenn du die Adjazenzmatrix mit sich selbst multiplizierst, dann bekommst du für jeden Knoten die Knoten, die du mit genau 2 Schritten erreichst. Wenn du dann noch mal die Matrix dranmultiplizierst kriegst du die Knoten, die du mit 3 Schritten erreichst usw...
Allerdings macht deine zusammengefasste Matrix irgendwie keinen Sinn. Da steht jetzt z.B. dass du von D nach G gehen kannst, dabei gibt es gar keine Verbindung zwischen D und G. Auf der anderen Seite müsstest du von A nach G kommen, aber da steht bei dir eine 0. Und alle anderen Verbindungen von deiner AEFG-Matrix fehlen irgendwie auch...
Ich kenn es außerdem eigentlich auch nur so, dass es
eine Adjazenzmatrix gibt, in der alle Knoten-Kombinationen drin sind, und nicht mehrere Ajazenzmatrizen für Teilgraphen, die erst noch kombiniert werden müssen.
Aber ich verweise jetzt einfach mal
auf diese Vorlesungsfolien (oder hier das etwas ausführlichere
Skript, ab Seite 101 geht’s los), damit wir nicht noch weiter ins Off-Topic abdriften.
[/
OT]