Rudiments de la théorie des graphes

La notion de graphe a été introduite au siècle dernier, motivée par des jeux mathématiques (comme le célèbre problème ``des ponts de Königsberg''). Elle a l'avantage de faciliter l'expression -- par une visualisation intuitive -- de certaines relations abstraites entre les éléments d'ensembles. Ainsi, les graphes ont aujourd'hui une multitude d'applications comme : les chaînes de Markov, l'optimisation, les discrétisations pluri-dimensionnelles (triangulations ou, plus généralement, décompositions simpliciales en dimension supérieure), les développements en séries des perturbations, la recherche algorithmique, la combinatoire, l'étude des réseaux de transport, la topologie, la théorie des groupes, etc.

Dans cette annexe est présenté le strict minimum des notions qui servent soit au développement des méthodes Monte Carlo, soit à certaines applications qui sont traitées par simulation Monte Carlo. Des traités plus complets sur la théorie des graphes sont, par exemple, [BOLLOBÁS, GIBBONS].