matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

For pupils, students, teachers.
Hello Guest!Log In | Register ]
Home · Forum · Knowledge · Courses · Members · Team · Contact
Navigation
 Home...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Tools...
 Agency for private tuition beta...
 Online Games beta
 Search
 Registered Society...
 Contact
Forenbaum
^ Tree of Forums
Status Maths
  Status School
    Status Grades 1-4
    Status Grades 5-7
    Status Grades 8-10
    Status Grades 11-12
    Status Mathematical Contest
    Status School maths - Miscellaneous
  Status University
    Status Uni-Calculus
    Status Uni-LinA u. Algebra
    Status Algebra and Number Theoriy
    Status Discrete Mathematics
    Status Teaching Methodology
    Status Financial Maths and Actuarial Theory
    Status Logic and Set Theory
    Status 
    Status Stochastic Theory
    Status Topology and Geometry
    Status Uni Maths - Miscellaneous
  Status Courses on maths
    Status 
    Status 
    Status Universität
  Status Software for maths
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Calculators

Only forums with an interest level bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
The project is organised by our team of coordinators.
Hundreds of members help out in our moderated forums.
Service provider for this webpage is the Registered Society "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Graph Theory" - Zusammenhängender Zufallsgraph
Zusammenhängender Zufallsgraph < Graph Theory < Discrete Mathematics < University < Maths <
View: [ threaded ] | ^ Forum "Graphentheorie"  | ^^ all forums  | ^ Tree of Forums  | materials

Zusammenhängender Zufallsgraph: Lösungsansatz
Status: (Frage) überfällig Status 
Date: 15:25 So 20/05/2018
Author: SimpleDude

Aufgabe
Zeigen Sie wie man einen zusammenhängenden Zufallsgraphen erzeugt. Das bedeutet, alle Kanten werden zufällig erzeugt. Es muss jedoch von jedem Knoten zu jedem anderen Knoten mindestens eine mögliche Route geben. (Es ist kein formaler Beweis erforderlich, eine lückenlos nachvollziehbare Beschreibung ist ausreichend.)

Aktuelles Thema sind ungerichtete Graphen, also sind die Kanten auch ungerichtet.

Ich habe schon versucht etwas in Python zu programmieren, aber viel weiter als Zufallsgraph der nur zufällig zusammenhängend wird bin ich noch nicht gekommen.

Habe mich auch schon über Gilbert-Graph und Erdos-Renyi-Graph informiert, aber die scheinen auch nur darauf ausgelegt zu sein, dass die Eigenschaft "Zusammenhang" zufällig entsteht oder auch nicht.

Kennt jemand einen Algorithmus oder kann mir zumindest einen Ansatzpunkt geben, wie man einen zusammenhängenden Zufallsgraphen erzeugt?

Irgendetwas nach dem Motto
1. erzeuge Zufallsgraph
2. falls nicht zusammenhängend gehe zu 1.
erscheint mir irgendwie nicht im Sinne der Aufgabenstellung.

Erst einen Zufallsgraphen erzeugen und dann nach einem festen Muster nicht verbundene Knoten einbinden erscheint mir auch nicht im Sinne der Aufgabenstellung.

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Zusammenhängender Zufallsgraph: Fälligkeit abgelaufen
Status: (Statement) No reaction required Status 
Date: 19:44 Mi 06/06/2018
Author: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Zusammenhängender Zufallsgraph: Mitteilung
Status: (Statement) No reaction required Status 
Date: 01:37 Di 19/06/2018
Author: HJKweseleit

Da das Forum für den Normalsterblichen erst jetzt wieder freigegeben wurde, kann ich leider erst jetzt antworten.

1. Schritt: Nummeriere alle Knoten von 1 bis n durch.
2. Schritt: Setze für alle Knoten einen Wert mit der Bedeutung "noch nicht dabei"
3. Würfle eine beliebige Zahl als Startzahl aus, trage sie in eine Liste a ein und setze ihren Wert auf die Bedeutung "ist dabei"
4. Setze einen Zähler auf 1. (Anzahl der schon vorhandenen Knoten im Netz)
5. Würfle eine beliebige Zahl x aus a und eine beliebige andere Zahl y. Trage die Verbindung xy als Kante in eine Liste ein (z.B. Matrix).
Falls y noch nicht dabei war, erhöhe den Zähler um 1.
Setze den Wert von y auf "ist dabei".
6. Falls der Zähler <n ist, gehe wieder zu 5.

Zu 5.

Nehmen wir an, du hast bereits folgende Konstellation erwürfelt:

          1 -----------3
          |            |
          |            |
          |            |
          17 ---------29

In Liste a sind also die Zahlen 1, 3, 17 und 29.
Nun würfelst du x aus der Liste, sagen wir die 17, und eine andere Zahl y.

Ist z.B. y=29, so besteht diese Kante schon. Du kannst das überprüfen oder diese erneut eintragen. Je nach Datenstruktur überschreibst du dabei nur den bisherigen Eintrag oder du hast ihn doppelt, musst dann ggf.  vor der endgültigen Ausgabe doppelten Einträge löschen (falls das so gewünscht ist).

Ist z.B. y=3, kommt eine zusätzliche Verbindung zustande, was durchaus erwünscht ist (sonst würde nur eine Kette entstehen), aber kein neuer Knoten hinzu. Deshalb bleibt der Zähler unverändert.

Ist z.B. y=49, so wird nun 17 mit 49 verbunden, 49 eingetragen als "dabei" und der Zähler um 1 erhöht. Unter den nun 5 Knoten können wieder weitere Verbindungen entstehen oder ein neuer Knoten hinzugewonnen werden.



Bemerkung: Zum Schluss entstehen sehr viele Verbindungen innerhalb des bestehenden Baumes, ohne dass ein neuer Punkt hinzukommt; der zuletzt hinzu gekommene Knoten erhält nur eine Kante, dann bricht das Verfahren ab.

Letzteres kann man abmildern, indem man nochmals eine Zufallszahl k wählt und noch k weitere Verbindungen auswürfelt.

Tatsächlich ist der Baum also nicht so ganz zufällig.





Bezug
View: [ threaded ] | ^ Forum "Graphentheorie"  | ^^ all forums  | ^ Tree of Forums  | materials


Alle Foren
Status 12m ago 6. Dom_89
UAnaRn/Extrema bestimmen
Status 1h 36m ago 1. Ataaga
SGeradEbene/Abstand eines Punktes
Status 1h 49m ago 5. Dom_89
ULinAAb/Kern und Bild bestimmen
Status 2h 14m ago 3. Dom_89
DiffGlGew/Anwenden der Substitution
Status 5h 13m ago 2. fred97
IntTheo/mehrdim. part. Int., Doppelint
^ Seitenanfang ^
www.mathspace.org
[ Home | Forum | Knowledge | Courses | Members | Team | Contact ]