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

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieZusammenhängender Zufallsgraph
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Graphentheorie" - Zusammenhängender Zufallsgraph
Zusammenhängender Zufallsgraph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Zusammenhängender Zufallsgraph: Lösungsansatz
Status: (Frage) beantwortet Status 
Datum: 15:25 So 20.05.2018
Autor: 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: (Antwort) fertig Status 
Datum: 01:37 Di 19.06.2018
Autor: 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: (Mitteilung) Reaktion unnötig Status 
Datum: 01:29 Mi 20.06.2018
Autor: 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
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]