Taux d'expansion (théorie des graphes)

En mathématiques, et plus particulièrement en théorie des graphes, le taux d'expansion d'un graphe est une mesure de connectivité de ce graphe. Informellement, un grand taux d'expansion veut dire que n'importe quel sous-ensemble de sommets relativement petit possède beaucoup de connexions avec le reste du graphe. Cette mesure est surtout utilisée en raison des propriétés intéressantes des graphes ayant un fort taux d'expansion, parfois appelés graphes expanseurs. On les retrouve notamment en informatique théorique. vignette|Les sommets coloriés en vert ont pour frontière l'ensemble des arêtes beiges. La frontière intérieure sont les sommets verts entourés en beige. La frontière extérieure sont les sommets noirs entourés en beige.|alt= Soit un graphe non orienté à sommets et un sous-ensemble de sommets de . On appelle frontière (boundary) de , notée , l’ensemble des arêtes de partant d'un sommet de et n'aboutissant pas à un sommet de . En notation mathématique, cela donne : Notons que l'ensemble peut aussi être défini comme la coupe entre et . Cette frontière est définie comme un ensemble d'arêtes, on parle parfois de frontière des arêtes (edge boundary) pour la différencier des notions de frontières des sommets (vertex boundaries) : la frontière des sommets extérieure (outer vertex boundary) notée est définie comme l'ensemble des sommets de ayant au moins un voisin dans : la frontière des sommets intérieure (inner vertex boundary) notée est définie comme l'ensemble des sommets de ayant au moins un voisin dans : Sur la figure, la frontière intérieure est en vert entouré en beige et la frontière extérieure en noir entouré en beige. Le taux d'expansion du graphe non orienté est : En d'autres termes, est le minimum, pris sur des parties comportant au maximum sommets, du rapport entre le nombre d'arêtes de la frontière de et le nombre de sommets de . est aussi appelé nombre isopérimétrique (isoperimetric number) ou constante de Cheeger, sachant qu'il existe aussi une constante de Cheeger en géométrie riemannienne.