www.wikidata.de-de.nina.az

Zufallsgraph Ein bezeichnet einen Graphen bei dem die Kanten zufällig erzeugt werden Häufig eingesetzte Modelle zufällig

Zufallsgraph

Ein Zufallsgraph bezeichnet einen Graphen, bei dem die Kanten zufällig erzeugt werden. Häufig eingesetzte Modelle zufälliger Graphen sind:

  • Das Gilbert-Modell (benannt nach Edgar Gilbert): mit einer natürlichen Zahl , der Zahl der Knoten, und einer Wahrscheinlichkeit bezeichnet die Menge aller Graphen, bei denen für jedes geordnete Paar von Knoten, mit , mit der Wahrscheinlichkeit bestimmt wird, ob sie durch eine Kante verbunden werden, und das unabhängig von den anderen Kanten. Man untersucht dann häufig, mit welcher Wahrscheinlichkeit die erzeugten Graphen eine bestimmte Eigenschaft haben, z. B. ob sie zusammenhängend sind. Eine weitere Möglichkeit ist es, in Abhängigkeit von vorzugeben und dann das Verhalten bei wachsendem zu untersuchen.
Realisierung des Gilbert-Graphen
  • Das Erdős-Rényi-Modell (benannt nach Paul Erdős und Alfréd Rényi): mit natürlichen Zahlen und bezeichnet die Menge aller Graphen mit exakt Knoten und Kanten.
  • Die Knoten des Graphen werden in der Ebene gemäß einer vorgegebenen Wahrscheinlichkeitsverteilung verteilt. Wenn zwei Knoten einen Abstand kleiner als eine vorgegebene Grenze haben, werden sie durch eine Kante verbunden.
  • Auf einer abzählbaren Knotenmenge kann jede Kante unabhängig und mit Wahrscheinlichkeit gewählt werden – durch diese Konstruktion entsteht fast sicher der Rado-Graph.

Fragestellungen Bearbeiten

Wichtige Fragestellungen bei zufälligen Graphen sind:

  • Gegeben eine Eigenschaft , für welche bzw. und ab welcher Graphengröße besitzen alle Graphen die Eigenschaft ?
  • Gegeben eine Eigenschaft , geht die Wahrscheinlichkeit für gegen 1 oder 0 für ? Man sagt dann auch, fast alle oder fast gar keine Graphen erfüllen die Eigenschaft (siehe auch hier).

Wichtige Ergebnisse Bearbeiten

Durch Anwendung der probabilistischen Methode auf sein Zufallsgraphenmodell bewies Paul Erdős den Satz: Für jede natürliche Zahl gibt es einen Graphen, bei dem sowohl Taillenweite (Länge des kürzesten Kreises) als auch Chromatische Zahl größer als k sind.

Im selben Zufallsgraphenmodell konnte gezeigt werden, dass Isomorphie zu einem beliebigen Graphen für fast alle Graphen in linearer Zeit entscheidbar ist.

Literatur Bearbeiten

  • Douglas B. West: Introduction to Graph Theory. Prentice Hall, Upper Saddle River, N.J. 1996, ISBN 0-13-227828-6.

Einzelnachweise Bearbeiten

  1. E. N. Gilbert: Random graphs, Annals of Mathematical Statistics, Band 30, 1959, S. 1141–1144
  2. P. Erdős, A. Rényi: On Random Graphs I, Publ. Math. Debrecen 6, 1959, S. 290–297
  3. Reinhard Diestel, Graphentheorie, Berlin, Heidelberg, New York: Springer, 3. Auflage 2006, S. 256ff.
  4. Babai, László, Paul Erdös, und Stanley M. Selkow. "Random graph isomorphism." Society for Industrial and Applied Mathematics Journal on Computing 9.3 (1980): 628-635.online
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Zufallsgraph bezeichnet einen Graphen bei dem die Kanten zufallig erzeugt werden Haufig eingesetzte Modelle zufalliger Graphen sind Das Gilbert Modell benannt nach Edgar Gilbert 1 G n p displaystyle G n p mit einer naturlichen Zahl n 1 displaystyle n geq 1 der Zahl der Knoten und einer Wahrscheinlichkeit 0 p 1 displaystyle 0 leq p leq 1 bezeichnet die Menge aller Graphen bei denen fur jedes geordnete Paar v 1 v 2 displaystyle v 1 v 2 von Knoten mit v i n displaystyle v i leq n mit der Wahrscheinlichkeit p displaystyle p bestimmt wird ob sie durch eine Kante verbunden werden und das unabhangig von den anderen Kanten Man untersucht dann haufig mit welcher Wahrscheinlichkeit die erzeugten Graphen eine bestimmte Eigenschaft haben z B ob sie zusammenhangend sind Eine weitere Moglichkeit ist es p p n displaystyle p p n in Abhangigkeit von n displaystyle n vorzugeben und dann das Verhalten bei wachsendem n displaystyle n zu untersuchen Realisierung des Gilbert Graphen G 20 0 1 displaystyle G 20 0 1 Das Erdos Renyi Modell benannt nach Paul Erdos und Alfred Renyi 2 G n m displaystyle G n m mit naturlichen Zahlen n 1 displaystyle n geq 1 und m 0 displaystyle m geq 0 bezeichnet die Menge aller Graphen mit exakt n displaystyle n Knoten und m displaystyle m Kanten Die Knoten V displaystyle V des Graphen G displaystyle G werden in der Ebene gemass einer vorgegebenen Wahrscheinlichkeitsverteilung f displaystyle f verteilt Wenn zwei Knoten v 1 v 2 displaystyle v 1 v 2 einen Abstand kleiner als eine vorgegebene Grenze d displaystyle d haben werden sie durch eine Kante verbunden Auf einer abzahlbaren Knotenmenge kann jede Kante unabhangig und mit Wahrscheinlichkeit 1 2 displaystyle tfrac 1 2 gewahlt werden durch diese Konstruktion entsteht fast sicher der Rado Graph Fragestellungen BearbeitenWichtige Fragestellungen bei zufalligen Graphen sind Gegeben eine Eigenschaft Q displaystyle Q nbsp fur welche p displaystyle p nbsp bzw m displaystyle m nbsp und ab welcher Graphengrosse n displaystyle n nbsp besitzen alle Graphen die Eigenschaft Q displaystyle Q nbsp Gegeben eine Eigenschaft Q displaystyle Q nbsp geht die Wahrscheinlichkeit fur Q displaystyle Q nbsp gegen 1 oder 0 fur n displaystyle n rightarrow infty nbsp Man sagt dann auch fast alle oder fast gar keine Graphen erfullen die Eigenschaft Q displaystyle Q nbsp siehe auch hier Wichtige Ergebnisse BearbeitenDurch Anwendung der probabilistischen Methode auf sein Zufallsgraphenmodell bewies Paul Erdos den Satz Fur jede naturliche Zahl k displaystyle k nbsp gibt es einen Graphen bei dem sowohl Taillenweite Lange des kurzesten Kreises als auch Chromatische Zahl grosser als k sind 3 Im selben Zufallsgraphenmodell konnte gezeigt werden dass Isomorphie zu einem beliebigen Graphen fur fast alle Graphen in linearer Zeit entscheidbar ist 4 Literatur BearbeitenDouglas B West Introduction to Graph Theory Prentice Hall Upper Saddle River N J 1996 ISBN 0 13 227828 6 Einzelnachweise Bearbeiten E N Gilbert Random graphs Annals of Mathematical Statistics Band 30 1959 S 1141 1144 P Erdos A Renyi On Random Graphs I Publ Math Debrecen 6 1959 S 290 297 Reinhard Diestel Graphentheorie Berlin Heidelberg New York Springer 3 Auflage 2006 S 256ff Babai Laszlo Paul Erdos und Stanley M Selkow Random graph isomorphism Society for Industrial and Applied Mathematics Journal on Computing 9 3 1980 628 635 online Abgerufen von https de wikipedia org w index php title Zufallsgraph amp oldid 227795253