Dans cette thèse, on étudie la convergence du processus d'exploration de l'arbre généalogique d'un processus de branchement en temps continu non binaire, dans la limite d'une grande population. Dans la première partie, nous donnons une description précise du processus d'exploration de l'arbre non binaire. Ensuite nous décrivons une certaine bijection entre l'ensemble des processus d'exploration et l'ensemble des arbres non binaires. Après renormalisation des paramètres, nous présentons les résultats de convergence du processus de population et du processus d'exploration dans la limite d'une grande population. Dans la deuxième partie, nous établissons d'abord la convergence du processus de population vers un processus de branchement à espace d'état continu avec sauts. Puis, nous montrons la convergence du processus d'exploration normalisé de l'arbre généalogique correspondant vers le processus de hauteur continu défini récemment par Li, Pardoux et Wakolbinger.Dans la dernière partie, on définit un modèle discret de population avec interaction définie par une fonction générale non linéaire f. On fait une renormalisation adéquate du modèle discret pour obtenir en limite un processus de branchement à espace d'état continu généralisé. Ensuite nous renormalisons le processus d'exploration de l'arbre généalogique associé et nous prenons la limite quand la taille de la population tend vers l'infini. / In this thesis, we study the convergence of the exploration process of the non-binary tree associated to a continuous time branching process, in the limit of a large population. In the first part, we give a precise description of the exploration process of the non-binary tree. We then describe a bijection between exploration processes and Galton Watson non-binary trees. After some renormalization, we present the results of convergence of the population process and the exploration process, in the limit of a large populations.In the second part, we first establish the convergence of the population process to a continuous state branching process (CSBP) with jumps. We then show the convergence of the (rescaled) exploration process, of the corresponding genealogical tree towards the continuous height process recently defined by Li, Pardoux and Wakolbinger. In the last part, we consider a population model with interaction defined with a more general non linear function $f.$ We proceed to a renormalization of the parameters model and we obtain in limit a generalized CSBP. We then renormalize the height process of the associated genealogical tree, and take the weak limit as the size of the population tends to infinity.

We study certain questions related to the performance of the Karp-Sipser algorithm on the sparse Erdös-Rényi random graph. The Karp-Sipser algorithm, introduced by Karp and Sipser [34] is a greedy algorithm which aims to obtain a near-maximum matching on a given graph. The algorithm evolves through a sequence of steps. In each step, it picks an edge according to a certain rule, adds it to the matching and removes it from the remaining graph. The algorithm stops when the remining graph is empty. In [34], the performance of the Karp-Sipser algorithm on the Erdös-Rényi random graphs G(n,M = [^cn/₂]) and G(n, p = ^c/_n), c > 0 is studied. It is proved there that the algorithm behaves near-optimally, in the sense that the difference between the size of a matching obtained by the algorithm and a maximum matching is at most o(n), with high probability as n → ∞. The main result of [34] is a law of large numbers for the size of a maximum matching in G(n,M = ^cn/₂) and G(n, p = ^c/_n), c > 0. Aronson, Frieze and Pittel [2] further refine these results. In particular, they prove that for c < e, the Karp-Sipser algorithm obtains a maximum matching, with high probability as n → ∞; for c > e, the difference between the size of a matching obtained by the algorithm and the size of a maximum matching of G(n,M = ^cn/₂) is of order Θ_{log n}(n^1/5), with high probability as n → ∞. They further conjecture a central limit theorem for the size of a maximum matching of G(n,M = ^cn/₂) and G(n, p = ^c/_n) for all c > 0. As noted in [2], the central limit theorem for c < 1 is a consequence of the result of Pittel [45]. In this thesis, we prove a central limit theorem for the size of a maximum matching of both G(n,M = ^cn/₂) and G(n, p = ^c/_n) for c > e. (We do not analyse the case 1 ≤ c ≤ e). Our approach is based on the further analysis of the Karp-Sipser algorithm. We use the results from [2] and refine them. For c > e, the difference between the size of a matching obtained by the algorithm and the size of a maximum matching is of order Θ_{log n}(n^1/5), with high probability as n → ∞, and the study [2] suggests that this difference is accumulated at the very end of the process. The question how the Karp-Sipser algorithm evolves in its final stages for c > e, motivated us to consider the following problem in this thesis. We study a model for the destruction of a random network by fire. Let us assume that we have a multigraph with minimum degree at least 2 with real-valued edge-lengths. We first choose a uniform random point from along the length and set it alight. The edges burn at speed 1. If the fire reaches a node of degree 2, it is passed on to the neighbouring edge. On the other hand, a node of degree at least 3 passes the fire either to all its neighbours or none, each with probability 1/2. If the fire extinguishes before the graph is burnt, we again pick a uniform point and set it alight. We study this model in the setting of a random multigraph with N nodes of degree 3 and α(N) nodes of degree 4, where α(N)/N → 0 as N → ∞. We assume the edges to have i.i.d. standard exponential lengths. We are interested in the asymptotic behaviour of the number of fires we must set alight in order to burn the whole graph, and the number of points which are burnt from two different directions. Depending on whether α(N) » √N or not, we prove that after the suitable rescaling these quantities converge jointly in distribution to either a pair of constants or to (complicated) functionals of Brownian motion. Our analysis supports the conjecture that the difference between the size of a matching obtained by the Karp-Sipser algorithm and the size of a maximum matching of the Erdös-Rényi random graph G(n,M = ^cn/₂) for c > e, rescaled by n^1/5, converges in distribution.