Quelques utilisations des arbres en combinatoire. |
| Les phénomènes de seuil
dans une structure aléatoire ont été mis en évidence
par Erdös et Rényi lors de leur étude de la taille des
composantes connexes dans le modèle de graphe aléatoire indépendant.
De tels phénomènes ont pu être mis en évidence
pour d'autres problèmes d'informatique théorique et sont liés
aux transitions de phase existants en physique statistique. Dans cette thèse nous nous intéressons à l'approximation de la fonction du seuil de satisfaisabilité d'une formule aléatoire sous forme 2-CNF sur n variables. Soit e fixé, on considère le rapport entre le nombre de clauses m de la formule et le nombre de variables n. Il a été montré par Chvátal et Reed et par Goerdt que lorsque ce rapport est inférieur à 1-e alors la formule aléatoire est presque sûrement satisfaisable tandis que lorsque ce rapport est supérieur à 1+e, la formule est presque sûrement insatisfaisable. Nous donnons ici des bornes pour la valeur du rapport m/n en fonction d'une puissance de n. La borne inférieure est obtenue en améliorant une preuve due à Goerdt tandis que la borne supérieure résulte d'une analyse d'algorithme à l'aide d'arbres de Galton-Watson. Nous étudions aussi les composantes fortement connexes dans le graphe aléatoire orienté et en particulier la taille de la composante géante. En effet, lorsque suffisamment d'arêtes ont été ajoutées, Karp a montré que l'on assiste avec grande probabilité à l'apparition soudaine d'une composante fortement connexe de taille linéaire. Nous améliorons les bornes données par Karp concernant la taille de cette composante géante en utilisant des arbres de Galton-Watson dans une analyse d'algorithme. |
Some uses of random trees in combinatorics. |
| Threshold phenomenon in random structures
were revealed by Erdös and Rényi while studying the size of the
connected components in the independent random graph model. Such phenomena
have been brought to the fore for others computer science problems and arise
in statistical physics. In this thesis, we are particularly interested in the approximation of the function of the satisfiability threshold of a 2-CNF random formula on n variables. Let e be a fixed constant, we consider the ratio between the number of clauses m and the number of variables n. It has been showed by Chvátal and Reed and by Goerdt independently that if this ratio is less than 1-e then the random formula is almost surely satisfiable while if the ratio is more than 1+e, the random formula is almost surely unsatisfiable. We give here bounds on the ratio m/n depending on a power of n. An inferior bound is obtained by extending a proof of Goerdt while the superior bound results from the analysis of an algorithm, using Galton-Watson trees. We also study the strongly connected components in the random directed graph and more particularly the size of the giant component. Indeed, when enough edges have been added, Karp showed the emergence with high probability of a strongly connected component of linear size. Using Galton-Watson trees in the analysis of an algorithm, we obtain more precise bounds for the fluctuations of the size of this giant component |
This document was translated from LATEX by HEVEA.