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 Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
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: (Question) answered 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: Antwort
Status: (Answer) finished 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
                
Bezug
Zusammenhängender Zufallsgraph: Nachtrag
Status: (Statement) No reaction required Status 
Date: 01:29 Mi 20/06/2018
Author: HJKweseleit

Mir ist noch eine fast konträre Idee gekommen:

1. Baue zwischen den n Knoten alle [mm] \bruch{n(n-1)}{2} [/mm] Kanten auf, so dass der Graph vollständig wird (Adjazenzmatrix).

Nun schießt du erlaubte Kanten ab, indem du sie auswürfelst.
2. Würfle zunächst die Anzahl der Schüsse aus, z.B eine Zahl aus [mm] 1,2,3,...\bruch{5n(n-1)}{2} [/mm] (fünffache Kantenzahl). So oft schießt du jetzt auf Kanten.

3. Solange noch Schüsse erlaubt sind, würfle zwei Knoten aus.
a) Falls dazwischen keine Kante mehr besteht, hast du einen Fehlschuss gemacht. Der zählt aber. Gehe wieder zu 3.
b) Falls dazwischen eine Kante besteht, versuche, vom ersten zum 2. Knoten über andere Wege zu gelangen, indem du alles austestest. Falls dies gelingt, lösche die Kante; andernfalls muss sie bestehen bleiben, und du hast einen Fehlschuss getan. Gehe wieder zu 3.

4. Gib den noch bestehenden Baum aus.

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


Alle Foren
Status 4h 07m ago 4. angela.h.b.
SGeradEbene/Abstand eines Punktes
Status 9h 57m ago 3. HJKweseleit
GraphTheo/Zusammenhängender Zufallsgraph
Status 15h 05m ago 6. HJKweseleit
ULinAAb/Kern und Bild bestimmen
Status 19h 38m ago 5. Dom_89
DiffGlGew/Lösung der DGL
Status 20h 33m ago 4. Dom_89
SGeradEbene/Parallele Ebenen
^ Seitenanfang ^
www.mathspace.org
[ Home | Forum | Knowledge | Courses | Members | Team | Contact ]