Erreichbarkeitsmatrix < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Aufgabenstellung:
Der gerichtete Graph G = (V,E,f) sei gegeben durch
V = {v1,v2,v3,v4,v5}
....
d) Wieviele Kantenfolgen der Länge 2 gibt es insgesammt in diesem Graphen?
e) Wieviele Kantenfolgen der Länge 3 gibt es von v3 nach v2?
f) Sind alle Knoten in diesem Graphen erreichbar? |
Hallo Leute!
Ich habe eine Frage zum Thema Graphentheorie bzw. zur Erreichbarkeitsmatrix.
Ich weiß dass hier im Forum schon mal was ähnliches gepostet wurde, nur bin ich aus dem nicht schlau geworden!
Ich habe wie oben angegeben 5 Knoten! Die Kanten sowie die Funktion ist mal unwichtig.
Ich habe folgende Adjazenzmatrix:
[mm] \pmat{ 0 & 1 & 0 & 3 & 1 \\ 0 & 0 & 1 & 0 & 0 \\0 & 2 & 0 & 1 & 1 \\0&1&2&0&0 \\ 0&0&1&2&0 }
[/mm]
a) b) c) habe ich lösen können -> (war adjazenz und inzidenzmatrix sowie graphen einzeichnen)
bei d) Habe ich A*A gerechnet und die Zeilensummen addiert. Da kommen 43 Kantenfolgen der Länge 2 raus.
bei e) Habe ich [mm] A^2 [/mm] genommen und nur die 2. Spalte von A damit multipliziert.
so.. und jetzt meine Frage zu f) Wie stelle ich die Erreichbarkeitsmatrix auf? Muss ich da bis [mm] A^5 [/mm] hinaufgehen und dann alle Einträge die nicht 0 sind in 1 ändern und 0 belassen?
Hoffe ihr könnt mir da weiterhelfen. Ist denke ich nur eine Kleinigkeit ;)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
lg Chris
|
|
| |
|
Hallo chris,
> Der gerichtete Graph G = (V,E,f) sei gegeben durch
>
> V = {v1,v2,v3,v4,v5}
> ....
>
> d) Wieviele Kantenfolgen der Länge 2 gibt es insgesamt in
> diesem Graphen?
> e) Wieviele Kantenfolgen der Länge 3 gibt es von v3 nach v2?
> f) Sind alle Knoten in diesem Graphen erreichbar?
>
> Ich habe eine Frage zum Thema Graphentheorie bzw. zur
> Erreichbarkeitsmatrix.
> Ich habe wie oben angegeben 5 Knoten! Die Kanten sowie die
> Funktion ist mal unwichtig.
(die Kanten sind natürlich schon auch wichtig !)
> Ich habe folgende Adjazenzmatrix:
>
> [mm]\pmat{ 0 & 1 & 0 & 3 & 1 \\ 0 & 0 & 1 & 0 & 0 \\0 & 2 & 0 & 1 & 1 \\0&1&2&0&0 \\ 0&0&1&2&0 }[/mm]
(daraus kann man die Kanten nun natürlich ablesen)
> a) b) c) habe ich lösen können -> (war adjazenz und
> inzidenzmatrix sowie graphen einzeichnen)
>
> bei d) Habe ich A*A gerechnet und die Zeilensummen addiert.
> Da kommen 43 Kantenfolgen der Länge 2 raus. ![[haee]](/images/smileys/haee.gif "[haee]")
ich komme auf 44
> bei e) Habe ich [mm]A^2[/mm] genommen und nur die 2. Spalte von A
> damit multipliziert.
(Begründung ? , Ergebnis ?)
> so.. und jetzt meine Frage zu f) Wie stelle ich die
> Erreichbarkeitsmatrix auf? Muss ich da bis [mm]A^5[/mm] hinaufgehen
> und dann alle Einträge die nicht 0 sind in 1 ändern und 0
> belassen?
Braucht man überhaupt eine Erreichbarkeitsmatrix ?
Man kann doch aus der ersten Spalte der Matrix A
sofort erkennen, dass der Knoten [mm] v_1 [/mm] von keinem Knoten
aus über eine Kante erreichbar ist - und damit ist ja
die gestellte Frage schon beantwortet, oder ?
LG Al-Chw.
|
|
|
| |
|
ja stimmt, da kommen 44 Kantefolgen der Länge 2 raus!
Sorry..
bei e)
Ich habe [mm] A^2 [/mm] genommen und die 3 Zeile davon mit der 2. Spalte von A multipliziert anstatt [mm] A^3 [/mm] auszurechnen und diese dann davon abzulesen!
Da sollten 12 Wege der Länge 3 rauskommen!
e) Mann! Das war schon wieder so ne Frage was der Prof. gestellt hat. Ja ich glaub du hast recht. Ich hätte hinschreiben sollen dass man das an der Adjazenzmartix ablesen kann, da die erste Spalte gleich 0 ist. ^^
Aber nochmal zu der Frage: wenn das jetzt nicht der Fall wäre. Wie gehe ich da vor bei der Erreichbarkeitsmatrix? Muss ich da bis n-1, also in dem Fall bis [mm] A^4 [/mm] hochrechnen?
|
|
|
| |
|
Guten Tag !
> ja stimmt, da kommen 44 Kantefolgen der Länge 2 raus!
>
> Sorry..
>
> bei e)
> Ich habe [mm]A^2[/mm] genommen und die 3 Zeile davon mit der 2.
> Spalte von A multipliziert anstatt [mm]A^3[/mm] auszurechnen und
> diese dann davon abzulesen!
> Da sollten 12 Wege der Länge 3 rauskommen!
Meine Rechnung: (3.Zeile von A) mal A mal (2.Spalte von A):
$ [mm] \pmat{0 & 2 & 0 & 1 & 1 }\ [/mm] *\ [mm] \pmat{ 0 & 1 & 0 & 3 & 1 \\ 0 & 0 & 1 & 0 & 0 \\0 & 2 & 0 & 1 & 1 \\0&1&2&0&0 \\ 0&0&1&2&0 }\ [/mm] *\ [mm] \pmat{ 1 \\0 \\ 2 \\1\\ 0}\ [/mm] =\ 12 $
> e) Mann! Das war schon wieder so ne Frage was der Prof.
> gestellt hat. Ja ich glaub du hast recht. Ich hätte
> hinschreiben sollen dass man das an der Adjazenzmartix
> ablesen kann, da die erste Spalte gleich 0 ist. ^^
>
> Aber nochmal zu der Frage: wenn das jetzt nicht der Fall
> wäre. Wie gehe ich da vor bei der Erreichbarkeitsmatrix?
> Muss ich da bis n-1, also in dem Fall bis [mm]A^4[/mm] hochrechnen?
Schau dir dazu mal diesen thread an !
LG Al-Chw.
|
|
|
|
