Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 24 Avril 2001

Aspects combinatoires des graphes sans isomorphisme

par Vlady Ravelomanana (Universite d'Amiens)

L'enumeration de graphes etiquetes trouve ses origines quand, vers 1880, A. Cayley compta le nombre d''etiquetages d'arbres pouvant etre construits sur $n$ sommets. Depuis, les graphes multicycliques connexes (possedant $n$ sommets et $n+k$ ar\^etes) ont ete enumeres par E.~M. Wright de maniere exacte et asymptotiquement par E. Bender et al.. Toutefois, les problemes combinatoires souleves par les enumerations des graphes sans triangle (sans carres) s'averent difficiles.

Etant donne un ensemble fini, $\xi$, de motifs interdits, le but de cet expose est d'introduire une equation fonctionnelle (type ``conduction de la chaleur'') satisfaite par les series generatrices des graphes sans $\xi$. Nous montrerons sur quelques exemples, comment resoudre une telle equation et obtenir les series generatrices des premiers multicycles sans $\xi$. Nous montrerons alors que ces series generatrices se presentent toutes sous une forme particuliere permettant de compter asymptotiquement les graphes sans $\xi$ avec $n$ sommets et $n+o(n^{1/3}) aretes. Nous verrons alors les consequences de ces enumerations dans divers modeles de graphes aleatoires (et ce par l'approche enumerative).

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr