L’œuvre réalisée ci-dessus est similaire à un graphe.
Un graphe est un ensemble de points (sommets) reliés par des traits (arêtes).

Les graphes ont servi à résoudre le problème des 7 ponts de Königsberg. Il y a aussi la théorie des réseaux qui est une étude de graphes permettant d’analyser les relations entre plusieurs personnes comme dans cette image. Par exemple, l’analyse des réseaux sociaux a pour but d’étudier les interactions sociales. Le réseau est alors modélisé en un graphe dans lequel les sommets sont les acteurs sociaux et les arêtes représentent les relations entre eux. Grâce à un simple coup d’œil, on peut visualiser l’importance des interactions au sein du réseau.

Voici un exemple de graphe bien connu dans lequel tous les sommets ne sont pas reliés par le même nombre d’arêtes : si un sommet représente une personne, chacune d’entre-elle a plus ou moins d’interactions avec les autres même si elles sont toutes rattachées par différentes chaînes (chemins). Cela nous rapproche de la théorie des 6 degrés de séparation (ou du "petit monde") qui affirme que chaque personne de la planète est reliée à toutes les autres grâce à une chaîne d’au moins 6 personnes.

Questions

• Q1 : Qu’est-ce qu’un graphe ?
• Q2 : Donner un exemple dans lequel les graphes ont servi.

Le problème des 7 ponts de Königsberg
À savoir : le degré d’un sommet correspond au nombre d’arêtes auxquelles il est relié.
Ce problème est à l’origine de la théorie des graphes. Le but est de savoir s’il est possible de trouver un chemin qui permet de traverser tous les ponts de la ville une seule fois en revenant au même point de départ.

Ce problème a été représenté par un graphe comme ci-dessus par Léonard Euler, un grand mathématicien, qui l’a résolu. Il a expliqué que, pour qu’un tel parcours existe à l’intérieur de ce graphe, il faudrait que chaque sommet soit relié à un nombre pair d’arêtes (une pour arriver au point, et une pour repartir). De même pour le point de départ qui est également le point d’arrivé. Or ce n’est pas le cas dans ce graphe. On remarque alors que, dans le problème des 7 ponts de Königsberg, c'est impossible même si l’on supprime la condition de revenir au point de départ.

Questions

• Q3 : Combien de ponts faut-il traverser dans le problème des ponts de Königsberg ?
• Q4 : Le chemin demandé est-il possible ?

La théorie des 6 degrés de séparation
Cette théorie a été établie par Frigyes Karinthy, un écrivain Hongrois, en 1929. Il explique que toute personne sur la Terre peut être reliée à n’importe qui d’autre par une chaîne de 6 personnes par l’intermédiaire des réseaux sociaux. Son étude à été modélisée par un graphe comme celui-là :

Pour confirmer cette théorie, une expérience a été menée sur un réseau social en 2011, et effectivement, il fallait moins de 5 amis intermédiaires pour réaliser une chaîne qui relie toutes les personnes. Plus les années passent, et moins il y a besoin d’avoir d’amis pour réaliser cette chaîne : 5 ans plus tard, en 2016, moins de 4 amis intermédiaires suffisaient.

Questions

• Q5 : Dans la théorie de Frigyes Karinthy, combien de personnes contient la chaîne qui permet de relier une personne avec toutes les autres ?
• Q6 : Cette théorie a-t-elle été validée grâce à l’expérience menée avec le réseau social Facebook ?

Bibliographie

• Graphe (mathématiques discrètes), Wikipédia (consulté le 15 mars 2023).
• Théorie des réseaux, Wikipédia (consulté le 15 mars 2023).
• Problème des sept ponts de Königsberg, Wikipédia (consulté le 22 mars 2023).
• Six degrés de séparation, Wikipédia (consulté le 22 mars 2023).
• Graphes, Maths-cours.fr (consulté le 30 mars 2023).
• Graphes : définitions, propriétés, Maxicours (consulté le 30 mars 2023).

Réponses aux questions

Q1 : Un graphe est un ensemble de points reliés par des arêtes.
Q2 : Les graphes ont servi dans la théorie des réseaux ou encore dans le problème des 7 ponts de Königsberg.
Q3 : Il faut traverser 7 ponts.
Q4 : Non, le chemin demandé n’est pas possible, même sans revenir au point
de départ.
Q5 : Dans sa théorie, il faut une chaîne contenant 6 personnes pour relier toutes les personnes entre elles.
Q6 : Oui, l’expérience menée avec Facebook a confirmé que 5 personnes suffisaient à relier tout le monde, et même moins.