13:00
14:00

[LX] Bruno Courcelle

** Arbres infinis fortement réguliers **

Tout graphe connexe nonorienté H admet un revêtement universel qui est un arbre infini (sauf cas de H arbre fini). Cette notion venant de la topologie est utile pour la théorie des algorithmes distribués étudiée par Y. Métivier.

On la généralise aux graphes H finis équipés d'un poids entier sur chaque demi-arête. Leurs revêtements universels sont des arbres dits fortement réguliers, T tels que pour chaque noeud x, l'arbre enraciné Tx égal à T muni de x comme racine est régulier et ces arbres sont en nombre fini à isomorphisme près. On donnera des caractérisations équivalentes plus précises. Tout arbre fortement régulier T provient d'un H canonique construit comme quotient de T.

On peut décider si un arbre régulier dont on oublie la racine est fortement régulier.

On peut caractériser en termes d'automorphismes des arbres fortement réguliers de diamètre infini.

LaBRI