Erreichbarkeitsmatrix < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:50 Do 23.04.2009 | | Autor: | georgb |
| Aufgabe | Folgende Adjazenzmatrix des ungerichteten Graphen G ist gegeben:
[mm] \pmat{ 0 & 2 & 1 & 3 \\ 2 & 0 & 3 & 1 \\ 1 & 3 & 0 & 1\\ 3 & 1 & 1 & 0 }
[/mm]
Sind alle Knoten von G erreichbar?
Stellen Sie dazu die Erreichbarkeitsmatrix auf |
Wie berechne ich die Erreichbarkeitsmatrix?
Bei ein paar Ausarbeitungen von Kollegen habe ich gesehen, dass sie die Erreichbarkeitsmatrix wie folgt berechnen:
[mm] G^{2}= [/mm] G*G
[mm] G^{3}= G^{2}*G
[/mm]
[mm] G^{4}= G^{3}*G
[/mm]
und dann alles addieren:
R = [mm] G+G^{2}+G^{3}+G^{4}
[/mm]
Ich hab das bei der Prüfung gemacht, aber der Prof hat daneben "nein" geschrieben.
Kann mir da wer weiterhelfen, wie das richtig wäre?
danke
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:26 Fr 24.04.2009 | | Autor: | felixf |
Hallo!
> Folgende Adjazenzmatrix des ungerichteten Graphen G ist
> gegeben:
> [mm]\pmat{ 0 & 2 & 1 & 3 \\ 2 & 0 & 3 & 1 \\ 1 & 3 & 0 & 1\\ 3 & 1 & 1 & 0 }[/mm]
>
> Sind alle Knoten von G erreichbar?
> Stellen Sie dazu die Erreichbarkeitsmatrix auf
> Wie berechne ich die Erreichbarkeitsmatrix?
> Bei ein paar Ausarbeitungen von Kollegen habe ich gesehen,
> dass sie die Erreichbarkeitsmatrix wie folgt berechnen:
>
> [mm]G^{2}=[/mm] G*G
> [mm]G^{3}= G^{2}*G[/mm]
> [mm]G^{4}= G^{3}*G[/mm]
Die $n$-te Potenz [mm] $G^n$ [/mm] der Matrix $G$ gibt dir an der $(i, j)$-Stelle an, wieviele Wege der Laenge $n$ es zwischen $i$ und $j$ gibt.
> und dann alles addieren:
> R = [mm]G+G^{2}+G^{3}+G^{4}[/mm]
Damit gibt dir der Eintrag von $R$ an der Stelle $(i, j)$ an, wieviele Wege der Laenge [mm] $\le [/mm] 4$ es von $i$ nach $j$ gibt.
Die Erreichbarkeitsmatrix allerdings hat als Eintraege nur Nullen und Einsen: eine Null bei $(i, j)$ wenn es keinen Weg zwischen $i$ und $j$ gibt, und eine Eins bei $(i, j)$ wenn es einen Weg von $i$ nach $j$ gibt.
Wenn es nun einen Weg zwischen $i$ und $j$ gibt, dann immer einen der Laenge hoechstens $n$, wobei $n$ die Anzahl der Eckpunkte des Graphen ist (hier: 4).
Also ist der $(i, j)$-Eintrag von $E$ genau dann 1, wenn der $(i, j)$-Eintrag von $R$ nicht 0 ist.
Du musst also $R$ so aendern, dass du alle Eintraege, die nicht 0 sind, durch 1 ersetzt.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:06 Fr 24.04.2009 | | Autor: | georgb |
| Aufgabe | 1. Wie viele Kantenfolgen der Länge 2 gibt es von v3 nach v3?
1. Wie viele Kantenfolgen der Länge 2 gibt es von v2 nach v4?
|
danke!
D.h in meinem Fall reicht bereits die Berechnung von A*A aus, das ergibt.
[mm] \pmat{ 14 & 6 & 9 & 3 \\ 6 & 14 & 3 & 9 \\ 9 & 3 & 11 & 6 \\ 3 & 9 & 6 & 11 \\ }
[/mm]
Eine weitere Multiplaktion würde mir für die Erreichbarkeitsmatrix nicht bringen, da sich nur die Zahlen ändern.
somit sieht die Erreichbarkeitsmatrix wie folgt aus:
[mm] \pmat{ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ }
[/mm]
Sehe ich das richtig, das hiermit auch folgende Fragestellung gelöst werden kann (siehe oben)?
1. Ich sehe in der Matrix A² nach (3. Zeile, 3.Element). Es gibt 11 Kantenfolgen.
1. Ich sehe in der Matrix A² nach (2. Zeile, 4.Element). Es gibt 9 Kantenfolgen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:19 Fr 24.04.2009 | | Autor: | felixf |
Hallo!
> 1. Wie viele Kantenfolgen der Länge 2 gibt es von v3 nach
> v3?
> 1. Wie viele Kantenfolgen der Länge 2 gibt es von v2 nach
> v4?
>
> danke!
>
> D.h in meinem Fall reicht bereits die Berechnung von A*A
> aus, das ergibt.
>
> [mm]\pmat{ 14 & 6 & 9 & 3 \\ 6 & 14 & 3 & 9 \\ 9 & 3 & 11 & 6 \\ 3 & 9 & 6 & 11 \\ }[/mm]
>
> Eine weitere Multiplaktion würde mir für die
> Erreichbarkeitsmatrix nicht bringen, da sich nur die Zahlen
> ändern.
>
> somit sieht die Erreichbarkeitsmatrix wie folgt aus:
> [mm]\pmat{ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ }[/mm]
>
> Sehe ich das richtig, das hiermit auch folgende
> Fragestellung gelöst werden kann (siehe oben)?
Genau.
> 1. Ich sehe in der Matrix A² nach (3. Zeile, 3.Element). Es
> gibt 11 Kantenfolgen.
>
> 1. Ich sehe in der Matrix A² nach (2. Zeile, 4.Element). Es
> gibt 9 Kantenfolgen.
Genau. :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:50 Fr 24.04.2009 | | Autor: | georgb |
Danke! hätt ich das nur zur Prüfung gewusst 
|
|
|
|
