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 30 Juin 2015

Graphes inhomogènes

par Élie de Panafieu (Research Institute for Symbolic Computation (RISC), J. Kepler Universität, Autriche)

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.

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