English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGraphes et réseauxLes graphiques au quotidien
Tout au long de ce cours, nous avons vu de nombreuses applications de la théorie des graphes, même si certaines étaient en quelque sorte artificielles. Il s'avère toutefois que les graphiques sont au cœur de nombreux objets et concepts de la vie quotidienne.
Internet, par exemple, est un vaste graphe virtuel. Chaque sommet est une page Web individuelle et chaque arête signifie qu’il existe un lien hypertexte entre deux pages. Notez que les liens ne vont que dans un sens. Ce graphique est donc
Certains sites Web, tels que Wikipedia ou Facebook, contiennent de nombreux liens entrants, alors que de nombreux sites Web plus petits peuvent ne contenir que très peu de liens entrants. C’est le concept sous-jacent utilisé par Google pour trier les résultats de recherche.
Les sites Web contenant davantage de liens entrants ont tendance à être de meilleure qualité et devraient figurer en haut des résultats de recherche. Par exemple, lors de la recherche de «Londres», les sites d’information touristique officiels sont affichés avant les petits magasins londoniens ou les blogs de personnes vivant à Londres. Cette idée simple de la théorie des graphes, l'algorithme Page Rank, a rendu Google nettement meilleur que les autres moteurs de recherche.
Internet est le plus grand réseau jamais créé par l’humanité. Cette image montre une très petite proportion de tous les serveurs connectés à Internet:
Alors que les sites Web et les hyperliens forment un graphique virtuel, il existe également le réseau physique, qui comprend des ordinateurs, des serveurs, des routeurs, des lignes téléphoniques et des câbles.
Chaque fois que vous passez un appel ou chargez un site Web, les opérateurs de réseau doivent trouver un moyen de connecter l'expéditeur et le destinataire, sans dépasser la capacité de chaque câble ou connexion. La théorie des graphes et la probabilité permettent de garantir un service fiable, par exemple en trouvant des déviations lorsqu'une connexion particulière est occupée.
Les graphiques jouent également un rôle important dans les transports et la navigation. Tous les réseaux de vol, de train et de métro forment des graphiques pouvant être utilisés pour créer des horaires efficaces. L’un des graphiques les plus reconnaissables est la carte du métro de Londres:
Toutes les routes et les autoroutes forment également un vaste réseau, qui est utilisé par les services de navigation tels que Google Maps pour établir l'itinéraire le plus court entre deux points donnés.
À l'avenir, les systèmes de transport intelligents réduiront les encombrements et les accidents en acheminant les voitures de manière plus efficace, en utilisant les données de localisation recueillies à partir de smartphones et de voitures autonomes. Cela permettrait d'économiser des millions d'heures perdues sur la route chaque année, de réduire considérablement la pollution et de permettre aux services d'urgence de voyager plus rapidement.
Cette image montre le réseau de vols de compagnies aériennes commerciales dans le nord de l'Europe.
Il existe d'innombrables autres graphiques dans la science, l'ingénierie ou la vie quotidienne:
Les liens entre les atomes de molécules et les grilles cristallines forment un graphe.
La propagation des maladies et des épidémies peut être modélisée à l'aide d'un réseau.
En Biologie, les arbres évolutifs illustrant l'ascendance des espèces forment un graphique.
Les différents composants des circuits électriques et des puces informatiques forment un réseau.
La structure grammaticale des langues peut être modélisée à l'aide de graphiques, par exemple pour créer des algorithmes de traduction.
Les graphes ont également de nombreuses applications en probabilités, en théorie des jeux et en mathématiques financières.
Réseaux sociaux
Enfin, pensons à un exemple particulièrement intéressant de graphes existant dans la vie quotidienne: les médias sociaux. Ici, les vertices représentent les
Lorsque nous commençons à dessiner des graphiques sur les médias sociaux, nous pouvons clairement voir certains groupes d'amis communs, qui peuvent être allés dans la même école ou vivre dans la même ville. Nous pouvons également déterminer la centralité d'une personne, qui dépend du degré de connexion d'un sommet et qui peut être un indicateur de la popularité d'une personne sur les réseaux sociaux.
En 2014, Facebook comptait 1,4 milliard d'utilisateurs actifs et plus de 200 milliards d'amitiés. La moitié des utilisateurs de Facebook ont plus de 200 amis et, comme la plupart de nos amis ont le même nombre d'amis, nous pourrions facilement avoir des dizaines de milliers d'amis d'amis.
Une question passionnante serait désormais la suivante: si vous choisissez deux utilisateurs de Facebook au hasard, combien «de liens d'amitié» devez-vous suivre pour aller de l'un à l'autre? Par exemple, la distance entre amis est de
Selon une étude menée par Facebook en 2016, vous êtes en moyenne connecté à quiconque sur Facebook par le biais d'au plus 3,57 personnes: nous disons qu'il existe 3,57 degrés de séparation.
En d'autres termes, si vous choisissez l'un des milliards d'utilisateurs de Facebook dans le monde entier, ils auront un ami d'un ami qui connaît un ami d'un de vos amis. Et cela inclut des célébrités, des politiciens ou des membres de la royauté…
Geographic visualisation of all Facebook friendships in 2010.
En 1929, lorsque l'auteur hongrois
En 1967,
Aujourd'hui, chacun de nous fait partie d'innombrables graphiques invisibles, qui sous-tendent nos interactions sociales, les voyages, Internet et la technologie, la science et bien plus encore.