La présente thèse porte sur la théorie combinatoire et géométrique des groupes, c'est-à-dire l'étude de l'interaction entre les propriétés des groupes et celles des objets géométriques sur lesquels ils agissent. L'objectif principal de ce travail est d'étudier un objet classique en théorie des groupes: le groupe des automorphismes d'un groupe libre non-abélien de rang fini et son action sur les présentations des groupes de type fini. Pour tout groupe de type fini, cette action peut être décrite par le graphe de Nielsen, aussi appelé “Product Replacement Graph”. Le graphe de Nielsen est devenu un objet d'intérêt particulier depuis l'introduction du “Product Replacement algorithm”. Il s'agit d'un algorithme “pratique” pour générer des éléments aléatoires dans un groupe fini – une tâche hautement non-triviale en théorie calculatoire des groupes. Les sujets principaux de cette thèse sont la connexité et le comportement asymptotique (la non-moyennabilité, plus précisément) de graphes de Nielsen associés à des groupes spécifiques. Les travaux antérieurs sur ces sujets ont principalement porté sur les groupes finis. Dans cette thèse, l'accent est mis sur l'étude des graphes de Nielsen de groupes infinis de type fini. Nous considérons une classe de groupes, que nous appelons la classe MN, qui inclut les groupes nilpotents ainsi que des exemples exotiques de groupes infinis de torsion agissant sur des arbres enracinés. Nous montrons que, pour un groupe de type fini de la classe MN, les graphes de Nielsen peuvent avoir des comportements assez différents: ils peuvent tout aussi bien être connexes qu'avoir un nombre infini de composantes connexes. Plus précisément, nous montrons que graphes de Nielsen des groupes de Gupta-Sidki ont un nombre infini de composantes connexes; à la connaissance de l'auteur, c'est le premier exemple d'un groupe de torsion avec cette propriété. Des exemples de groupes de type fini de MN dont les graphes de Nielsen sont connexes sont déjà apparus dans la littérature; néanmoins, on en exhibe des nouvelles, notamment les groupes de Heisenberg. La question de la connexité des graphes de Nielsen, déjà intéressante en elle-même, est liée à la fameuse conjecture d'Andrews-Curtis. Cette conjecture a été motivée par des problèmes topologiques profonds et reste encore ouverte plus de 50 ans après sa formulation. Dans le contexte de ce problème, on montre que la classe MN ne peut pas fournir de contre-exemples à la conjecture d'Andrews-Curtis. L'analyse de la géométrie des graphes de Nielsen est un sujet assez nouveau, mais fascinant et actif. En particulier, la question de la moyennabilité des graphes de Nielsen infinis est étroitement liée à la question, ouverte depuis longtemps, de savoir si le groupe des automorphismes d'un groupe libre non-abélien de rang plus grande que 3 possède la Propriété (T). Nous montrons, en collaboration avec T. Smirnova-Nagnibeda, la non-moyennabilité des graphes de Nielsen pour les groupes indicables et les groupes élémentairement moyennables infinis.