www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de