Graphentheorie < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Graph vorgegeben und man soll die Adjazenzmatrix erstellen und mit Hilfe dieser, die Anzahl der gerichteten Kantenfolgen der Länge 3 von Knoten 4 nach 6 finden |
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
die sieht dann die Adjazenzmatrix letztendlich folgendermaßen aus:
[mm] \pmat{ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 }
[/mm]
wie genau muss ich das angehen um aufgrund der Matrix auf die Länge 3 von Knoten 4 nach 6 zu finden?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:25 Mo 21.01.2008 | | Autor: | Zaed |
Hallo,
dazu muss man einen kleinen Fakt aus der Darstellung von Graphen durch eine Adjazenzmatrix verwenden. Soweit ich mich erinnere gilt für eine Adjazentmatrix A folgende Aussage: In der Matrix [mm] A^k, k\in\IN [/mm] steht im Eintrag (i,j) die Anzahl der Pfade der Länge k von einem Knoten i nach j.
Das kann man leicht mittels vollständiger Induktion beweisen.
Nun wirst du diesen Satz sicherlich auf deine gegebene Matrix anwenden können, oder?
Liebe Grüße, Zaed
|
|
|
| |
|
ja das hab ich schon verstanden, nur dachte ich, dass es diesbezüglich vielleicht noch einen trick geben würde, aber danke :)
|
|
|
|
