Théorie spectrale des graphes

Summarize Timeline Top Qs Fact Check

Soit un graphe ${\displaystyle G=(V,E)}$, où ${\displaystyle V}$ désigne l'ensemble des sommets et ${\displaystyle E}$ l'ensemble des arêtes. Le graphe possède ${\displaystyle |V|=n}$ sommets, notés ${\displaystyle v_{1},\cdots ,v_{n}\in V}$ et ${\displaystyle |E|=m}$ arêtes, notées ${\displaystyle e_{ij},v_{i}\in V,v_{j}\in V}$. Chaque élément de la matrice d'adjacence ${\displaystyle A}$ du graphe ${\displaystyle G}$ est défini par :

${\displaystyle a_{ij}=\left\{{\begin{array}{rl}1&{\mbox{si }}e_{ij}\in E\\0&{\mbox{sinon.}}\end{array}}\right.}$

Graphe	Représentation par une matrice d'adjacence	Représentation par une matrice laplacienne (non normalisée)
	${\displaystyle {\begin{pmatrix}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}$	${\displaystyle {\begin{pmatrix}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{pmatrix}}}$

La matrice des degrés ${\displaystyle D}$ est une matrice diagonale où les éléments ${\displaystyle D_{ii}}$ correspondent au nombre de liens du sommet ${\displaystyle i}$, c'est-à-dire à son degré. En utilisant cette matrice et la précédente, on peut également définir la matrice laplacienne non normalisée ${\displaystyle L=D-A}$.

On obtient sa forme normalisée ${\displaystyle L'}$ par ${\displaystyle L'=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}}$, où ${\displaystyle I}$ est la matrice identité. On obtient aussi ${\displaystyle L'}$ directement par chacun de ses éléments :

${\displaystyle \ell _{i,j}:={\begin{cases}1&{\mbox{si}}\ i=j\ {\mbox{et}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{si}}\ i\neq j\ {\mbox{et}}\ v_{i}{\text{ est adjacent à }}v_{j}\\0&{\text{sinon}}.\end{cases}}}$

Enfin, la matrice d'incidence ${\displaystyle M}$ d'un graphe ${\displaystyle G=(V,E)}$ est la matrice de dimensions ${\displaystyle |V|\times |E|}$ dans laquelle l'élément ${\displaystyle b_{ij}}$ vaut 1 si le sommet ${\displaystyle v_{i}}$ est une extrémité de l'arête ${\displaystyle x_{j}}$, et 0 sinon. On a l'ensemble de relations suivantes^[1], où ${\displaystyle I}$ désigne la matrice identité :

• ${\displaystyle A=MM^{T}-D}$
• Pour la matrice d'adjacence du line graph ${\displaystyle L(G)}$, ${\displaystyle A=M^{T}M-2I}$
• Pour la matrice d'adjacence du graphe de subdivision ${\displaystyle S(G)}$, ${\displaystyle A={\begin{pmatrix}0&M^{T}\\M&0\\\end{pmatrix}}}$

Le spectre d'une matrice est l'ensemble de ses valeurs propres ; si elles sont réelles, nous convenons de les classer : ${\displaystyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}}$. Par extension, on parle du spectre du graphe. On rappelle que la multiplicité algébrique d'une valeur propre ${\displaystyle \lambda }$ est la puissance du monôme ${\displaystyle (X-\lambda )}$ dans le polynôme caractéristique (c'est-à-dire la multiplicité de la racine dans le polynôme caractéristique). Il est également possible de modifier le polynôme caractéristique pour prendre en compte d'autres propriétés du graphe : on considère par défaut le polynôme ${\displaystyle P_{G}(\lambda )=|\lambda I-A|}$ (appelé polynôme caractéristique du graphe), mais on peut aussi s'intéresser à des variantes^[1] telles que ${\displaystyle R_{G}(\lambda )=|\lambda I-D-A|}$ ou ${\displaystyle Q_{G}(\lambda )=|D|^{-1}\cdot |\lambda D-A|}$.

Summarize Timeline Fact Check

La matrice du graphe est définie positive, et elle ne peut être réduite si le graphe est connexe. Dans le cas d'un graphe non orienté, la matrice est symétrique et hermitienne, c'est-à-dire que ${\displaystyle A^{\dagger }=A}$ où ${\displaystyle A^{\dagger }}$ est la matrice adjointe de ${\displaystyle A}$. La trace de la matrice est égale au nombre de boucles : en effet, un élément sur la diagonale indique la présence d'une boucle et la trace est la somme de ces éléments. Nous avons les propriétés suivantes^[1] :

• Le rayon spectral ${\displaystyle \rho (A)}$ de la matrice, c'est-à-dire sa plus grande valeur propre, satisfait ${\displaystyle 2\cdot \cos \left({\frac {\pi }{n+1}}\right)\leq \rho (A)\leq n-1}$ pour un graphe connexe. La borne inférieure est atteinte dans le cas où le graphe est un chemin et la supérieure est atteinte pour le graphe complet.
• Si le graphe est ${\displaystyle k}$-régulier alors ${\displaystyle \rho (A)=k}$ et la multiplicité de ${\displaystyle \rho (A)}$ donne le nombre de composantes connexes.
• Le graphe ne contient un cycle de longueur impaire que si ${\displaystyle -\rho (A)}$ est aussi une valeur propre^{[réf. nécessaire]}.
• S'il y a ${\displaystyle m}$ valeurs propres distinctes, alors le diamètre ${\displaystyle D}$ satisfait ${\displaystyle D\leq m-1}$.
• La taille ${\displaystyle t}$ du stable maximum satisfait ${\displaystyle t\leq p_{0}+\min(p_{-},p_{+})}$ où ${\displaystyle p_{-},p_{0},p_{+}}$ sont respectivement le nombre de valeurs propres inférieures, égales ou supérieures à 0.
• ${\displaystyle {\frac {\rho (A)}{-q}}+1\leq \chi (G)\leq \rho (A)+1}$ où ${\displaystyle \chi (G)}$ est le nombre chromatique et ${\displaystyle q}$ la plus petite valeur propre.

Summarize Timeline Fact Check

La valeur propre ${\displaystyle \lambda _{1}}$ est appelée la connectivité algébrique du graphe. Les propriétés essentielles du spectre sont résumées ci-dessous^[2] :

• ${\displaystyle \lambda _{0}=0}$.
• ${\displaystyle \sum _{i}\lambda _{i}\leq n}$ si le graphe est connexe.
• Si ${\displaystyle n\geq 2}$ et que G est un graphe complet alors ${\displaystyle \lambda _{1}={\frac {n}{n-1}}}$, sinon ${\displaystyle \lambda _{1}\leq {\frac {n}{n-1}}}$.
• Si le graphe est connexe alors ${\displaystyle \lambda _{1}>0}$. Si ${\displaystyle \lambda _{i}=0}$ et ${\displaystyle \lambda _{i+1}\neq 0}$ alors ${\displaystyle G}$ a exactement ${\displaystyle i+1}$ composantes (i.e. graphes connexes).
• ${\displaystyle \lambda _{i}\leq 2}$ ${\displaystyle \forall i\leq n-1}$.

Le théorème de Kirchhoff (aussi appelé matrix-tree theorem) donne une relation entre le nombre d'arbres couvrants et la matrice laplacienne.