Les graphes et internet

Relier des noeuds avec des arêtes

Soit un reseau constitué de 6 machines, que l’on symbolisera par 6 ronds A, B ,C ,D, E et F.

Quels sont les avantages et inconvénients de chacun des graphes constuits sur le cahier (complets, en étoile, circulaires en particulier) en termes de fiabilité, de coût.

Questions:

• Quel graphe est le plus fiable?

• Avec le graphe complet ( tous les sommets reliés à toutes les arêtes): exprimer le nombre d’arêtes en fonction du nombre de sommets
• calculer ainsi le nombre d’arêtes d’un graphe complet de 10, puis 20 sommets à l’aide d’un tableau .
• calculer le nombre de connections qu’il faudrait pour relier directement chacun des 3 milliards d’internautes(chiffrede2015) )

Definitions et remarques:

• Un graphe est un ensemble d’arêtes et de sommets. Ces sommets peuvent constituer des noeuds s’ils sont reliés à d’autres sommets par une arête.
• Deux sommets sont voisins s’ils sont reliés par une arête.
• Le degré d’un sommet dans un graphe est son nombre de voisins.
• Un graphe est dit connexe s’il est en un seul morceau.
• Un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux.
• Un chemin entre 2 sommets d’un graphe est le parcours qui relie ces 2 sommets. On peut présenter le parcours en énonçant les sommets traversés, ou bien les arêtes empruntées.
• La longueur du chemin est égale au nombre d’arêtes empruntées.
• il est illusoire d’imaginer que toutes les machines sur internet sont reliées 2 à 2 selon un graphe complet.
• Les données echangées doivent donc transiter selon un chemin avec de nombreux sauts, de routeur en routeur.

Enoncé du premier problème sur les graphes

Le problème des sept ponts de Königsberg est connu pour être à l'origine de la topologie et de la théorie des graphes. Résolu par Leonhard Euler en 1735, ce problème mathématique se présente de la façon suivante :

il y a une île appelée le Kneiphof, entourée d’un fleuve qui se partage en 2 bras. Les bras de ce fleuve sont garnis de 7 ponts

Il est possible de vérifier, de manière intuitive, que la promenade demandée n’existe pas. Ce sont au moins deux ponts, bien choisis, qu’il faudrait ajouter ou retirer pour permettre la promenade avec retour initialement cherchée.

Questions:

• Que modélisent les noeuds du graphe?

• Que modélisent les arêtes du graphe?
• Vérifier que cette promenade n’existe pas.
• Modifier le plan des ponts (avec un nombre minimum de ponts ajoutés) pour rendre cette balade possible.
• Que remarque t-on alors sur la parité du nombre d’arêtes pour chacun des noeuds?

Modélisation

Euler propose une modélisation qui consiste à désigner chacune des berges par une lettre majuscule, les ponts par une lettre minuscule et à étudier l’existence de listes d’une taille donnée de lettres majuscules. Par exemple, sur la figure précédente, la liste CABD peut correspondre à un parcours de la berge C à la berge A par le pont e, puis de A vers B par le pont a, puis de B vers D par f.

L’impossibilité de passer deux fois par le même pont se traduit par l’impossibilité qu’une liste comporte plus de fois la séquence XY ou Y X qu’il n’existe de ponts entre les berges X et Y.

Pour Euler, une solution est une liste comportant exactement une lettre de plus qu’il n’y a de ponts, et répondant aux contraintes précédentes.

Testez le vous-même:

• Repérer les berges par des noms de sommet (A, B, C, D). Et représenter les parcours possibles comme une liste de sommets atteints, en n’empruntant qu’une seule fois chaque pont.

• Constater alors que la liste-solution n’existe pas.

Euler propose ensuite une règle pour répondre au problème général de promenades sur des ponts : Un parcours eulérien est possible si, et seulement si, deux régions au plus ont un nombre impair de ponts y conduisant. Si deux régions ont un nombre impair de ponts y conduisant, le parcours commencera par l’une de ces deux régions.

Où sont les graphes?

La théorie des graphes a connu un essor important et a permis de modéliser de nombreux problèmes:

• Le problème hamiltonien, qui peut paraître proche du problème eulérien. Il s’énonce ainsi : Existe-t-il un chemin ou un circuit passant par tous les sommets d’un graphe une et une seule fois ? Ce problème n’a pas de solution générale aujourd’hui.
• Le théorème des 4 couleurs : Énoncé en 1852 par Francis Guthrie, ce problème a été résolu à la fin du vingtième siècle. Dans sa première forme, il s’énonçait ainsi : peut- on colorier avec quatre couleurs une carte géographique de telle façon que deux régions limitrophes aient une couleur différente? Voir resolution ici: villemin.gerard.free.fr

Les algorithmes développés par les mathématiciens discrets se prêtent bien à l’implémentation informatique, dans la mesure où le graphe est un objet discret aisément représentable de façon matricielle ou par listes chaînées par exemple.

• Si le graphe modélise un réseau (les sommets représentant les sites et les arêtes les liens de communication): voir ci-dessous.

• Si le graphe est un plan de métro,

  • quel est le nombre minimal de changements entre deux stations données ?
  • quelles sont les stations que l’on peut rejoindre à partir d’une station donnée, avec un changement au plus ?

Quels problèmes peuvent resoudre les graphes pour Internet

La modélisation en graphe du reseau internet peut répondre aux questions:

• tous les noeuds du graphe sont-ils accessibles? deux sites donnés peuvent-ils communiquer ?
• Quels sont les chemins possibles pour relier 2 noeuds A et B?
• Si l’un des chemins est rompu, existe t-il un autre chemin?
• Quel est le plus court chemin pour relier 2 noeuds A et B?

Toutes ces questions peuvent être résolues grâce à un algorithme de parcours de ce graphe, dont un exemple sur cette page, avec le parcours en largeur.