Élie de Panafieu (Research Institute for Symbolic Computation (RISC)

Nous introduisons le modèle de « graphes inhomogènes » où chaque sommet possède un « type » et chaque arête un « poids » déterminé par les types des sommets qu’il relie. Le « poids » du graphe inhomogène est alors défini comme le produit des poids de ses arêtes.

Ce modèle fournit un cadre unifié pour traiter de nombreux problèmes provenant de divers domaines informatiques et mathématiques. En particulier, il permet d’énumérer les instances satisfaites de problèmes de satisfaction de contraintes, tels que la coloration de graphe et la satisfaisabilité de formules logiques.

Nous verrons comment calculer la somme des poids des graphes inhomogènes selon leurs nombres de sommets et d’arêtes, et énoncerons des résultats de structure des grands graphes inhomogènes aléatoires.