Kern < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei L die Laplace Matrix eines Graphen, und [mm] L_W [/mm] die Laplace Matrix eines Graphen mit gewichteten Kanten.
Zeigen Sie, dass der Kern von L durch die Gewichtung nicht beeinflusst wird, d. h. [mm] kern(L)=kern(L_W). [/mm] |
Hallo!
Ich weiß, dass ich die Laplace-Matrizen zerlegen kann:
L = [mm] DD^T [/mm]
[mm] L_W [/mm] = [mm] DWD^T
[/mm]
Außerdem weiß ich [mm] kern(L)=kern(D^T).
[/mm]
Zeigen muss ich also
[mm] kern(DWD^T)=kern(D^T)
[/mm]
[mm] \{x|DWD^T x = 0\} [/mm] = [mm] \{x|D^T x = 0\}
[/mm]
Aus der rechten Gleichung folgt natürlich immer die linke Gleichung. Ich muss also zeigen, dass [mm] DWD^T [/mm] x =0 nicht noch weitere Lösungen hat, oder? Aber wie kann ich das geschickt machen?
Grüße
Papillon
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:13 Do 03.09.2009 | | Autor: | felixf |
Hallo!
> Sei L die Laplace Matrix eines Graphen, und [mm]L_W[/mm] die Laplace
> Matrix eines Graphen mit gewichteten Kanten.
Die Matrizen gehoeren schon zum gleichen Graph, oder?
> Zeigen Sie, dass der Kern von L durch die Gewichtung nicht
> beeinflusst wird, d. h. [mm]kern(L)=kern(L_W).[/mm]
>
> Ich weiß, dass ich die Laplace-Matrizen zerlegen kann:
>
> L = [mm]DD^T[/mm]
> [mm]L_W[/mm] = [mm]DWD^T[/mm]
Kannst du irgendetwas ueber die Matrix $W$ sagen? Ist es eine Diagonalmatrix? Kann $W$ in der Form $V [mm] V^T$ [/mm] geschrieben werden?
> Außerdem weiß ich [mm]kern(L)=kern(D^T).[/mm]
Ja, da $L v = 0 [mm] \Rightarrow [/mm] D [mm] D^T [/mm] v = 0 [mm] \Rightarrow v^T [/mm] D [mm] D^T [/mm] v = 0 [mm] \Rrightarrow \langle D^T [/mm] v, [mm] D^T [/mm] v [mm] \rangle [/mm] = 0 [mm] \Rightarrow D^T [/mm] v = 0$; und aus [mm] $D^T [/mm] v = 0$ folgt natuerlich auch $L v = D [mm] (D^T [/mm] v) = D 0 = 0$.
Wenn du etwa $W$ in der Form $V [mm] V^T$ [/mm] schreiben kannst mit $V$ invertierbar, dann bekommst du mit dem gleichen Argument [mm] $L_W [/mm] v = 0 [mm] \Leftrightarrow V^T D^T [/mm] v = 0$, und da [mm] $V^T$ [/mm] invertierbar ist ist dies aequivalent zu [mm] $D^T [/mm] v = 0$.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:09 Do 03.09.2009 | | Autor: | papillon |
Also:
[mm] L_W [/mm] und L gehören zum gleichen Graphen.
W ist die Gewichtungsmatrix, die jeder Kante [mm] e_k [/mm] vom Knoten [mm] v_i [/mm] zum Knoten [mm] v_j [/mm] ein Gewicht [mm] w_{ij} [/mm] zuordnet. Es ergibt sich für W also eine Diagonalmatrix
W = [mm] \pmat{ w_1 & 0 & 0 & ... \\ 0 & w_2 & 0 \\ ... &...&... }
[/mm]
Kann ich dieses W dann entsprechend zerlegen? Das wäre natürlich günstig.
Gruß
Papillon
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:52 Do 03.09.2009 | | Autor: | felixf |
Hallo Papillon,
> [mm]L_W[/mm] und L gehören zum gleichen Graphen.
> W ist die Gewichtungsmatrix, die jeder Kante [mm]e_k[/mm] vom
> Knoten [mm]v_i[/mm] zum Knoten [mm]v_j[/mm] ein Gewicht [mm]w_{ij}[/mm] zuordnet. Es
> ergibt sich für W also eine Diagonalmatrix
>
> W = [mm]\pmat{ w_1 & 0 & 0 & ... \\ 0 & w_2 & 0 \\ ... &...&... }[/mm]
Und was ist mit [mm] $w_{ij}$ [/mm] fuer $i [mm] \neq [/mm] j$? Aber nehmen wir mal an, dass es eine Diagonalmatrix ist.
Sind die Gewichtungen alle nicht-negativ? In dem Falle kannst du
$W = [mm] \hat{W} \hat{W}^T [/mm] = [mm] \hat{W}^T \hat{W} [/mm] = [mm] \hat{W} \hat{W}$ [/mm] mit [mm] $\hat{W} [/mm] := [mm] \pmat{\sqrt{w_1} & 0 & \cdots & 0 \\ 0 & \sqrt{w_2} & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & \sqrt{w_n} }$ [/mm] schreiben.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 So 06.09.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
