www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - Erreichbarkeitsmatrix
Erreichbarkeitsmatrix < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Erreichbarkeitsmatrix: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:50 Do 23.04.2009
Autor: georgb

Aufgabe
Folgende Adjazenzmatrix des ungerichteten Graphen G ist gegeben:
[mm] \pmat{ 0 & 2 & 1 & 3 \\ 2 & 0 & 3 & 1 \\ 1 & 3 & 0 & 1\\ 3 & 1 & 1 & 0 } [/mm]

Sind alle Knoten von G erreichbar?
Stellen Sie dazu die Erreichbarkeitsmatrix auf

Wie berechne ich die Erreichbarkeitsmatrix?
Bei ein paar Ausarbeitungen von Kollegen habe ich gesehen, dass sie die Erreichbarkeitsmatrix wie folgt berechnen:

[mm] G^{2}= [/mm] G*G
[mm] G^{3}= G^{2}*G [/mm]
[mm] G^{4}= G^{3}*G [/mm]

und dann alles addieren:
R = [mm] G+G^{2}+G^{3}+G^{4} [/mm]

Ich hab das bei der Prüfung gemacht, aber der Prof hat daneben "nein" geschrieben.
Kann mir da wer weiterhelfen, wie das richtig wäre?

danke

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Erreichbarkeitsmatrix: Antwort
Status: (Antwort) fertig Status 
Datum: 05:26 Fr 24.04.2009
Autor: felixf

Hallo!

> Folgende Adjazenzmatrix des ungerichteten Graphen G ist
> gegeben:
>  [mm]\pmat{ 0 & 2 & 1 & 3 \\ 2 & 0 & 3 & 1 \\ 1 & 3 & 0 & 1\\ 3 & 1 & 1 & 0 }[/mm]
>  
> Sind alle Knoten von G erreichbar?
>  Stellen Sie dazu die Erreichbarkeitsmatrix auf
>  Wie berechne ich die Erreichbarkeitsmatrix?
>  Bei ein paar Ausarbeitungen von Kollegen habe ich gesehen,
> dass sie die Erreichbarkeitsmatrix wie folgt berechnen:
>  
> [mm]G^{2}=[/mm] G*G
>  [mm]G^{3}= G^{2}*G[/mm]
>  [mm]G^{4}= G^{3}*G[/mm]

Die $n$-te Potenz [mm] $G^n$ [/mm] der Matrix $G$ gibt dir an der $(i, j)$-Stelle an, wieviele Wege der Laenge $n$ es zwischen $i$ und $j$ gibt.

> und dann alles addieren:
>  R = [mm]G+G^{2}+G^{3}+G^{4}[/mm]

Damit gibt dir der Eintrag von $R$ an der Stelle $(i, j)$ an, wieviele Wege der Laenge [mm] $\le [/mm] 4$ es von $i$ nach $j$ gibt.

Die Erreichbarkeitsmatrix allerdings hat als Eintraege nur Nullen und Einsen: eine Null bei $(i, j)$ wenn es keinen Weg zwischen $i$ und $j$ gibt, und eine Eins bei $(i, j)$ wenn es einen Weg von $i$ nach $j$ gibt.

Wenn es nun einen Weg zwischen $i$ und $j$ gibt, dann immer einen der Laenge hoechstens $n$, wobei $n$ die Anzahl der Eckpunkte des Graphen ist (hier: 4).

Also ist der $(i, j)$-Eintrag von $E$ genau dann 1, wenn der $(i, j)$-Eintrag von $R$ nicht 0 ist.

Du musst also $R$ so aendern, dass du alle Eintraege, die nicht 0 sind, durch 1 ersetzt.

LG Felix


Bezug
        
Bezug
Erreichbarkeitsmatrix: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:06 Fr 24.04.2009
Autor: georgb

Aufgabe
1. Wie viele Kantenfolgen der Länge 2 gibt es von v3 nach v3?
1. Wie viele Kantenfolgen der Länge 2 gibt es von v2 nach v4?

danke!

D.h in meinem Fall reicht bereits die Berechnung von A*A aus, das ergibt.

[mm] \pmat{ 14 & 6 & 9 & 3 \\ 6 & 14 & 3 & 9 \\ 9 & 3 & 11 & 6 \\ 3 & 9 & 6 & 11 \\ } [/mm]

Eine weitere Multiplaktion würde mir für die Erreichbarkeitsmatrix nicht bringen, da sich nur die Zahlen ändern.

somit sieht die Erreichbarkeitsmatrix wie folgt aus:
[mm] \pmat{ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ } [/mm]

Sehe ich das richtig, das hiermit auch folgende Fragestellung gelöst werden kann (siehe oben)?

1. Ich sehe in der Matrix A² nach (3. Zeile, 3.Element). Es gibt 11 Kantenfolgen.

1. Ich sehe in der Matrix A² nach (2. Zeile, 4.Element). Es gibt 9 Kantenfolgen.






Bezug
                
Bezug
Erreichbarkeitsmatrix: Antwort
Status: (Antwort) fertig Status 
Datum: 09:19 Fr 24.04.2009
Autor: felixf

Hallo!

> 1. Wie viele Kantenfolgen der Länge 2 gibt es von v3 nach
> v3?
>  1. Wie viele Kantenfolgen der Länge 2 gibt es von v2 nach
> v4?
>  
> danke!
>  
> D.h in meinem Fall reicht bereits die Berechnung von A*A
> aus, das ergibt.
>  
> [mm]\pmat{ 14 & 6 & 9 & 3 \\ 6 & 14 & 3 & 9 \\ 9 & 3 & 11 & 6 \\ 3 & 9 & 6 & 11 \\ }[/mm]
>  
> Eine weitere Multiplaktion würde mir für die
> Erreichbarkeitsmatrix nicht bringen, da sich nur die Zahlen
> ändern.
>  
> somit sieht die Erreichbarkeitsmatrix wie folgt aus:
>  [mm]\pmat{ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ }[/mm]
>  
> Sehe ich das richtig, das hiermit auch folgende
> Fragestellung gelöst werden kann (siehe oben)?

Genau.

> 1. Ich sehe in der Matrix A² nach (3. Zeile, 3.Element). Es
> gibt 11 Kantenfolgen.
>  
> 1. Ich sehe in der Matrix A² nach (2. Zeile, 4.Element). Es
> gibt 9 Kantenfolgen.

Genau. :)

LG Felix


Bezug
                        
Bezug
Erreichbarkeitsmatrix: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:50 Fr 24.04.2009
Autor: georgb

Danke! hätt ich das nur zur Prüfung gewusst ;-)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]