Abstract FR:

Cette thèse rassemble plusieurs travaux dont le point commun est l'utilisation de méthodes probabilistes. La première partie concerne l'étude des paramètres de domination et d'irredondance dans les graphes aléatoires de probabilité d'arête 1/2. Nos résultats apportent un point final à l'étude du trio: irredondance, domination et stabilité dans ces graphes. Dans la deuxième partie on délaisse momentanément les probabilités pour aborder les graphes signés. On s'intéresse plus particulièrement au problème de l'équilibre dans ces graphes. On introduit la notion de sous-graphes équilibrants dont on donne quelques caractérisations qui permettent d'obtenir de nouveaux résultats. Nous introduisons dans la troisième partie la notion de graphes signés aléatoires et nous étudions les principales propriétés statistiques de ces graphes. La quatrième partie est consacrée à l'énumération d'une classe d'ordres partiels. Nous donnons une procédure pour calculer le nombre d'ordres partiels gradués de largeur et de rang donnes. Pour une largeur fixée la procédure utilise un temps de calcul qui est une fonction linéaire du rang. Finalement, dans la dernière partie, on étudie le problème de la satisfiabilité d'un ensemble de 3-clauses aléatoires