La première partie de la thèse porte sur les graphes de Steinhaus réguliers. On commence par obtenir une nouvelle preuve du théorème de Dymacek, selon lequel toute matrice de Steinhaus associée à un graphe pair est bisymétrique, en exhibant une relation entre les éléments de l'antidiagonale d'une matrice de Steinhaus et les degrés des sommets du graphe associé. Ce théorème est ensuite utilisé pour montrer que toute matrice de Steinhaus associée à un graphe régulier de degré impair admet une grande sous-matrice multisymétrique. On étudie alors les matrices de Steinhaus multisymétriques, en particulier celles dont le graphe associé admet une certaine régularité. Cette étude permet enfin de vérifier jusqu'à 1500 sommets une conjecture de Dymacek, qui annonce que le graphe complet à deux sommets K2 est le seul graphe de Steinhaus régulier de degré impair, améliorant ainsi d'un facteur 12 la borne précédemment connue (117 sommets).<br />La seconde partie porte sur les triangles de Steinhaus dans Z/nZ. En 1978 Molluzzo pose le problème de savoir si, pour tout n≥1 et pour toute longueur admissible m, il existe une suite balancée de longueur m dans Z/nZ, c'est-à-dire une suite dont le triangle de Steinhaus associé contienne chaque élément de Z/nZ avec la même multiplicité. On donne ici une réponse complète et positive au Problème de Molluzzo dans tout groupe cyclique d'ordre une puissance de 3. Plus généralement, on construit une infinité de suites balancées dans tout groupe cyclique d'ordre impair. Ces résultats, qui sont les premiers obtenus sur ce problème dans Z/nZ avec n>3, proviennent de l'étude des triangles de Steinhaus des suites arithmétiques dans les groupes cycliques.

Les langages réguliers sont des langages qui ont été largement étudiés, notamment du point de vue de leurs propriétés de clôture ensembliste : l'ensemble des langages réguliers (pour un alphabet donné) forme une algèbre de Boole close par concaténation et étoile de Kleene. Ces propriétés ne se généralisent pas toutes à l ensemble des langages algébriques qui est un sur-ensemble de l'ensemble des langages réguliers. Notamment les langages algébriques ne sont pas clos par intersection. Pour engendrer ces langages, nous utilisons les grammaires déterministes de graphes. Une grammaire de graphes est un système fini de récriture d'hypergraphes finis. Par récriture itérée à partir d'un non-terminal, la grammaire engendre un graphe régulier dont les traces forment un langage algébrique. En définissant une relation de synchronisation entre ces grammaires, on montre que l'on peut définir des sous-ensembles stricts de langages algébriques non-ambigus qui forment des algèbres de Boole effectives contenant les langages réguliers. Nous donnons également des conditions suffisantes pour que ces algèbres booléennes soient closes par concaténation et étoile de Kleene.

Dans cette thèse, nous étudions les propriétés de concentration des fonctions propres du laplacien discret sur des graphes réguliers de degré fixé dont le nombre de sommets tend vers l'infini. Cette étude s'inspire de la théorie de l'ergodicité quantique sur les variétés. Par analogie avec cette dernière, nous développons un calcul pseudo-différentiel sur les arbres réguliers : nous définissons des classes de symboles et des opérateurs associés, et nous prouvons un certain nombre de propriétés de ces classes de symboles et opérateurs. Nous montrons notamment que les opérateurs sont bornés dans L², et nous donnons des formules de l'adjoint et du produit. Nous nous servons ensuite de cette théorie pour montrer un théorème d'ergodicité quantique pour des suites de graphes réguliers dont le nombre de sommets tend vers l'infini. Il s'agit d'un résultat de délocalisation de la plupart des fonctions propres dans la limite des grands graphes réguliers. Les graphes vérifient une hypothèse d'expansion et ne comportent pas trop de cycles courts, deux hypothèses vérifiées presque sûrement par des suites de graphes réguliers aléatoires.

Dans cette thèse, nous étudions les propriétés de concentration des fonctions propres du laplacien discret sur des graphes réguliers de degré fixé dont le nombre de sommets tend vers l'infini. Cette étude s'inspire de la théorie de l'ergodicité quantique sur les variétés. Par analogie avec cette dernière, nous développons un calcul pseudo-différentiel sur les arbres réguliers : nous définissons des classes de symboles et des opérateurs associés, et nous prouvons un certain nombre de propriétés de ces classes de symboles et opérateurs. Nous montrons notamment que les opérateurs sont bornés dans L², et nous donnons des formules de l'adjoint et du produit. Nous nous servons ensuite de cette théorie pour montrer un théorème d'ergodicité quantique pour des suites de graphes réguliers dont le nombre de sommets tend vers l'infini. Il s'agit d'un résultat de délocalisation de la plupart des fonctions propres dans la limite des grands graphes réguliers. Les graphes vérifient une hypothèse d'expansion et ne comportent pas trop de cycles courts, deux hypothèses vérifiées presque sûrement par des suites de graphes réguliers aléatoires. / N this thesis, we study concentration properties of eigenfunctions of the discrete Laplacian on regular graphs of fixed degree, when the number of vertices tend to infinity. This study is made in analogy with the Quantum Ergodicity theory on manifolds. We construct a pseudo-differential calculus on regular trees by defining symbol classes and associated operators and proving some properties of these classes of symbols and operators. In particular we prove that the operators are bounded on L² and give adjoint and product formulas. We then use this theory to prove a Quantum Ergodicity theorem on large regular graphs. This is a property of delocalization of most eigenfunctions in the large scale limit. We consider expander graphs with few short cycles (for instance random large regular graphs). These hypothesis are almost surely satisfied by sequences of random regular graphs.

Dans cette thèse, nous nous intéressons aux aspects algorithmiques et applications de deux problèmes de graphes, à savoir, la coloration et les alliances. La première partie concerne deux variantes de la coloration de graphes, la coloration Grundy et la coloration forte stricte. Nous commençons par l'étude du nombre Grundy des graphes réguliers. Nous donnons une condition fixe k, nous fournissons une condition nécessaire et suffisante pour que le nombre Grundy d'un graphe régulier soit au moins égal k. Nous caractérisons la classe des graphes cubiques (3-réguliers) pour laquelle le nombre Grundy est égal à 4, et nous présentons un algorithme linéaire pour déterminer le nombre Grundy d'un graphe cubique quelconque. Par ailleurs, en se basant sur la coloration forte stricte pour décomposer les arbres en petites composantes, nous présentons un nouvel algorithme pour l'appariement d'arbres étiquetés, non-ordonnés non-enracinés. Nous montrons que la distance calculée entre deux arbres est une pseudo-métrique. Nos expérimentations sur de larges bases synthétiques et des bases de données réelles confirment nos résultats analytiques et montrent que la distance proposée est précise et son algorithme est scalable. La seconde partie de cette thèse est consacrée aux alliances dans les graphes. Nous proposons un algorithme distribué autostabilisant pour la construction d'alliance offensive globale minimale dans un graphe arbitraire. Nous démontrons que cet algorithme converge sous le démon synchrone en temps linéaire. Ensuite, nous donnons le premier algorithme distribué autostabilisant pour le problème de l'alliance forte globale minimale dans un graphe quelconque. Nous prouvons que cet algorithme est polynomial sous le démon inéquitable distribué. Nous montrons par la suite, comment cet algorithme peut être adapté pour des généralisations du problème, comme la k-alliance forte et l'alliance forte pondérée. Enfin, en se basant sur les propriétés structurelles de l'alliance offensive, nous présentons une solution pour décentraliser le protocole de signalisation SIP. Ceci rend possible son déploiement dans un réseau mobile ad hoc / This thesis investigates the algorithmic aspects and applications of two graph problems, namely, colorings and alliances. In the first part, we focus on two variants of the proper vertex coloring, the Grundy coloring and the strict strong coloring. We start by the study of Grundy number for regular graphs. We give a sufficient condition for d-regular graphs with sufficiently large girth to have Grundy number equals d + 1. Then, using graph homomorphism, we obtain a necessary and sufficient condition for d-regular graphs to have Grundy number at least k. Moreover, we characterize cubic graphs (3-regular) for which the Grundy number is d + 1, and present a linear-time algorithm to determine the Grundy number of any arbitrary cubic graph. Subsequently, based on the strict strong coloring, we present an approach for the problem of matching labeled trees. Using this coloring, we propose a new algorithm to deterministically decompose a tree into small components. This leads to an efficient algorithm to measure an accurate distance between unrooted unordered labeled trees. The second part is devoted to the alliances in graphs. We first propose a linear-time self-stabilizing algorithm for the minimal global offensive alliance set problem, under the synchronous distributed scheduler. Then, we give the first self-stabilizing algorithm for the minimal global powerful alliance set problem in arbitrary graphs. Moreover, we show how this algorithm can be adapted to find the minimal global powerful k-alliance and the minimal weighted global powerful alliance sets. We prove that all these algorithms converge in polynomial-time under the unfair distributed scheduler. Finally, based on the structural properties of the offensive alliance, we propose a solution to decentralize the signaling protocol SIP. This enables SIP applications in mobile ad hoc networks