AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Wieviele Verbindungen gibt es bei x Punkten?

Wieviele Verbindungen gibt es bei x Punkten?

Ein Thema von StefanDP · begonnen am 22. Aug 2005 · letzter Beitrag vom 24. Aug 2005
Antwort Antwort
Seite 3 von 3     123
rascalpo

Registriert seit: 7. Aug 2005
11 Beiträge
 
Delphi 5 Professional
 
#21

Re: Wieviele Verbindungen gibt es bei x Punkten?

  Alt 23. Aug 2005, 19:42
Zitat:
(n-1)*n/2
daran könnte durchaus was dran sein, denn
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:
es muss auch nicht die "dauer" möglichst kurz sein, sondern die gesamtsumme aller einzelverbindungen (also quasi die länge des netztes)
okay, was ist aber, wenn die Anzahl der Kanten immer gleich bleibt????
(Edit Also bei N Punkten, immer N-1 Kanten...
Des Pudels wahrer Kern...
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#22

Re: Wieviele Verbindungen gibt es bei x Punkten?

  Alt 23. Aug 2005, 20:33
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
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
StefanDP

Registriert seit: 11. Apr 2004
294 Beiträge
 
#23

Re: Wieviele Verbindungen gibt es bei x Punkten?

  Alt 23. Aug 2005, 21:12
@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.
  Mit Zitat antworten Zitat
Claas M

Registriert seit: 23. Aug 2005
5 Beiträge
 
Delphi 2005 Personal
 
#24

Re: Wieviele Verbindungen gibt es bei x Punkten?

  Alt 23. Aug 2005, 21:34
Zitat von StefanDP:
also: bei n punkten gibt es genau n-1 kanten, wobei jedoch alle puntke durch ein zusammenhängendes netz verbunden sein müssen.
Wenn du jeden Punkt mit den anderen verbindest, stimmt n*(n-1). Ergibt auch ein Gitter, zeichne es mal auf. So, wenn nun aber nicht zwischen A-B oder B-a unterschieden wird, musst du das ganze halbieren. Ich sähe keine andere Lösung bei deiner Beschreibund.
  Mit Zitat antworten Zitat
rascalpo

Registriert seit: 7. Aug 2005
11 Beiträge
 
Delphi 5 Professional
 
#25

Re: Wieviele Verbindungen gibt es bei x Punkten?

  Alt 23. Aug 2005, 23:41
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:
| 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
|
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...
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.
Des Pudels wahrer Kern...
  Mit Zitat antworten Zitat
StefanDP

Registriert seit: 11. Apr 2004
294 Beiträge
 
#26

Re: Wieviele Verbindungen gibt es bei x Punkten?

  Alt 24. Aug 2005, 00:50
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.
  Mit Zitat antworten Zitat
runger
(Gast)

n/a Beiträge
 
#27

Re: Wieviele Verbindungen gibt es bei x Punkten?

  Alt 24. Aug 2005, 07:17
Hallo,

such mal im Internet unter Graphentheorie. Dort kannst du alles nachlesen.
Dort wird dieses Thema behandelt.

Rainer
  Mit Zitat antworten Zitat
runger
(Gast)

n/a Beiträge
 
#28

Re: Wieviele Verbindungen gibt es bei x Punkten?

  Alt 24. Aug 2005, 07:20
Hallo

Graphentheorie

Dort findest du die Theorie dazu!

Rainer
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:40 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