Graphes inhomogènes

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, nous verrons qu’il permet de calculer la probabilité limite qu’un graphe aléatoire soit bipartite et la probabilité de satisfiabilité de systèmes d’équations, d’énumérer les graphes proprement k -colorés et d’analyser des graphes intervenant dans la modélisation de réseaux sociaux.

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.