Ê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
Taux d'expansion (théorie des graphes)
Résumé
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.
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.