Erreichbarkeitsmatrix < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Die Erreichbarkeitsmatrix M eines gerichteten Graphen G mit n Ecken ist eine n×n-Matrix mit folgenden Elementen:
$ [mm] M_{ij}=\begin{cases} 1, & \mbox{falls } \mbox{ es} \mbox{ einen} \mbox{ gerichteten}\mbox{ Weg} \mbox{ von}\mbox{ Ecke} \mbox{ i} \mbox{ nach}\mbox{ Ecke} \mbox{ j}\mbox{ gibt}\\\ 0, & \mbox{sonst}\end{cases} [/mm] $
(Damit sind die Diagonalelemente von M alle gleich 1, denn Wege der Länge 0 sind zulässig.)
Beweisen Sie, dass das i-te Diagonalelement von [mm] M^{2} [/mm] gleich der Anzahl der Ecken derjenigen starken Zusammenhangskomponente von G ist, welche die Ecke i enthält. |
Hallo,
ich habe Schwierigkeiten beim Lösen der Aufgabe, wäre super, wenn mir jemand helfen könnte.
Mein Ansatz:
1. Man nehme irgendeinen Graphen mit starken Zusammenhangskomponenten.
2. Zu diesen Graphen wird die Adjazenmatrix aufgestellt. Die Elemente der Hauptdiagonale werden auf 1 gesetzt. (Führt zur Erreichbarkeitsmatrix)
4. Die Erreichbarkeitsmatrix wird mit sich selbst multipliziert. Es kommt eine Matrix mit Einsen in der Diagonale heraus.
Ich weiß aber nicht was mir das jetzt sagen soll. Wenn ich nach der Aufgabe gehen würde, dann heißt das doch, dass es für jeden Knoten eine starke Zusammenhangskomponente gibt, oder? Wie kann ich das beweisen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:52 Di 29.05.2007 | | Autor: | piet.t |
Hallo und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
> Mein Ansatz:
>
> 1. Man nehme irgendeinen Graphen mit starken
> Zusammenhangskomponenten.
Eigentlich hat ja jeder Graph starke Zusammenhangskomponenten, und wenn sie nur aus einer Ecke bestehen, aber egal....
> 2. Zu diesen Graphen wird die Adjazenmatrix aufgestellt.
> Die Elemente der Hauptdiagonale werden auf 1 gesetzt.
> (Führt zur Erreichbarkeitsmatrix)
O.K.
> 4. Die Erreichbarkeitsmatrix wird mit sich selbst
> multipliziert. Es kommt eine Matrix mit Einsen in der
> Diagonale heraus.
Warum sollen da Einsen auf der Diagonalen stehen? Es steht ja schon in der Aufgabe, dass das i-te Diagonalelement gleich der Anzahl der Ecken in der starken Zusammenhangskomponente ist - und das können durchaus auch mehr als eine sein.
Schreib doch einfach mal hin, wie Du das i-te Diagonalelement von [mm] M^2 [/mm] ausrechnen würdest. Dann überlegst Du Dir noch, was die jeweiligen Einträge in M bedeuten und dann sollte man es eigentlich schon sehen!
>
> Ich weiß aber nicht was mir das jetzt sagen soll. Wenn ich
> nach der Aufgabe gehen würde, dann heißt das doch, dass es
> für jeden Knoten eine starke Zusammenhangskomponente gibt,
> oder?
> Wie kann ich das beweisen?
Natürlich gibt es für jeden Knoten eine starke Zusammenhangskomponente. Wie oben schon gesagt: im schlimmsten Fall besteht sie aus dem Knoten selbst und sonst gar nichts.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Vielleicht kommst Du damit ja schon ein bisschen weiter.
Gruß
piet
|
|
|
| |
|
Hallo Peter,
vielen, vielen Dank für deine Antwort!
Ich muss zugeben, mir ist nicht ganz klar was mit "i-te" gemeint ist. Ich versuche es mal:
1. "i" wird als Index angegeben.
2. Bei der Diagonale handelt es sich, wenn ich es richtig verstanden habe, um eine Nebendiagonale? Aber welche? Kann ich die frei wählen z.B: [mm] a_{21} [/mm] bis [mm] a_{54}? [/mm] (2, 0,0,0)
Matrix [mm] M^{2}:
[/mm]
[mm] \vmat{ 1 & 1 & 1& 1&0 \\ 2 & 1&0&1&0 \\0&0&1&0&0\\1&2&0&1&0\\0&0&0&0&1}
[/mm]
Bin ich damit auf dem richtigen Weg?
Vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:01 Di 29.05.2007 | | Autor: | piet.t |
Hallo,
es handelt sich dabei um die Hauptdiagonale der Matrix. Ist also [mm] $M^2=(a_{ij})$, [/mm] dann ist das i-te Diagonalelement also gerade [mm] $a_{ii}$. [/mm] Wie gesagt: schreib Dir mal ganz allgemein auf, wie man [mm] $a_{ii}$ [/mm] aus den [mm] $M_{ij}$ [/mm] berechnet. Der Rest ist scharfes anschauen.
Gruß
piet
|
|
|
| |
|
Vielen Dank! Das hat mir geholfen!
|
|
|
|
