Wegematrizen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 03:09 Fr 20.08.2010 | | Autor: | melodie |
| Aufgabe | Sei G = (Gn,E) ein gerichteter Graph und A die Adjazenzmatrix von G.
Wir definieren:
[mm] W_0 [/mm] =sgn(A+I)
[mm] \forall [/mm] i [mm] \in N_0 [/mm] : [mm] W_i_+_1 =sgn(W_i [/mm] * [mm] W_i)
[/mm]
|
Hallo,
ich soll Wegematrizen für einen Graph ausrechnen.Den Graphen kann ich hier nicht abtippen. [mm] W_0 [/mm] habe ich schon raus. Adjazenmatirx+Einheitsmatrix.
[mm] W_0: \pmat{ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 }
[/mm]
Nun komme ich bei [mm] W_1 [/mm] nicht weiter. nach der Aufgabenstellung soll [mm] W_1= W_i_+_1 [/mm] sein also [mm] W_0_+_1 [/mm] ? was bedeutet aber die signumfunktion und wie soll ich mit [mm] W_0*W_0 [/mm] auf [mm] W_1 [/mm] kommen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:03 Fr 20.08.2010 | | Autor: | felixf |
Moinmoin!
> Sei G = (Gn,E) ein gerichteter Graph und A die
> Adjazenzmatrix von G.
> Wir definieren:
> [mm]W_0[/mm] =sgn(A+I)
> [mm]\forall[/mm] i [mm]\in N_0[/mm] : [mm]W_i_+_1 =sgn(W_i[/mm] * [mm]W_i)[/mm]
>
>
>
> ich soll Wegematrizen für einen Graph ausrechnen.
Ich vermute, dazu rechnest du solange die [mm] $W_i$s [/mm] aus bis [mm] $W_i [/mm] = [mm] W_{i+1}$ [/mm] ist fuer ein $i$? Und dann ist [mm] $W_i [/mm] = [mm] W_{i+1}$ [/mm] die Wegematrix?
> Den
> Graphen kann ich hier nicht abtippen. [mm]W_0[/mm] habe ich schon
> raus. Adjazenmatirx+Einheitsmatrix.
> [mm]W_0: \pmat{ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 }[/mm]
Damit sagt der $(i, j)$-Eintrag in [mm] $W_0$ [/mm] aus, ob es einen Weg der Laenge 0 oder 1 von $i$ nach $j$ gibt.
> Nun komme ich bei [mm]W_1[/mm] nicht weiter. nach der
> Aufgabenstellung soll [mm]W_1= W_i_+_1[/mm] sein also [mm]W_0_+_1[/mm] ?
Ja. Also [mm] $W_1 [/mm] = [mm] sgn(W_0 \cdot W_0)$.
[/mm]
> was bedeutet aber die signumfunktion
Nun, das musst du herausfinden - wir koennen nicht hellsehen. Schau mal in euer Skript.
Ich hab zwei Vermutungen:
a) man nimmt einfach von jedem Eintrag in der Matrix das Signum;
b) man betreibt etwas mehr lineare Algebra, was bei den Matrizen von gerichteten Graphen nicht so gut funktionieren wird.
Insofern tippe ich auf a).
Der $(i, j)$-Eintrag in [mm] $W_0 \cdot W_0$ [/mm] ist die Anzahl der Wege mit Laenge $0 + 0$, $0 + 1$, $1 + 0$ und $1 + 1$. Wenn du also Vorzeichen nimmst, bleiben nur noch Nullen und Einsen. Eine Eins gibt's genau dann, wenn es einen Weg der Laenge [mm] $\le [/mm] 2$ gibt.
Genauso besteht [mm] $W_2$ [/mm] nur aus Einsen und Nullen, mit einer Eins genau bei den $(i, j)$-Eintraegen, wenn es einen Weg der Laenge [mm] $\le [/mm] 4$ von $i$ nach $j$ gibt.
Damit gibt es in [mm] $W_i$ [/mm] am Eintrag $(k, [mm] \ell)$ [/mm] genau dann eine Eins, wenn es einen Weg der Laenge [mm] $\le 2^i$ [/mm] von $k$ nach [mm] $\ell$ [/mm] gibt.
> und wie soll ich mit
> [mm]W_0*W_0[/mm] auf [mm]W_1[/mm] kommen?
Multipliziere [mm] $W_0$ [/mm] mit sich selbst, und ersetze positive Zahlen durch 1.
LG Felix
|
|
|
|
