No description available.

[pt] Calcular o valor do fluxo máximo entre um nó origem e um nó destino em uma rede é um problema clássico no contexto de Fluxos em Redes. Sua extensão, chamada de problema do fluxo máximo multiterminal, consiste em achar os valores dos fluxos máximos entre todos os pares de nós de uma rede não direcionada. Estes problemas possuem diversas aplicações, especialmente nos campos de transporte, logística, telecomunicações e energia. Neste trabalho, apreciamos a recente teoria da análise de sensibilidade, em que se estuda a influência da variação de capacidade de arestas nos fluxos máximos multiterminais, e estendemos a computação dinâmica dos fluxos multiterminais para o caso de mais de uma aresta com capacidade variável. Através dessa teoria, relacionamos também nós de corte e fluxos multiterminais, o que permitiu desenvolver um método competitivo para solucionar o problema do fluxo máximo multiterminal, quando a rede possui nós de corte. Os resultados dos experimentos computacionais conduzidos com o método proposto são apresentados e comparados com os de um algoritmo clássico, fazendo uso de instâncias geradas e outras conhecidas da literatura. Por último, aplicamos a teoria apresentada em um problema de identificação de complexos de proteínas em redes de interação proteína-proteína. Através da generalização de um algoritmo e de um resultado teórico sobre exclusão de cortes mínimos, foi possível reduzir o número de cálculos de fluxo máximo necessários para identificar tais complexos. / [en] Computing the maximum flow value between a source and a terminal nodes in a given network is a classic problem in the context of network flows. Its extension, namely the multi-terminal maximum flow problem, consists of finding the maximum flow values between the all pairs of nodes in a given undirected network. These problems have several applications, especially in the fields of transports, logistics, telecommunications and energy. In this work, we study the recent theory of sensitivity analysis, which examines the influence of edges capacity variation on the multi-terminals maximum flows, and we extend the dynamic computation of multi-terminals flows to the case of more than one edge with variable capacity. Based on this theory, we also relate cut nodes and multiterminals flows, allowing us to develop a competitive method to solve the multiterminal maximum flow problem, when the network has cut nodes. The results of the computational experiments conducted with the proposed method are presented and compared with the results of a classical algorithm, using generated and wellknown instances of the literature. Finally, we apply the presented theory on a problem of identifying protein complexes in protein-protein interaction networks. Through the generalization of an algorithm and a theoretical result about exclusion of minimum cuts, it was possible to reduce the number of maximum flow computations necessary to identify such complexes.

Cette thèse se divise en deux parties. Nous nous intéressons dans un premier temps à des fragmentations d'arbres aléatoires, et aux arbres des coupes associés. Dans le cadre discret, les modèles étudiés sont des arbres de Galton-Watson, fragmentés en enlevant successivement des arêtes choisies au hasard. Nous étudions également leurs analogues continus, l'arbre brownien et les arbres stables, que l'on fragmente en supprimant des points donnés par des processus ponctuels de Poisson. L'arbre des coupes associé à l'un de ces processus, discret ou continu, décrit la généalogie des composantes connexes créées au fur et à mesure de la dislocation. Pour une fragmentation qui se concentre autour de nœuds de grand degré, nous montrons que l'arbre des coupes continu est la limite d'échelle des arbres des coupes discrets correspondants. Dans les cas brownien et stable, nous montrons également que l'on peut reconstruire l'arbre initial à partir de son arbre des coupes et d'un étiquetage bien choisi de ses points de branchement. Nous étudions ensuite un problème portant sur les cartes aléatoires, et plus précisément sur la quadrangulation uniforme infinie du plan (UIPQ). De récents résultats montrent que dans l'UIPQ, toutes les géodésiques infinies issues de la racine sont essentiellement similaires. Nous déterminons la quadrangulation limite obtenue en ré-enracinant l'UIPQ ''à l'infini'' sur de l'une de ces géodésiques. Cette étude se fait en découpant l'UIPQ le long de cette géodésique. Nous étudions les deux parties ainsi créées via une correspondance avec des arbres discrets, puis nous obtenons la limite souhaitée par recollement. / This PhD thesis is divided into two parts. First, we study some fragmentations of random trees and the associated cut-trees. The discrete models we are interested in are Galton-Watson trees, which are cut down by recursively removing random edges. We also consider their continuous counterparts, the Brownian and stable trees, which are fragmented by deleting the atoms of Poisson point processes. For these discrete and continuous models, the associated cut-tree describes the genealogy of the connected components which appear during the cutting procedure. We show that for a ''vertex-fragmentation'', in which the nodes having a large degree are more susceptible to be deleted, the continuous cut-tree is the scaling limit of the corresponding discrete cut-trees. In the Brownian and stable cases, we also give a transformation which rebuilds the initial tree from its cut-tree and a well chosen labeling of its branchpoints. The second part relates to random maps, and more precisely the uniform infinite quadrangulation of the plane (UIPQ). Recent results show that in the UIPQ, all infinite geodesic rays originating from the root are essentially similar. We identify the limit quadrangulation obtained by rerooting the UIPQ at a point ''at infinity'' on one of these geodesics. To do this, we split the UIPQ along this geodesic ray. Using a correspondence with discrete trees, we study the two sides, and obtain the desired limit by gluing them back together.