Considérons un ensemble de personnes, disons Pierre, Paul et Jacques. Maintenant, donnons leur des cordes de la façon suivante : si une personne a déjà rencontré une autre, on donne à chacun une extrémité d'une même corde. Par exemple, si Pierre a déjà rencontré les deux autres, mais que ceux-ci ne se sont pas rencontrés, alors Pierre tiendra deux extrémités de cordes, l'une dont l'autre extrémité est tenue par Paul et l'autre par Jacques. Si maintenant chaque personne attache ses extrémités de cordes ensemble, et s'en va en laissant tout sur place, on obtient deux cordes reliées en un noeud. Ces ensembles de cordes et de noeuds sont ce qu'on appelle un graphe.

Lorsqu'on étudie un graphe, il semble naturel de vouloir le dessiner sur une feuille, de façon à pouvoir le regarder et s'en faire une idée. Soulignons qu'il y a un très grand nombre de façons de dessiner un graphe donné. Par exemple, celui obtenu avec Pierre, Paul et Jacques peut être dessiné comme suit (chaque noeud est représenté par un petit carré bleu, les cordes étant représentées en rouge) :             . Dans le premier et le troisième dessin, Pierre est au milieu, alors que dans le second et le quatrième il est à gauche.

Dessiner un graphe peut être beaucoup plus complexe que dans cet exemple. Supposons qu'on fasse la même chose qu'avec Pierre, Paul et Jacques, mais avec un grand nombre de personnes, disons tous les élèves d'un lycée. On obtient à nouveau un ensemble de cordes et de noeuds, c'est-à-dire un graphe, mais cette fois il est beaucoup plus grand, et il est beaucoup plus difficile de s'y retrouver. Dans ce cas, comment positionner les noeuds et comment dessiner les cordes ? Par exemple, peut-on dessiner ce graphe de façon à ce qu'il n'y ait pas de croisements de cordes ? On peut même se poser une question générale sur les graphes : peut-on dessiner n'importe quel graphe de façon à ce qu'aucune des cordes qui le compose n'en croise une autre ? La réponse à cette question est négative. C'est par exemple impossible pour le graphe suivant : . À votre avis, est-ce qu'il existe des graphes plus petits (c'est-à-dire avec moins de noeuds) qu'on ne peut pas dessiner sans croisements ?

Les graphes sont parmi les objets les plus importants des mathématiques et de l'informatique. En effet, ils ne sont rien d'autre que la formulation mathématique de la notion de relation : dès qu'il y a des relations entre des objets, des gens, des concepts, ou quoi que ce soit, il y a un graphe. Nous en avons vu un exemple simple ci-dessus : le graphe des gens qui se sont déjà rencontrés. On peut aussi considérer le graphe des gens qui travaillent ensemble, par exemple. Dans l'image présentée ici, chaque noeud correspond à un chercheur d'un laboratoire, et on a mis une corde entre deux chercheurs s'ils ont écrit un article ensemble (avec encore d'autres chercheurs, éventuellement). On peut aussi construire le graphe des villes qui sont reliées par une route, ou le graphe des interactions entre les atomes d'une molécule, ou encore le graphe des relations de descendance entre les animaux, etc, etc. Toutes ces notions, ces relations, peuvent être vues comme des graphes, et les problèmes qu'on arrivera à résoudre sur les graphes (comme le problème du dessin) ont du sens dans tous ces contextes.

Quand on considère un grand graphe, comme celui issu de notre exemple des élèves d'un lycée qui se sont déjà rencontrés, on se retrouve face à un grand nombre de cordes qui sont attachées les unes aux autres dans le désordre le plus complet... Est-ce vraiment le désordre ? Certes, on obtient un gros fouilli de cordes, mais n'y a-t-il pas de l'ordre là-dedans ? En d'autres termes, est-ce que ce graphe est construit n'importe comment, comme un tas de cordes que nous aurions reliées au hasard ? Certainement pas !

Par exemple, dans le graphe des chercheurs qui ont écrit un article ensemble, que peut-on remarquer ? Tout d'abord, si un chercheur appelé Pierre a écrit un article avec un chercheur nommé Paul, ça veut dire qu'ils travaillent sur des sujets voisins. Si Paul a également écrit un article avec un troisième chercheur, Jacques, alors le même raisonnement laisse penser que Paul et Jacques travaillent sur des sujets qui se ressemblent. Mais alors, tout ceci implique que Pierre et Jacques travaillent probablement sur des sujets proches, et par consequent il y a de bonnes chances qu'ils écrivent un article ensemble un jour ! En d'autres termes, le fait qu'il y ait une corde entre Pierre et Paul et une autre entre Pierre et Jacques implique qu'il y en a probablement une entre Paul et Jacques. C'est pour ça qu'il y a beaucoup de triangles dans le dessin de graphe ci-dessus !

On peut aller plus loin dans l'observation de ce graphe. Par exemple, on voit sur le dessin qu'il y a par endroits des paquets de noeuds et de cordes concentrés : il y a des petits groupes de chercheurs qui travaillent beaucoup ensemble (on appelle un tel ensemble une communauté). D'un autre côté, il y a des chercheurs qui travaillent avec beaucoup de personnes qui, elles, ne travaillent pas ensemble : ce sont des chercheurs qui travaillent sur beaucoup de sujets différents (ils sont pluridisciplinaires). Il y a aussi des petits groupes de chercheurs qui travaillent entre eux sans jamais travailler avec les autres : ce sont les parties du graphe qui ne sont pas reliées aux autres. Il y a aussi des chercheurs qui sont les seuls à être reliés à deux communautés données. Ce sont généralement des chercheurs qui font le lien entre deux thématiques de recherche différentes. On peut imaginer aller encore plus loin de cette façon, par exemple en cherchant les grands thèmes de recherche du laboratoire, ou encore en identifiant les personnes qui sont essentielles pour la cohésion de l'ensemble. C'est fou tout ce qu'un graphe peut nous apprendre ! Voyez-vous d'autres choses qu'on peut deviner sur le fonctionnement du laboratoire simplement en regardant le graphe ?

Matthieu Latapy, août 2002.

Commentaires bienvenus : matthieu.latapy@lip6.fr