Abstände zwischen Knoten

Neue Frage »

22.01.2013, 19:21	Petey	Auf diesen Beitrag antworten »
Abstände zwischen Knoten Meine Frage: Hallo, ich habe ein Problem in der Graphentheorie. Die Fragestellung lautet: "Berechne alle Abstände zwischen Knoten im folgenden Wegenetz." (angehängt) Meine Ideen: Ich habe eine nun folgende Distanzmatrix nach dem Floyd-Warshall-Algorithmus aufgestellt: $\begin{eqnarray} D = \begin{pmatrix} 0 & \infty & \infty & \infty & \infty \\ 16 & 0 & \infty & \infty & \infty \\ 25 & 9 & 0 & \infty & 5\\ 4 & \infty & 17 & 0 & \infty \\ \infty & \infty & \infty & 9 & 0\end{pmatrix} \end{eqnarray}$ Ist das ausreichend zur Lösung der Fragestellung bzw. das was gefordert ist? Danke!
22.01.2013, 19:32	weisbrot	Auf diesen Beitrag antworten »
RE: Abstände zwischen Knoten kommt drauf an was mit "abstände" gemeint ist. vermutlich "kürzeste wege"? jedenfalls sieht mir deine matrix etwas suspekt aus.. " $\begin{eqnarray} \infty \end{eqnarray}$ " im eintrag i,j soll doch immer bedeuten dass es von i nach j (bei irgendeiner weglänge) keinen weg gibt, aber von 1 nach 5 gibt es doch einen.. lg
22.01.2013, 20:04	petey101	Auf diesen Beitrag antworten »
RE: Abstände zwischen Knoten Danke für deine Antwort, weisbrot! Was mit Abstände wirklich gemeint ist, weiß ich selbst nicht so genau. Die Aufgabenstellung lautet genau so und eine weitere Aufgabe des Übungszettels ist es, den Floyd-Warshall-Algorithmus so zu ergänzen, dass nicht nur Abstände, sondern auch kürzeste Wege berechnet werden. Also glaube ich, dass wirklich die Abstände gemeint sind. (Leider weiß ich nicht, ob da tatsächlich ein Unterschied ist, aber demnach müsste einer sein ...) Und ups, stimmt da habe ich einen Fehler. Da war mein Problem, dass es zwei Wege von 1 nach 5 gibt. Und 51/19 kann man dort nicht einsetzen, oder? $\begin{eqnarray} \begin{pmatrix} 0 & 16 & 2 & 4 & 13 \\ \infty & 0 & 9 & 26 & 35 \\ \infty & \infty & 0 & 17 & 26 \\ \infty & \infty & 14 & 0 & 9 \\ \infty & \infty & 5 & 22 & 0 \end{pmatrix} \end{eqnarray}$ PS: Nachträglich alles Gute zum Geburtstag, weisbrot!
22.01.2013, 20:37	weisbrot	Auf diesen Beitrag antworten »
RE: Abstände zwischen Knoten danke wenn ihr später erst die kürzesten wege berechnen sollt, dann ist hier wohl einfach nach den kantenlängen der jeweils verbindenden kante gefragt - aber du hast in deiner matrix anscheinend schon weglängen mehrerer mit mehreren kanten eingetragen also ich würd wirklich sagen es ist einfach die distanzmatrix gesucht - wenn es keine kante zwischen i,j gibt, dann gehört in die stelle i,j auch ein " $\begin{eqnarray} \infty \end{eqnarray}$ ". lg
22.01.2013, 21:19	petey101	Auf diesen Beitrag antworten »
RE: Abstände zwischen Knoten Okay, danke nochmal!! Ist das dann die korrekte Lösung in diesem Fall (hab am Anfang glaube ich, die Dimensionen von Ausgangs- und Zielknoten vertauscht)? $\begin{eqnarray} D = \begin{pmatrix} 0 & 16 & 2 & 4 & 19 \\ \infty & 0 & 9 & \infty & \infty \\ \infty & \infty & 0 & 17 & \infty \\ \infty & \infty & \infty & 0 & 9 \\ \infty & \infty & 5 & \infty & 0 \end{pmatrix} \end{eqnarray}$
22.01.2013, 21:25	weisbrot	Auf diesen Beitrag antworten »
RE: Abstände zwischen Knoten also das wäre dann zumindest die richtige distanzmatrix (ich glaube bei uns war das adersrum - also transponiert, aber das ist nicht so wichtig, hauptsache du weißt was der kontrolleur haben will bzw womit der algorithmus funktioniert). lg
Anzeige

22.01.2013, 21:32	petey101	Auf diesen Beitrag antworten »
RE: Abstände zwischen Knoten Vielen Dank für deine Hilfe!!
22.01.2013, 23:25	petey101	Auf diesen Beitrag antworten »
Oder ist folgende Distanzmatrix korrekt, wobei alle Abstände, auch über mehrere Kanten, berücksichtigt werden? In der Angabe steht ja "ALLE Abstände". $\begin{eqnarray} D =\begin{pmatrix} 0 & 16 & 2 & 4 & 13 \\ \infty & 0 & 9 & 26 & 35 \\ \infty & \infty & 0 & 17 & 26 \\ \infty & \infty & 14 & 0 & 9 \\ \infty & \infty & 5 & 22 & 0 \end{pmatrix} \end{eqnarray}$
23.01.2013, 17:54	weisbrot	Auf diesen Beitrag antworten »
also wie gesagt: wenn mit "abstand" die länge der - die entspr. knoten verbindenden - kante gemeint ist, dann war das von vorher (die distanzmatrix) richtig (denn das sind ja dann ALLE direkt verbindenden kanten) - denn dort schreibst du nur wenn eine kante existiert ihre länge und sonst "unendl." rein (und 0 auf der diag.). das was du zuletzt gepostet hast ist dann in diesem sinne überhaupt nicht die distanzmatrix (es gibt ja dann nur die eine d.matrix), sondern - das hab ich jetzt nicht genau nachgeprüft - die kürzeste-wege-matrix (du solltest du ja glaube später erst bestimmen) oder irgendeine matrix, die die weglängen von irgendwelchen (beliebig langen) wegen enthält (von soeiner matrix will man normalerweise nichts wissen, weil man immer daran interessiert ist was der kürzeste weg mit einer vorgegebenen maximalen kantenanzahl ist). lg

Neue Frage »

Antworten »

Abstände zwischen Knoten

Verwandte Themen