Adjazenzmatrix, Spur < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:58 Mi 14.12.2005 | | Autor: | heine789 |
Hallo Leute!
Soll zeigen, dass
spur ( Ag² ) = 2m
ist.
Ag = Adjazenzmatrix eines ungerichteten Graphen mit m Kanten.
Habe mit einem Bsp. begonnen:
Ag = [mm] \pmat{ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 }
[/mm]
Ag² = [mm] \pmat{ 2 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 }
[/mm]
Wegen Symmetrie ist j-te Zeile = k-te Spalte von Ag. (j,k = 1,...,n)
Daraus folgere ich:
[mm] \summe_{i=1}^{n} a_{ii} [/mm] = [mm] \summe_{j=1}^{n} (z_{j})² [/mm] = 2m
mit [mm] a_{ii} [/mm] Diagonalelemente von Ag² und z = Zeile von Ag, m = Anz. Kanten
Mit Bewiesen hab ich es leider nicht so drauf.
Also kann mir jemand das bestätigen, was ich gemacht habe oder hat vielleicht jemand einen andere Lösung des Problems zu bieten, vielleicht eine einfachere?
Vielen Dank
Gruß heine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:28 Mi 14.12.2005 | | Autor: | felixf |
> Hallo Leute!
>
> Soll zeigen, dass
>
> spur ( Ag² ) = 2m
>
> ist.
>
> Ag = Adjazenzmatrix eines ungerichteten Graphen mit m
> Kanten.
>
> [...]
> oder hat vielleicht jemand einen andere Lösung des Problems
> zu bieten, vielleicht eine einfachere?
Ihr habt sicher folgendes Ergebnis gehabt: Der (i, j)-Eintrag von [mm] $Ag^n$ [/mm] ist die Anzahl der Wege von Knoten #i zu Knoten #j. Was ist also der Wert des (i, i)-Eintrages von [mm] $Ag^2$? [/mm] Was hat er mit den Kanten zu tun?
LG & HTH, Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:30 Fr 16.12.2005 | | Autor: | heine789 |
Also: Der (i, i)-te Eintrag von [mm] Ag^{2} [/mm] gibt jeweils die Anzahl der Wege der Länge 2 vom Knoten i zu sich selbst an. Da benachbarte Knoten die gleiche Kante haben, wird jede Kante des Graphen 2x überfahren.
(i = 1,...,n)
Damit wäre gezeigt, dass die Spur [mm] (Ag^{2}) [/mm] = 2m ist.
Oder???
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:12 Sa 17.12.2005 | | Autor: | felixf |
> Also: Der (i, i)-te Eintrag von [mm]Ag^{2}[/mm] gibt jeweils die
> Anzahl der Wege der Länge 2 vom Knoten i zu sich selbst an.
...also die Anzahl der Kanten, die von diesem Knoten weggehen.
> Da benachbarte Knoten die gleiche Kante haben, wird jede
> Kante des Graphen 2x überfahren.
> (i = 1,...,n)
>
> Damit wäre gezeigt, dass die Spur [mm](Ag^{2})[/mm] = 2m ist.
Genau.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:35 Sa 17.12.2005 | | Autor: | heine789 |
Vielen Dank für deine Hilfe!
|
|
|
|
