Schaltungsanalyse Widerstandsnetzwerk

Hallo,

kennt jemand einen schlauen Algorithmus zur Erstellung eines "vollständigen Baumes", wie er bspw für das Maschenstromverfahren gebraucht wird? Es geht dabei um zufällige Netzwerke aus Widerständen, die kreuz und quer miteinander verdrahtet sind.

Herzlichen Dank, Arne

Reply to
Arne Lüllmann
Loading thread data ...

Der Algorithmus, den Du suchst, nennt sich DFS (Depth First Search oder Tiefensuche). Der kann einen beliebigen Graphen durchlaufen und generiert dabei einen Spannbaum.

Man fängt an einem Knoten an, markiert ihn als "besucht", packt alle seine direkten Nachbarn auf einen Stack und nimmt dann den nächsten vom Stack und macht das selbe. Findet man einen Knoten, der bereits besucht ist, so kommt er natürlich nicht mehr auf den Stack. Ist der Knoten noch nicht besucht, so stellt dies eine Kante im Spannbaum vom aktuelle bearbeiteten zu diesem Knoten dar.

Ausführlichere Erläuterung gibts zum Beispiel bei Wikipedia:

formatting link

Gruß,

Andreas

--
.------- -  -                    ---.
| Andreas Schroeder - www.a-netz.de |
 Click to see the full signature
Reply to
Andreas Schroeder

Bist du dir sicher, dass du einen vollständigen Graphen haben willst (also von der Größe (n^2)/2 mal so groß wie Eingangsknoten)? Also "jeder mit jedem"? Schau dir mal den Floyd-Algorithmus und den Dijkstra an, die berechnen jeweils kürzeste Wege zwischen zwei Knoten - dann noch dynamisches Programmieren und das sollte recht effizient zu lösen sein.

Aber irgendwie weiß ich nicht wirklich, ob das das ist, was du suchst.

Gruß, Johannes

Reply to
Johannes Bauer

Gesucht wird eher ein "Minimaler Spannbaum" (besser: irgendein Spannbaum, da die Kanten ja keine Gewichte haben). Dafür gibt es die Algorithmen von Kruskal und Prim, die beide einfach zu verstehen sind.

Reply to
Lars Noschinski

Ah okay, ich bin durch das Wort "vollständig" da auf die falsche Fährte gelockt worden.

Viele Grüße, Johannes

Reply to
Johannes Bauer

Vielen Dank für die Antworten. Na ja, es geht um das Aufstellen des lin. Gleichungssystems aus Maschen- und Knotenregel. Um die Mschen zu Identifizieren brauche ich einen Algorithmus. Und hier bietet das Verfahren mit vollständigem Baum - d.h. ein Teilgraph, der alle Knoten miteinander verbindet, ohne eine geschlossene Masche entstehen zu lassen - und dem komplementären Baum - d.h. der Rest - einen Weg zur Bestimmung aller unabhängigen Maschen.

Bin mir nicht sicher, ob mir das Wissen um die kürzeste Verbindung da weiterhilft. Bin auf diese Verfahren auch schon gestoßen. Aber auf eine Idee zum Verfahren haben sie mich noch nicht gebracht.

schöne Grüße, Arne

Reply to
Arne Luellmann

Lars Noschinski schrieb:

ah danke, da werde ich gleich mal nachschauen. Deine Antwort hatte irgendwie Verspätung bei mir.

viele Grüße, Arne

Reply to
Arne Luellmann
  • Arne Luellmann [2006-03-28 18:40]:

Wie gesagt, ein (minimaler) Spannbaum ist das, was du suchst.

formatting link
formatting link

für eine erste Anlaufstelle.

Reply to
Lars Noschinski
  • Arne Luellmann [2006-03-28 18:41]:

Wenn man sich vorstellt, dass es früher durchaus Newslaufzeiten von mehreren Tagen gab ... ;)

Reply to
Lars Noschinski

Lars Noschinski schrieb:

genau, gerade ausgedruckt! Bin sehr dankbar! Arne

Reply to
Arne Luellmann

"Arne Lüllmann" schrieb im Newsbeitrag news:e0b9pc$h57$ snipped-for-privacy@gwdu112.gwdg.de...

Hallo Arne,

Wenn es um die Berechnung mit einem Computer geht, dann kannst du stur eine Matrix aufstellen und mit dem Gauß-Algo lösen.

Grundlagen und Rechneverfahren der Elektrotechnik Gerhard Schnell, Konrad Hoyer, Martin Vömel Vieweg Verlag ISBN 3-528-04530-2

Und hier kannst du es einsehen oder ausleihen,

formatting link

Gruß Helmut

Reply to
Helmut Sennewald

Hallo,

Arne Luellmann schrieb:

Hmm... wieso nimmst Du nicht einfach einen normalen Zyklentest? Also z.B. Tiefensuche, dabei den "Vater" merken. Jeder schon besuchten Nachfolger eines Knotens, der nicht der eigene "Vater" ist, bedeutet einen Zyklus.

Gruesse,

Norbert Stuhrmann

Reply to
Norbert Stuhrmann

Norbert Stuhrmann schrieb:

Vielen Dank! Könnte man bspw. Spice für einen Test des eigenen Ergebnisses benutzen, wenn man eine entsprechende Verbindungsliste erzeugt? Und zwar auch noch für Netzwerke mit ca. 10.000 Widerständen unregelmäßig angeordnet?

Gruß, Arne

Reply to
Arne Luellmann

"Arne Luellmann" schrieb im Newsbeitrag news:e0ddep$2p0h$ snipped-for-privacy@gwdu112.gwdg.de...

Maschen-

d.h.

Hallo Arne,

SPICE sollte das problemlos können.

Ein gutes und trotzdem kostenloses SPICE-Programm ist LTspice/SwitcherCADIII. Es hat keienrlei Begrenzung der Schaltungsgröße und hat eine graphische Schaltplaneingabe, kann aber auch direkt Netzlisten verarbeiten. Also mit ein paar tausend Widerständen habe ich schon mal mit LTspice simuliert.

formatting link

Falls du Probleme mit dem Programm hast, dann kannst du in der User-Group nachfragen.

formatting link

Gruß Helmut

Reply to
Helmut Sennewald

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.