Diskussion:Zufallsgraph

Graph-Isomorphie ist (vermutlich) nicht NP-schwer

Der Abschnitt unter "Wichtige Ergebnisse" suggeriert meiner Meinung nach, dass Graph-Isomorphie NP-schwer sei. Tatsächlich wäre dies nur dann möglich wenn die polynomielle Hierarchie auf der zweiten Stufe kollabiert (laut englischer Seite zu Graph-Isomorphie: Schöning, Uwe (1987), "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, pp. 114–124; also Journal of Computer and System Sciences 37: 312–323, 1988) und damit höchst unerwartet. László Babai hat wohl sogar einen quasipolynomiellen Algorithmus dafür gefunden, ich habe aber das zugehörige Paper noch nicht gelesen. Dadurch ist der Abschnitt nicht nur nicht hinreichend mit Belegen ausgestattet, sondern inhaltlich/fachlich fehlerhaft.

Als Neuling, der mit den Richtlinien der Wikipedia noch nicht vertraut ist, wollte ich nicht gleich am Artikel herumfummeln. Wenn keiner der erfahreneren Autoren das übernimmt, denke ich hoffentlich daran, bald selbst Hand anzulegen. Kann jemand ein schönes Beispiel für ein NP-vollständiges Problem, das für Zufallsgraphen bestimmter interessanter Modelle effizient lösbar ist, vorschlagen? --Kakistocrtor (Diskussion) 21:07, 11. Jan. 2016 (CET)

Satz von Erdős

Welcher ist gemeint? Es gibt viele.--Pugo (Diskussion) 07:49, 18. Jan. 2017 (CET)

Ich hab den Link korrigiert. Ein Artikel existiert jedoch bisher nicht. --Redrobsche (Diskussion) 22:01, 16. Feb. 2017 (CET)

Verwechslung

G(n,p) ist der Erdos Graph und G(n,m) Gilbert.

Dieser Artikel ist wirklich fahrlässig schlecht. (nicht signierter Beitrag von 2A02:908:1A9:D20:6CDD:3BB9:AD76:828D (Diskussion) 06:43, 4. Jan. 2022 (CET))