2006 | OriginalPaper | Buchkapitel
Zufällige Graphen
verfasst von : Amin Coja-Oghlan, Michael Behrisch
Erschienen in: Informatik
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Wie verbreiten sich Viren im Internet? Warum haben einige meiner Freunde viel mehr Freunde als ich? Mit wie vielen Klicks komme ich von einer beliebigen Webseite zu einer anderen? Und wie sieht das in zehn Jahren aus? Wie konstruiert man gute fehlerkorrigierende Codes, mit denen man Nachrichten effizient codieren und decodieren kann? Wieviele zusammenhängende Graphen mit einer bestimmten Knoten- und Kantenzahl gibt es? Wie generiert man aussagekräftige Testinstanzen für Algorithmen? — Fragen dieser Art motivieren die Untersuchung zufälliger Graphen. In diesem Artikel skizzieren wir, wie sich die Theorie derselben von einem reinen Hilfsmittel für mathematische Existenzbeweise zu einem mächtigen Werkzeug entwickelt hat, dessen Anwendungen in der Informatik von der Analyse von Algorithmen bis zur Beschreibung des Internets reichen.