Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème de Kirchhoff
Résumé
Dans le domaine de la théorie des graphes, le théorème de Kirchhoff, aussi appelé matrix-tree theorem, nommé d'après le physicien Gustav Kirchhoff, est un théorème donnant le nombre exact d'arbres couvrants pour un graphe non orienté quelconque. C'est une généralisation de la formule de Cayley qui donne ce résultat pour les graphes complets non orientés.
Le théorème de Kirchhoff s'appuie sur la notion de matrice laplacienne, définie elle-même comme la différence entre la matrice des degrés et la matrice d'adjacence du graphe. Formellement, pour un graphe où , la matrice laplacienne est définie par :
Le théorème de Kirchhoff s'énonce ainsi :
On calcule d'abord la matrice laplacienne de ce graphe :
Le sommet 1 est de degré 2 et il est relié aux sommets 2 et 5 : la première colonne vaut (2, -1, 0, 0, -1, 0).
Le sommet 2 est de degré 3 et il est relié aux sommets 1, 3 et 5 : la deuxième colonne vaut (-1, 3, -1, 0, -1, 0).
Le sommet 3 est de degré 2 et il est relié aux sommets 2 et 4 : la troisième colonne vaut (0, -1, 2, -1, 0, 0).
Le sommet 4 est de degré 3 et il est relié aux sommets 3, 5 et 6 : la quatrième colonne vaut (0, 0, -1, 3, -1, -1).
Le sommet 5 est de degré 3 et il est relié aux sommets 1, 2 et 4 : la cinquième colonne vaut (-1, -1, 0, -1, 3, 0).
Le sommet 6 est de degré 1 et il est relié au sommet 4 : la sixième colonne vaut (0, 0, 0, -1, 0, 1).
Cela donne la matrice laplacienne :
On supprime ensuite n'importe quelle ligne et n'importe quelle colonne de la matrice. Si l'on supprime par exemple la troisième colonne et la deuxième ligne :
Le cofacteur est . D'après le théorème de Kirchhoff, il y a 11 arbres couvrants.
Le graphe possède en effet 11 arbres couvrants, ce que l'on peut effectivement constater dans la figure suivante :
600px|centré|Les 11 arbres couvrant le graphe de départ
Si le graphe de départ n'est pas connexe, alors la matrice laplacienne sera diagonale par bloc. En supprimant une ligne et une colonne, il y aura au moins une composante connexe pour laquelle aucune colonne n'aura été supprimée.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.