Ce mémoire est consacré au problème de la bissection dans les
graphes aléatoires. Il s'agit de partitionner
l'ensemble des sommets d'un graphe en deux sous-ensembles de même
taille, de telle manière que le nombre d'arêtes entre ces deux
sous-ensembles soit minimum.
Afin d'étudier ce problème, nous allons tout d'abord présenter
dans le chapitre 1
quelques notions et méthodes de la théorie des graphes
aléatoires. Ensuite nous exposerons dans le chapitre 2 quelques résultats de la
théorie algorithmique des graphes aléatoires, nous entendons par
là l'analyse d'algorithmes sur des graphes aléatoires.
Ces résultats
porteront principalement sur les problèmes de la
bissection de graphe et l'affectation.
Les meilleurs résultats sur ces problèmes ont été
jusqu'ici obtenus grâce à une
méthode tirée de
la physique théorique: la méthode des spin
glasses. Nous avons donc jugé utile de présenter cette méthode
dans le chapitre 3 avec les principes généraux de l'utilisation de méthode de
physique statistique pour des problèmes d'optimisation. Toutefois,
du fait de la difficulté de la théorie ainsi
que du manque de justification mathématique (défaut reconnu par
les physiciens eux mêmes, on pourra voir à ce propos le livre de Mézard, Parisi et
Viraroso), nous nous sommes limités aux lignes
générales de la méthode.
Enfin, nous serons amenés, dans le chapitre 4 à exposer des résultats obtenus par nous même durant le stage sur le problème de la bissection ainsi que sur celui de la coupe maximum, ces deux problèmes étant liés dans le cas aléatoire comme nous pourront le voir. On donne en particulier des bornes inférieures et supérieures sur la valeur minimum d'une bissection, la borne supèrieure etant obtenue par l'analyse d'un algorithme de type glouton. Ces résultats sont moins précis que ce que donnent la méthode des spin glasses, mais ils sont par contre parfaitement rigoureux.