Homologie d’un graphe

Dans ce post, je vais parler d’homologie (ce sera une petite introduction aux idées de l’homologie simpliciale) et de graphes. En particulier un des objectifs est de prouver par des “méthodes homologiques” la propriété suivante :

Proposition : Soit un graphe connexe, qui a sommets (pour “vertex” en anglais) et arêtes (pour “edge” en anglais). Alors .

On peut le prouver relativement facilement par récurrence; je vais vous proposer une preuve plus compliquée et qui a l’air plus alambiquée, mais qui me semble conceptuellement plus intéressante qu’une preuve par récurrence où on ne comprend pas forcément “ce qui se passe”.  Et puis cette preuve plus compliquée permet de découvrir un peu l’homologie, c’est un “exemple bébé” d’homologie (voire de topologie algébrique) – elle permettra de compter les “trous” d’un graphe !

Déjà mettons nous d’accord sur ce qu’est un graphe. Pour les besoins de ma preuve, il faudra qu’un graphe soit orienté, i.e. chaque arête sait d’où elle part et vers où elle va. Au vu de l’énoncé, ça ne change rien au résultat (si on a un graphe non orienté, on rajoute des orientations arbitraires) – si on s’entend pour dire que “connexe” ne prend pas en compte l’orientation des arêtes. Finalement, puisque ça ne change rien à la preuve et augmente la généralité, j’autorise mes graphes à avoir plusieurs arêtes entre deux sommets, et j’autorise des arêtes qui bouclent sur un sommet. Pour être sûr que ce soit clair :

Définition : Un graphe est un couple muni d’applications (pour “source” et “cible”).

représente l’ensemble des sommets du graphe, l’ensemble des arêtes, et si , est son point de départ, son point d’arrivée.

Pour définir la connexité d’une manière qui va nous simplifier la vie, on définit une relation d’équivalence sur : Si sont deux sommets, on dit que si il existe telle que . Notre relation d’équivalence est alors la relation d’équivalence engendrée par , c’est-à-dire la plus petite relation d’équivalence contenant .

Cette définition va nous simplifier la vie parce que pour montrer qu’une relation d’équivalence contient , il suffit de vérifier que est relié à pour toute arête .

On dit qu’un graphe est connexe si est la relation d’équivalence totale, i.e. pour tous .

Passons à l’homologie ! On va associer des espaces vectoriels à notre graphe .

L’idée est la suivante : si est une arête dans , on veut exprimer que ne sont pas tant différents que ça (après tout ils sont reliés par un chemin), donc on veut que leur “différence” soit nulle. Evidemment ça n’a pas de sens, on ne peut pas soustraire deux sommets. Sauf si…

Définition: Soit un graphe. On définit comme un espace vectoriel  (disons, pour se fixer les idées, sur ) dont une base est ; concrètement ses éléments sont des sommes formelles , où pour tout , et où tous sauf un nombre fini des sont nuls (si notre graphe est infini par exemple). On additionne ces sommes formelles de manière évidente, et on les multiplie par des scalaire de la seule manière raisonnable.

De même, on définit comme un espace vectoriel dont une base est .

Pour faire en sorte que la différence (qui est maintenant bien définie : c’est un élément de !) soit nulle, on définit sur la base par .

Ensuite, pour s’assurer que cette quantité est nulle, on quotiente !

On définit et (pour la preuve, on ne va regarder que , mais j’expliquerai comment interpréter après); et notons la projection canonique.

Soit la relation définie par . Il est immédiat que est une relation d’équivalence; et la définition de et assure que , d’où .

En particulier (!) si est connexe (car est la relation d’équivalence totale). Il s’ensuit que pour tout , donc est de dimension au plus (il est engendré par qui est de cardinal au plus – le formuler comme ça permet de gérer le cas où sans exception).

Il s’ensuit que , ou encore . Or on connait une base de et une de ! Notant les cardinaux respectifs de , on a , ce qui est exactement ce qu’on voulait !

Il est à noter que cette preuve montre que l’égalité arrive “rarement” : en effet pour qu’on ait égalité, il faut déjà que soit de dimension , donc non vide; et ensuite il faut que soit injective (i.e. : on voit déjà poindre le bout de son nez), ce qui, au vu de sa définition, est relativement rare.

En fait on peut interpréter “indépendamment” pour voir plus précisément quand ça arrive.

L’idée est la suivante : on veut regarder quand . Si est dans la base, cette équation nous dit que est une boucle sur . En fait, plus généralement, les éléments de représentent des cycles dans .

Je ne vais pas rentrer dans les détails (qui sont pour le coup un peu pénibles à écrire à cause des orientations), mais l’idée est la suivante : si est un cycle (disons orienté, pour me simplifier la vie), c’est-à-dire que pour et , alors : c’est un calcul rapide que je vous laisse.

Si c’est un cycle, mais pas orienté (i.e. s’il faut éventuellement renverser le sens de certaines arêtes pour obtenir un cycle orienté), on a la même chose mais en rajoutant des signes devant les arêtes qu’il faut retourner : je vous laisse en exercice le fait d’écrire précisément ce que j’ai dit, et de faire la vérification.

On peut alors vérifier que les cycles minimaux (c’est-à-dire qu’ils ne peuvent pas être décomposés en plus petits cycles, et qu’ils ne contiennent pas deux fois la même arête de suite – orientés ou pas) forment une base de ; ainsi compte le “vrai” nombre de cycles dans (si sont deux cycles autour du sommet , alors faire puis est aussi un cycle, mais on ne veut pas le compter, on le voit comme )

Il s’ensuit que si et seulement si n’a pas de cycles ! Cela nous donne automatiquement le cas d’égalité : si est connexe, on a si et seulement si est non vide et ne contient aucun cycle; i.e. si c’est un arbre non vide.

En fait, avec à peine plus de travail (je vous le laisse donc en exercice! ) on peut montrer que est le nombre de composantes connexes de (les classes d’équivalence de la relation ; en fait montrer que la relation est toujours égale à ), c’est-à-dire le nombre de “trous -dimensionnels” de , et est le nombre de cycles minimaux, donc le nombre de “trous -dimensionnels”.

Cela semble indiquer qu’on peut continuer, avec des qui compteraient les “trous -dimensionnels”. C’est le cas: en fait si on rajoute par exemple des “faces” à notre graphe, c’est-à-dire un ensemble avec trois applications (imaginer les faces comme des triangles pleins, et est le -ème bord du triangle) on peut imaginer “combler” certains trous : imaginons par exemple un graphe sur sommets , avec une arête de à , une de vers , et une de vers , on a clairement un “trou” au milieu. Maintenant, si on met une face dont les bords sont précisément ces trois arêtes, on peut imaginer notre “figure” comme un triangle plein, qui n’a donc pas de trou.

Plus généralement, on peut imaginer des “-faces” pour tout . Une des manières de faire ça est la théorie des “ensembles simpliciaux”, leur homologie est définie de manière très similaire à ce que j’ai fait là, et on peut définir qui “compte les trous -dimensionnels” (par exemple on peut construire un ensemble simplicial qui ressemble à une -sphère, qui aura précisément un trou -dimensionnel, et aucun autre trou, comme le dessin le suggère). Je ne rentrerai pas là-dedans dans ce post, mais c’est très intéressant.

Je conclus sur une remarque qui n’a l’air de rien mais qui peut, dans des contextes plus généraux, avoir un intérêt : j’ai regardé des -espaces vectoriels, mais j’aurais pu regarder des -espaces vectoriels pour n’importe quel corps ; en fait j’aurais même pu regarder des -modules pour n’importe quel anneau ; même si pour ces derniers l’argument de la dimension ne fonctionne pas forcément. Pour le cela ne change pas grand chose, et en fait pour le d’un graphe non plus; mais il y a des ensembles simpliciaux pour lesquels il y a une vraie différence (par exemple un ensemble simplicial qui représenterait , le plan projectif réel)