Warshall / Floyd Algorithmus < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe 1 | WARSHALL:
Sei M := {a, b, c, d} , sei R = {(a, b), (a, d), (b, b), (b, c), (c, a), (c, d), (d, d)} und
sei G der Graph der Relation R. Stellen Sie die Adjazenzmatrix des Graphen G auf,
berechnen Sie mit dem Algorithmus von Warshall die Adjazenzmatrix der transitiven
H¨ulle T von R und geben Sie die Mengendifferenz M2 \ T an. |
| Aufgabe 2 | FLOYD:
Sei G der bewertete Graph mit der Eckenmenge fa; b; c; dg und der Kantenmenge
f(a; 1; b); (a; 2; c); (b; 2; a); (c; 2; b); (d; 4; c); (d; 1; a)g ;
wobei in jedem Tripel die erste Komponente die Anfangsecke, die zweite Komponente
die Kantenbewertung und die dritte Komponente die Endecke angibt.
Berechnen Sie mit dem Algorithmus von Floyd alle Abstände zwischen den Ecken.
Geben Sie die Startmatrix sowie in jedem Schritt des Algorithmus die berechnete
Matrix an. |
Hi!
kann mir jemand die beiden Algorithmen erlären? was machen sie genau und wie gehen sie...
btw: adjazenzmatrix bei der ersten aufgabe ist
0 1 0 1
0 1 1 0
1 0 0 1
0 0 0 1
bei der 2.
0 1 2 [mm] \infty
[/mm]
2 0 [mm] \infty \infty
[/mm]
[mm] \infty [/mm] 2 0 [mm] \infty
[/mm]
1 [mm] \infty [/mm] 4 0
danke für eure hilfe
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 So 28.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
