Conférences

Retour au programme

Retour à la liste des conférenciers

Toutes les conférences ont lieu dans la salle PK-5115 du pavillon Président-Kennedy.

Toutes les conférences

Détails des conférences
  • Cédric Lamathe
  • UQAM
  • Vendredi 8 septembre, 15h
  • Énumération des graphes de k-arches étiquetés
  • Nous nous intéressons aux graphes de k-arches, une généralisation des arbres, contenant comme sous-classe les k-arbres. Nous montrons que le nombre de graphes de k-arches étiquetés est donné par une nouvelle suite d'entiers. Nous établissons ce résultat via une bijection entre ces graphes et certains mots dont les lettres sont des sous-ensembles de taille k de l'ensemble des sommets. Cette bijection généralise le code de Prüfer pour les arbres. Nous retrouvons également, lorsque k vaut 1, la formule de Cayley qui énumère les arbres étiquetés. La bijection proposée permet, en outre, d'obtenir un algorithme de génération aléatoire des graphes de k-arches étiquetés.