Évaluation du nombre d'arbres couvrants d'un réseau planaire

Abstract

This thesis focuses on the characterization of color This thesis focuses on the evaluation of the spanning trees number in planar networks. Being an important invariant, this number arises in various applications which leads us to investigate the complexity of planar graphs. In this context, we propose the splitting method which consists of the decomposition of a planar graph into two subgraphs through an edge or a simple path. This technique provides the derivation of recursive functions counting the number of spanning trees in planar graphs and conceives an algorithm for the chained planar graphs with a simple path such as the graph that illustrates the airport problem and the chained wheel graph. However, the splitting method has geometrical restrictions, thus, it cannot be used for some families of planar graphs. From this point of view, we propose the contraction method that provides the enumeration of spanning trees in a large family of planar networks such as the campus local and the pseudo fractal scale free networks. It consists of splitting the graph into n subgraphs and evaluates the complexity of these later before and after the contraction of a separation pair of vertices. In despite of the advantage of this technique, it cannot resolve the problem of enumerating the spanning trees in some families of networks. Thus, we use some combinatorics transformations that change the geometrical nature of these networks. We propose three approaches, the duality that simplifies the network topology, the bipartition that reduces the number of vertices and the reduction that reduces the number of edges. These techniques consist of finding the relation between the complexity of a planar graph and its dual, its bipartite and its reduced graphs. The aim of these approaches is the evaluation of the number of spanning trees in some networks which can not be find using the existing methods such as the Ven and the grid bipartite networks.