Les développeurs informatiques

Nico intègre le club d'informatique «Olympiades». Il repère très vite qui a l'habitude de collaborer avec qui :

Pour y voir plus clair, Nico a dessiné le diagramme ci-contre, où chaque rectangle représente un développeur et chaque trait relie deux développeurs qui collaborent ensemble. Cependant, il a oublié de noter les noms des développeurs dans les rectangles. Pouvez-vous les retrouver ?

Faites glisser les noms sur les rectangles correspondants.

N'hésitez pas à utiliser un stylo et du papier brouillon pour vous aider.

Solution

Une manière d'aborder le problème consiste à repérer sur le graphe qu'il y a des cas singuliers : une seule personne n'a qu'un collaborateur, et une seule personne a 4 collaborateurs. On peut donc étudier le nombre de collaborateurs de chaque personne et repérer qui peut être l'un de ces cas singuliers pour le placer en premier.

Par exemple, on peut commencer par repérer le nom de la seule personne qui n'a qu'un seul collaborateur ; puis le placer directement. Ensuite, on peut placer le nom du collaborateur de cette personne.
Pour continuer, parmi les deux collaborateurs de cette dernière personne, l'une a un total de 3 2 collaborateurs, tandis que l'autre a un total de 4. On peut donc distinguer ces deux collaborateurs et les mettre aux bons endroits.
De même, on peut identifier les autres personnes en fonction du nombre total de leurs collaborateurs, en continuant de proche en proche.

Voici la solution complète.

C'est de l'informatique !

Le diagramme ci-dessus est appelé un « graphe ». De manière générale, un graphe sert à représenter un ensemble de « relations » entre des objets ou des personnes.

Les graphes peuvent être gigantesques, comme par exemple le graphe de Facebook qui contient plus d'un milliards de personnes, chacune ayant typiquement de l'ordre d'une centaine d'amis. Pour pouvoir récupérer des informations sur la structure de graphes aussi grands, comme par exemple pour trouver une chaîne d'amis connectant deux personnes données, il est nécessaire d'utiliser des algorithmes très efficaces.