Re: Wieviele Verbindungen gibt es bei x Punkten?
Zitat:
Delphi-Quellcode:
1 + 2 + 3 + 4 + ... + (n-1) + n = (n-1)*n div 2
//ist schliesslich (fast) das gleiche wie Verbindungen := 0; for i := 1 to n do Verbindungen := Verbindungen +(i - 1); Zitat:
(Edit:) Also bei N Punkten, immer N-1 Kanten... |
Re: Wieviele Verbindungen gibt es bei x Punkten?
Och, da will ich auch mal meinen Senf zu geben:
1. Ob A-B = B-A ist, hängt von der Aufgabenstellung ab, wenn A z.B. auf einem Berg liegt, ist es sehr wohl wichtig. 2. Was hier gesucht wird ist die Anzahl von Spanning Trees eines Graphen. Vielleicht bringt das hier was http://citebase.eprints.org/cgi-bin/...org:cs/0502038 |
Re: Wieviele Verbindungen gibt es bei x Punkten?
@rascalpo: ja genau, das stimmt allerdings
also: bei n punkten gibt es genau n-1 kanten, wobei jedoch alle puntke durch ein zusammenhängendes netz verbunden sein müssen. ich glaub wir sind schon ein minimales stück weitergekommen, hab aber trotzdem noch keine formel/ergebnis :) @alzaimar: der link geht ins leere. :( |
Re: Wieviele Verbindungen gibt es bei x Punkten?
Zitat:
|
Re: Wieviele Verbindungen gibt es bei x Punkten?
hm.. dieses Problem hat irgendwie Ähnlichkeiten zu MISSISSIPPI (Permutation aus einer Menge mit Wiederholung..)
also, mal angenommen, bei einem Knoten existieren zwar mehrere Verbindungen, aber nur eine davon wird weiterverfolgt(so wie bei deiner Skizze das untere Beispiel A-C-E-F) und wie immer hat er bei N Knoten genau N-1 Kanten. und manchmal hat ein Punkt nur eine Verbindung zum nächsten, manchmal aber auch 2 und manchmal 3 und vielleicht auch 4. vom Anfangpunkt aus gesehen könntest du die Verbindungen nacheinander aufschreiben... die Verbindung A-B-C-D-E würde 1 1 1 1 geschrieben werden A-B-E-C-D: 1 1 1 1 // 1+1+1+1 = 4*1 = 4 = 5-1 = N-1 und davon gäbe es N! Möglichkeiten, wobei die Summe der einzelnen Verbindungen immer N-1 wäre. weiter beispiele:
Delphi-Quellcode:
die Anzahl der möglichen Verbindungs-Kombinationen (nur Verbindungen! und immer nur eine weitergeführte richtung!) wäre erstmal, alle möglichen "Auflösungen" zu finden...
| C
| | | A-B-D-E 1 2 1 = 4 B D F | \|/ N=9 | C A-C-E // 1 7 = 8 | | /|\ | A-B-D 1 3 = 4 G H I | | | E | bei N=5 1 1 1 1 // hie 4! div 4! möglichkeiten 1 1 2 // hier wären 3! div 2! möglichkeiten.... 1 3 // 2! 2 2 // 2! div 2! 4 // 1!... // 4+3+1+1+1 = 10 Möglichkeiten... bei N = 6 1 1 1 1 1 // 5! div 5! 1 1 1 2 // 4! div 3! 1 1 3 // 3! div 2! 1 2 2 // 3! div 2! 1 4 // 2! 2 3 // 2! 5 // 1! // 1+4+3+3+2+2+1 = 16. .. das nur mal so als anregung. |
Re: Wieviele Verbindungen gibt es bei x Punkten?
hm. es können aber theoretisch alle knoten weiterverfolgt werden.
ich hab jetzt glaub in fachsprache das was ich bereits implementiert hab: das nennt sich glaub Minimaler Spannbaum (Minimal Spanning Tree) mit n Knoten und n-1 Kanten. (danke @alzaimar) Dabei ist es ein ungerichteter zusammenhängender Graph. Lauter neue Ausdrücke für mich, aber anscheinend ist es genau das was ich brauch. Daraus resultierend hab ich jetzt noch ne 2te implementierung von so einem spanning tree, aber weiß aber immer noch nicht, wieso es genau x möglichkeiten gibt so einen geschlossenen spannbaum zu machen. :( |
Re: Wieviele Verbindungen gibt es bei x Punkten?
Hallo,
such mal im Internet unter Graphentheorie. Dort kannst du alles nachlesen. Dort wird dieses Thema behandelt. Rainer |
Re: Wieviele Verbindungen gibt es bei x Punkten?
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:09 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz