English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGraphen und NetzwerkeGraphen im Alltag
In den vorhergehenden Kapiteln haben wir viele verschiedene Anwendungen der Graphentheorie kennen gelernt, auch wenn einige von ihnen ein wenig konstruiert waren. Es stellt sich jedoch heraus, dass Graphen die Grundlage vieler Gegenstände, Konzepte und Prozesse des täglichen Lebens bilden.
Das Internet, zum Beispiel, ist ein riesiger, virtueller Graph. Jeder Knoten ist eine einzelne Webseite, und jede Kante bedeutet, dass es einen Hyperlink zwischen zwei Seiten gibt. Beachte, dass Links nur in eine Richtung gehen, also ist dieser Graph
Einige Websites, wie Wikipedia oder Facebook, haben viele eingehende Links, während viele kleinere Websites möglicherweise nur sehr wenige eingehende Links haben. Das ist übrigens das Konzept, nach dem Google seine Suchergebnisse sortiert.
Websites mit mehr eingehenden Links sind in der Regel von höherer Qualität und sollten in den Suchergebnissen ganz oben angezeigt werden. Wenn man zum Beispiel nach "London" sucht, werden offizielle Touristeninformationen vor kleinen Geschäften in London oder Blogs von Leuten, die in London leben, angezeigt. Diese einfache Idee aus der Graphentheorie, der PageRank-Algorithmus, führte dazu, dass Google viel besser war als andere frühe Suchmaschinen.
Das Internet ist das größte Netzwerk, das je von Menschenhand geschaffen wurde. Dieses Bild zeigt einen sehr kleinen Teil aller an das Internet angeschlossenen Server:
Während Webseiten und Hyperlinks einen virtuellen Graphen bilden, gibt es auch ein wirkliches Netzwerk von Computern, Servern, Routern, Telefonleitungen und Kabeln.
Jedes Mal, wenn du telefonierst oder eine Webseite aufrufst, müssen die Netzbetreiber einen Weg finden, Sender und Empfänger zu verbinden, ohne die Kapazität jedes einzelnen Kabels oder jeder einzelnen Verbindung zu überschreiten. Mit Hilfe der Graphentheorie und der Wahrscheinlichkeitsrechnung kann ein zuverlässiger Betrieb garantiert werden, indem beispielsweise Umleitungen gefunden werden, wenn eine bestimmte Verbindung besetzt ist.
Graphen spielen auch im Transport- und Verkehrswesen eine wichtige Rolle. Alle Flug-, Zug- und U-Bahn-Netze bilden Graphen, die bei der Erstellung effizienter Fahrpläne verwendet werden können. Einer der bekanntesten Graphen ist die Karte der Londoner U-Bahn:
Auch alle Straßen und Autobahnen bilden ein großes Netzwerk, das von Navigationsdiensten wie Google Maps verwendet wird, um die kürzeste Route zwischen zwei bestimmten Punkten zu ermitteln.
In Zukunft werden Intelligente Transportsysteme Staus und Unfälle reduzieren, da Autos mit Hilfe von Standortdaten, die von Smartphones und selbstfahrenden Autos gesammelt werden, effizienter geleitet werden können. Dadurch könnten jedes Jahr Millionen von Stunden, die auf der Straße verloren gehen, eingespart, die Umweltverschmutzung erheblich reduziert und Notfalldienste rascher werden.
Dieses Bild zeigt das Netzwerk kommerzieller Fluglinienflüge durch Nordeuropa.
Es gibt unzählige andere Graphen in Wissenschaft, Technik oder im Alltag:
Die Verbindungen zwischen Atomen in Molekülen und Kristallgittern bilden einen Graphen.
Die Ausbreitung von Krankheiten und Epidemien kann mithilfe eines Netzwerks modelliert werden.
In der Biologie bilden die Evolutionsbäume, die die Abstammung von Arten zeigen, einen Graphen.
Die verschiedenen Bestandteile von Stromkreisen und Computerchips bilden ein Netzwerk.
Die grammatikalische Struktur von Sprachen kann mithilfe von Graphen modelliert werden, um beispielsweise Übersetzungsalgorithmen zu erstellen.
Graphen haben auch viele Anwendungen in der Wahrscheinlichkeitsrechnung, Spieltheorie und Finanzmathematik.
Soziale Netzwerke
Zum Schluss wollen wir uns noch ein besonders gutes Beispiel für Graphen aus dem täglichen Leben ansehen: Soziale Medien. Hier repräsentieren Knoten
Wenn wir Graphen zu sozialen Medien zeichnen, sehen wir unter Umständen bestimmte Häufungen bei gemeinsamen Bekannten, die vielleicht in die gleiche Schule gehen oder in der gleichen Stadt leben. Wir können auch bestimmen, wie sehr jemand im Mittelpunkt steht, was davon abhängt, wie gut ein Knoten mit dem anderen verbunden ist, und somit ein Maß für die Popularität in Sozialen Medien sein kann.
Im Jahr 2014 hatte Facebook 1,4 Milliarden aktive Nutzer und insgesamt mehr als 200 Milliarden Freundschaften. Die Hälfte aller Facebook-Nutzer hat mehr als 200 Freunde, und da die meisten unserer Freunde eine ähnliche Anzahl von Freunden haben, könnten wir leicht Zehntausende von Freunden von Freunden haben.
Eine spannende Frage wäre nun: Wenn du zwei zufällige Facebook-Nutzer auswählst, wie viele „Freundschaftskanten“ müsstest du entlang gehen, um von einem zum anderen zu gelangen? Beispielsweise beträgt der Abstand zwischen Freunden
Im Jahr 2016 führte Facebook eine Studie durch, um festzustellen, wie eng die Benutzer miteinander verbunden sind. Sie fanden heraus, dass du im Durchschnitt mit jedem anderen auf Facebook durch höchstens 3,57 andere Personen verbunden bist. Und dazu gehören Berühmtheiten, Politiker oder sogar Könige!
Mit anderen Worten: Wenn du einen der Milliarden Facebook-Nutzer auf der ganzen Welt auswählst, dann wird dieser wahrscheinlich einen Freund eines Freundes haben, der einen Freund von einem deiner Freunde kennt. Man sagt, der Grad der Trennung beträgt 3,57.
Geografische Darstellung aller Facebook-Freundschaften im Jahr 2010.
Als der ungarische Autor
1967 führte
Heute ist jeder von uns Teil unzähliger unsichtbarer Graphen, die unseren sozialen Interaktionen, Reisen, Internet und Technik, Wissenschaft und vielem mehr zugrunde liegen.