Définition
La longueur (nombre d'arêtes) du plus court cycle d'un graphe ; définie comme l'infini si le graphe ne contient aucun cycle (c'est-à-dire s'il est une forêt).
Principe
Principe
La girth mesure la compacité cyclique locale d'un graphe : une petite girth signale des cycles courts et une structure cyclique locale dense, tandis qu'une grande girth indique un comportement local arborescent ou épars.
Démonstration
Démonstration
Le cycle C_n a girth n. Tout arbre a girth infinie. Le graphe de Petersen a girth 5. En théorie extrémale des graphes on construit souvent des familles avec grande girth et grand degré minimal.
Mauvaise application
Mauvaise application
Confondre girth et circonférence (longueur du plus long cycle), rang cyclique (nombre de cycles indépendants) ou moyennage des longueurs de cycles ; ne pas tenir compte des arêtes multiples ou boucles dans le cas des multigraphes.
Conséquence
Conséquence
La girth fournit des contraintes utilisées en théorie extrémale des graphes, influence les propriétés spectrales et d'expansion, et interagit avec des bornes de coloration ; une grande girth peut imposer des minorations du nombre chromatique dans certaines familles construites.
Inversion
Inversion
La perspective inverse met l'accent sur les plus longs cycles (circonférence) ou sur la structure cyclique globale plutôt que sur le cycle minimal local ; l'acyclicité correspond à une girth infinie et à l'absence de contraintes cycliques.
Limite
Limite
La girth standard concerne les graphes simples non orientés ; pour les graphes orientés on considère les cycles orientés, pour les multigraphes il faut préciser si arêtes multiples ou boucles comptent comme cycles, et pour les hypergraphes la notion se modifie.
Tension sémantique
Tension sémantique
Tension entre girth et dimension de l'espace des cycles (premier nombre de Betti) : un graphe peut avoir une petite girth mais un faible rang cyclique, ou une grande girth et de nombreux cycles indépendants ailleurs ; la girth est une minimalité locale, pas un compte global.
Synthèse
Synthèse
La girth est la longueur du plus court cycle et constitue une mesure locale de cyclicité : elle distingue le comportement arborescent (girth infinie) des graphes riches en cycles courts et joue un rôle central en théorie extrémale et spectrale des graphes.