A l’ère de l’urbanisation rapide dans les pays en développement, notre monde est aujourd’hui confronte a de nombreux défis en termes de réchauffement climatique. Pour y remédier, certains pays émergents ont commence ces dernières années a privilégier la mise en place croissante et progressive de transport en commun. C’est ainsi qu’en chine, en 2012, 1755 km de ligne de métro est construit pour seize villes. Or, la construction d’un métro possède d’importants risques financiers selon les expériences internationales. Néanmoins, le développement du métro en chine est en surchauffe. Le but global de la recherche est d’étudier les caractéristiques structurelles du réseau métropolitain a paris et son évolution afin de donner des suggestions au développement du métro de Wuhan. Pour atteindre cet objectif, nous avons adopte l’analyse de centralité structuralité pour étudier le réseau de métro parisien, ainsi que le réseau de métro a Wuhan. L’indicateur centralité structuralité (centralité en résume) consiste ainsi a mettre en évidence la distance « la plus simple » a parcourir pour arriver a sa destination, c’est-a-dire la distance a parcourir avec le moins de tournant a réaliser dans le réseau routier pour y arriver. Pour les réseaux de métro, cela signifie moins de changements de lignes. Des résultats nous monte que l’analyse de centralité pourrait indiquer l’importance relative des stations de métro dans un réseau. Cela pourrait permettre aux urbanistes et designers d’estimer le trafic entrant des stations. Eventuellement, cet indicateur pourrait d’être adopte pour analyser et comparer des projets différents du réseau de métro. / In the era of fast urbanisation in the developing countries, our world is now facing many challenges in the context of global warming. In order to solve these difficulties, certain developing countries have started in the last few years to promote increasingly the role of public transportation. It is also the case in china in 2020 that 1755 km of metro line was built in seventeen cities. However, according to the international experiences, there can be great financials risks in construction of metro system. Even though, the metro development in china is overheating. The general research objective is to study the structural characteristic of metro network in Paris and its development in order to give suggestions for the metro development in Wuhan. In order to attain this objective, we have adopted the structural centrality analyse to study the metro network in Paris and Wuhan. The indicator structural centrality (centrality in short) evaluates the simplest distance to reach the destination. It means that with the less turning to do in a road network. For the metro network, it means the less changes of lines. The results showed us that the centrality analyses could indicate the relative importance of the metro stations in a network. It could allow the urban planners and designers to estimate the entering traffic of the stations. Eventually, this indicator could be used to analyse and compare the different plans of metro networks.

La géométrie combinatoire est une large et belle branche des mathématiques. Cette thèse doctorale se compose de l'étude de cinq sujets différents dans ce domaine. Même si les problèmes et les techniques utilisés pour y faire face sont divers, ils partagent le mêeme objectif: Étudier l'interaction entre les structures combinatoires et géométriques. Dans le chapitre 1, nous étudions le problème suivant : pour un entier positif k, combien de points en position générale devons-nous prendre dans le plan de sorte que nous pouvons toujours trouver k d'entre eux définissant des triangles avec un rayon du cercle circonscrit distinct ? Cette question a été posée par Paul Erdös en 1975 qui a lui même proposé une solution en 1978. Toutefois, la preuve a omis par inadvertance un cas non trivial. Nous avons repris ce cas et donné une solution à la question en utilisant des outils de base de la géométrie algébrique et nous fournissons une borne polynomiale pour le nombre de points nécessaires.Dans le chapitre 2, nous sommes intéressés par de généralisations géométriques du critère de Hall pour les couplages dans les graphes bipartits (1935). Nous obtenons des théorèmes géométriques type Hall pour des ensembles convexes disjoints et pour points en position générale dans l'espace euclidien. Les outils de ce chapitre sont topologiques, et l'approche est motivés par une méthode remarquable introduite par Aharoni et Haxell en $2000$ ainsi que par ses généralisations.D'autre part, dans le chapitre 3, nous commençons par un théorème de Helly fractionné de 1979 due à A. Liu et M. Katchalski pour motiver un résultat combinatoire. Nous étudions des conditions combinatoires que des familles de graphes doivent avoir pour permettre d'obtenir des versions plus fine du théorème de Turán. Nous trouvons des liens intéressants entre les nombres de Turán, les nombres chromatiques et les nombres de clique dans la famille. Les outils de ce chapitre sont purement combinatoires.Dans le chapitre 4, nous nous concentrons sur l'obtention des résultats pour la bien connue classe des matroïde chemin du réseau introduite par Bonin, de Mier et Noy en 2003. La contribution principale est de prouver pour cette classe la validité d'une conjecture de Merino et Welsh (1999) sur une inégalité de certaines valeurs du polynôme de Tutte. Pour ce faire, nous introduisons et étudions des serpents, une classe spéciale de matroïdes chemin du réseau ``mince''.Enfin, dans le chapitre 5, nous étudions une variante d'un problème des transversales posé par J.L. Arocha, J. Bracho, L. Montejano et J.L. Ramírez-Alfonsín en 2010. Dans leur travaux originaux, ils ont rémarqué que si nous avons peu de points dans l'espace euclidien alors il est possible de trouver une transversale d'une dimension donnée qui travers les enveloppes convexes de tous les k-ensembles de points. De m&eme, ils montrent qu'il est impossible de trouver une telle transversale lorsque nous avons beaucoup de points. Les auteurs donnent des bornes spécifiques et ils laissent aussi quelques problèmes ouverts. Si la définition de transversale est légèrement plus restrictive, alors le problème peut être étudié en utilisant la théorie des matroïdes orientés. Dans la présente thèse, nous fournissons les détails de cette relation et nous donnons des bornes pour la famille de polytopes cycliques. / Combinatorial geometry is a broad and beautiful branch of mathematics. This PhD Thesis consists of the study of five different topics in this area. Even though the problems and the tools used to tackle them are diverse, they share a unifying goal: To explore the interaction between combinatorial and geometric structures.In Chapter 1 we study a problem by Paul Erdös: for a positive integer k, how many points in general position do we need in the plane so that we can always find a k-subset of them defining triangles with distinct circumradii? This question was posed in 1975 and Erdös himself proposed a solution in 1978. However, the proof inadvertently left out a non-trivial case. We deal with the case using basic tools from algebraic geometry and we provide a polynomial bound for the needed number of points.In Chapter 2 we are interested in providing geometric extensions of Hall's criterion for matchings in bipartite graphs (1935). We obtain geometric Hall-type theorems for pairwise disjoint convex sets and for points in general position in euclidean space. The tools of this chapter are topological, and are motivated by a remarkable method introduced by Aharoni and Haxell in 2000 and its generalizations.On the other hand, in Chapter 3 we begin with a fractional Helly theorem from 1979 by A. Liu and M. Katchalski to motivate a combinatorial result. We study combinatorial conditions on families of graphs that allow us to have sharpened variants of Turán's theorem. We find interesting relations between the Turán numbers, the chromatic numbers and the clique numbers of graphs in the family. The tools in this chapter are only combinatorial.In Chapter 4 we focus on obtaining some results for the well studied class of lattice path matroids introduced by Bonin, de Mier and Noy in 2003. The main contribution is proving for this class the validity of a 1999 conjecture of Merino and Welsh concerning an inequality involving certain values of the Tutte polynomial. In order to do this, we introduce and study snakes, a special class of ``thin'' lattice path matroids.Finally, in Chapter 5 we explore a variant of a transversal problem posed by J.L. Arocha, J. Bracho, L. Montejano and J.L. Ramírez-Alfonsín in 2010. In their original work, they realized that if we have few points in euclidean space then it is possible to find a transversal of a given dimension that goes through all the convex hulls of k-subsets of points. Similarly, they show that it is impossible to find such a transversal when we have many points. The authors give some specific bounds and they also leave some open problems. If the definition of transversal is slightly more restrictive, then the problem can be tackled using oriented matroid theory. We provide the details of the relation and we give bounds for the family of cyclic polytopes.

Depuis plusieurs années, l’aéronautique est confrontée à une mutation majeure due à l’émergence des matériaux composites. Ce changement, justifié par les excellentes propriétés mécaniques des matériaux composites et un gain de masse important, implique une révision complète des réseaux de retour de courant. Pour faciliter cette révision, la thèse propose de lier au travers de l’analyse spectrale des graphes les performances des réseaux électriques avec leur topologie. Deux objectifs couplés sont étudiés : un dimensionnement topologique visant un bon compromis masse/robustesse et une stratégie de surveillance de ces réseaux. / The principles of the electrical system design in future aircrafts have to be reconsidered due to the emergence of new composite materials. The use of these materials for the aircraft structure has indeed implied a complete revision of on-board current return path networks. To facilitate this revision, it is proposed to link through the spectral graph analysis the performances of electrical networks with their topology. The aim of this thesis is to give topological drivers that could help the aeronautical engineers during the design process and then to propose a monitoring methodology.

La question des villes moyennes ou intermédiaires a été largement débattue, en raison de la difficulté à établir leur définition. Un système de villes moyennes particulier est situé au sud du Chili, constitué par les régions de La Araucanía, Los Ríos et Los Lagos. Ce système présente une configuration spatiale plutôt monocentrique, où les interactions entre villes sont développées à l'intérieur de chaque région et, par conséquence, les liens transfrontaliers sont faibles voire inexistants. Les centres urbains à l'intérieur de chaque région développent différents types de configuration spatiale, tant à un niveau régional et que local. Cette thèse a cherché à comprendre les concepts de ville intermédiaire ou moyenne et à les stabiliser, pour pouvoir mieux comprendre le système de villes moyennes du sud du Chili à partir d'une analyse de réseau et du degré de cohésion des différentes villes. Le réseau qui organise ce système est déterminé principalement par les relations hiérarchiques et de type vertical. Ainsi, il existe un élevé degré de dépendance à l'égard des capitales régionales, ce qui organise un réseau monocentrique à l'intérieur de chaque espace régional, où il serait encore possible de trouver des villes isolées. Le degré de polycentrisme pour l'ensemble du système a été estimé moyen à faible. Cette situation est encore plus dramatique au sein de chaque espace régional. Les relations spatiales entre centres urbains se réalisent à deux échelles. Dans la première, trois types d'organisation spatiale se mettent en place et dans la deuxième, trois types d'organisation spatiale ont lieu entre des paires de nœuds du réseau. / Medium-size cities have been the subject of profound debate given their complexity in order to define them. A particular system consisting of this type of cities is located in southern Chile, an area which comprises the regions of La Araucania, Los Ríos and Los Lagos. This system seems to have a monocentric configuration, where interactions between population centers would be arranged within each region and therefore trans-border links would be weak or not present. In addition to that, urban centers that compose the system would have differentiated spatial patterns, both at a regional and local scale. In this sense, this thesis tries to understand the concept of medium-size and intermediate cities and stabilize it, to understand the system of cities of southern Chile thanks to a network approach and the analysis of the cohesion degree in urban centers. The network that organizes this system is determined largely by relations of hierarchical and vertical type, having a high degree of dependency of small cities within a region to each of the regional capitals, which organizes a moncentric network within each regional area, including identifying isolated towns. The degree of polycentrism for the entire system is low and this situation is even deeper within each regional area. The spatial relationships between urban centers are in two scales, first to set up three types of spatial organization and second presents three types of spatial organization that develop between pairs of nodes in the network.

Avec des volumes de données et d’informations de plus en plus importants, des données de plus en plus complexes et fortement inter-reliées, l’extraction de connaissances reste un véritable défi. Les graphes offrent actuellement un support de représentation efficace pour représenter ces données. Parmi les approches existantes, les multi-graphes ont montré que leur pouvoir d’expression était particulièrement adapté pour manipuler des données complexes possédant de nombreux types de relations entre elles. Cette thèse aborde deux aspects principaux liés aux multigraphes : la recherche de sous graphes et la fouille de sous graphes fréquents dans des multigraphes.Elle propose trois propositions dans le domaines du requêtage et de la fouille de données.La première contribution s’inscrit dans la recherche de sous graphes et concerne l’isomorphisme de sous graphes dans des multigraphes. Cette approche peut, par exemple, être appliquée dans de nombreux domaines d’applications comme l’analyse d’images satellites ou de réseaux sociaux. Dans la seconde, nous nous intéressons aux graphes de connaissances et abordons la problématique de l’homorphisme de graphes dans des multigraphes RDF. Dans les deux contributions, nous proposons de nouvelles techniques d’indexations pour représenter efficacement les informations contenues dans les multigraphes. La recherche des sous graphes tire avantage de ces nouveaux index et différentes heuristiques et optimisations sont également proposées pour garantir de bonnes performances lors de l’exécution des requêtes. La seconde contribution s’inscrit dans le domaine de la fouille de données et nous proposons un algorithme efficace pour extraire les multigraphes fréquents. Etant donné l’espace de recherche à considérer, la recherche de motifs fréquents dans des graphes est un problème difficile en fouille de données. Pour parcourir efficacement l’espace de recherche encore plus volumineux pour les multigraphes, nous proposons de nouvelles techniques et méthodes pour le traverser efficacement notamment en éliminant des candidats où détectant à l’avance les motifs non fréquents. Pour chacune de ces propositions de nombreuses expérimentations sont réalisées pour valider à la fois leurs performances et exactitudes en les comparant avec les approches existantes. Finalement, nous proposons une étude de cas sur des jeux de données issues d’images satellites modélisées sous la forme de multigraphe et montrons que l’application de nos propositions permet de mettre en évidence de nouvelles connaissances utiles. / With the ever-increasing growth of data and information, extracting the right knowledge has become a real challenge.Further, the advanced applications demand the analysis of complex, interrelated data which cannot be adequately described using a propositional representation. The graph representation is of great interest for the knowledge extraction community, since graphs are versatile data structures and are one of the most general forms of data representation. Among several classes of graphs, textit{multigraphs} have been captivating the attention in the recent times, thanks to their inherent property of succinctly representing the entities by allowing the rich and complex relations among them.The focus of this thesis is streamlined into two themes of knowledge extraction; one being textit{knowledge retrieval}, where we focus on the subgraph query matching aspects in multigraphs, and the other being textit{knowledge discovery}, where we focus on the problem of frequent pattern mining in multigraphs.This thesis makes three main contributions in the field of query matching and data mining.The first contribution, which is very generic, addresses querying subgraphs in multigraphs that yields isomorphic matches, and this problem finds potential applications in the domains of remote sensing, social networks, bioinformatics, chemical informatics. The second contribution, which is focussed on knowledge graphs, addresses querying subgraphs in RDF multigraphs that yield homomorphic matches. In both the contributions, we introduce efficient indexing structures that capture the multiedge information. The query matching processes introduced have been carefully optimized, w.r.t. the time performance and the heuristics employed assure robust performance.The third contribution is in the field of data mining, where we propose an efficient frequent pattern mining algorithm for multigraphs. We observe that multigraphs pose challenges while exploring the search space, and hence we introduce novel optimization techniques and heuristic search methods to swiftly traverse the search space.For each proposed approach, we perform extensive experimental analysis by comparing with the existing state-of-the-art approaches in order to validate the performance and correctness of our approaches.In the end, we perform a case study analysis on a remote sensing dataset. Remote sensing dataset is modelled as a multigraph, and the mining and query matching processes are employed to discover some useful knowledge.

Dans cette thèse, nous étudions des problèmes d'identification des sommets dans les graphes. Identifier les sommets d'un graphe consiste à attribuer à chaque sommet un objet qui rend le sommet unique par rapport aux autres. Nous nous intéressons particulièrement aux codes identifiants : sous-ensembles de sommets d'un graphe, dominants, tels que le voisinage fermé de chaque sommet du graphe a une intersection unique avec l'ensemble. Les sommets du code identifiant peuvent être considérés comme des capteurs et chaque sommet du graphe comme un lieu possible pour une défaillance. Nous caractérisons tout d'abord l'ensemble des graphes pour lesquels tous les sommets sauf un sont nécessaires dans tout code identifiant. Le problème consistant à trouver un code identifiant optimal, c'est-`a-dire de taille minimale, étant NP-difficile, nous l'étudions sur quatre classes restreintes de graphes. Suivant les cas, nous pouvons résoudre complètement le problème (pour les graphes de Sierpinski), améliorer les bornes générales (pour les graphes d'intervalles, les graphes adjoints, la grille du roi) ou montrer que le problème reste difficile même restreint (pour les graphes adjoints). Nous considérons ensuite des variations autour des codes identifiants permettant plus de flexibilité pour les capteurs. Nous étudions par exemple des capteurs du plan capables de détecter des défaillances `a un rayon connu avec une erreur tolérée. Nous donnons des constructions de tels codes et bornons leur taille pour des valeurs de rayons et d'erreurs fixés ou asymptotiques. Nous introduisons enfin la notion de coloration identifiante d'un graphe, permettant d'identifier les sommets d'un graphe avec les couleurs présentes dans son voisinage. Nous comparons cette coloration avec la coloration propre des graphes et donnons des bornes sur le nombre de couleurs nécessaires pour identifier un graphe, pour plusieurs classes de graphes. / In this thesis, we study problems on vertices identification of graphs. To identify the vertices of a graph consists in giving to each vertex of the graph an object that makes it unique. We are specially interested in the problem of identifying codes : dominating sets of vertices for which the closed neighborhood of each vertex has a unique intersection with the set. The vertices of the identifying code can be seen as sensors and each vertex of the graph as the location of a potential fault. We first classify all finite graphs for which all but one of the vertices are needed in any identifying code. Finding an optimal identifying code, i.e, an identifying code of minimum size, is a $NP$-hard problem. Therefore, we study this problem in some restricted classes of graphes. Depending on the class considered, we are able to solve this problem (for Sierpi`nski graphs), to give better bounds on the size of an identifying code than the general one (for interval graphs, line graphs and the king grid) or to prove that the problem remains NP-hard even in the restricted class (for line graphs). Then, we consider some variations of identifing codes that give flexibility to the sensors. For example, we study codes sensors able to detect faults within a radius around a fixed value. We give constructions of such codes and bounds on their size for general and asymptotic values of the radius and the tolerance on it. Finally, we introduce identifying colourings of graphs; verex-colouring of graph such that each vertex is identified by the set of colours in its closed neighbourhood. We compare this colouring of graphs with proper vertex-coloring and give bounds on the number of colours required to identify a graph, for several class of graphs.

Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code (propriété de domination) et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code (propriété de séparation). Dans cette thèse, nous nous intéressons à des aspects combinatoires et algorithmiques relatifs aux codes identifiants.Pour la partie combinatoire, nous étudions tout d'abord des questions extrémales en donnant une caractérisation complète des graphes non-orientés finis ayant comme taille minimum de code identifiant leur ordre moins un. Nous caractérisons également les graphes dirigés finis, les graphes non-orientés infinis et les graphes orientés infinis ayant pour seul code identifiant leur ensemble de sommets. Ces résultats répondent à des questions ouvertes précédemment étudiées dans la littérature.Puis, nous étudions la relation entre la taille minimum d'un code identifiant et le degré maximum d'un graphe, en particulier en donnant divers majorants pour ce paramètre en fonction de l'ordre et du degré maximum. Ces majorants sont obtenus via deux techniques. L'une est basée sur la construction d'ensembles indépendants satisfaisant certaines propriétés, et l'autre utilise la combinaison de deux outils de la méthode probabiliste : le lemme local de Lovasz et une borne de Chernoff. Nous donnons également des constructions de familles de graphes en relation avec ce type de majorants, et nous conjecturons que ces constructions sont optimales à une constante additive près.Nous présentons également de nouveaux minorants et majorants pour la cardinalité minimum d'un code identifiant dans des classes de graphes particulières. Nous étudions les graphes de maille au moins 5 et de degré minimum donné en montrant que la combinaison de ces deux paramètres influe fortement sur la taille minimum d'un code identifiant. Nous appliquons ensuite ces résultats aux graphes réguliers aléatoires. Puis, nous donnons des minorants pour la taille d'un code identifiant des graphes d'intervalles et des graphes d'intervalles unitaires. Enfin, nous donnons divers minorants et majorants pour cette quantité lorsque l'on se restreint aux graphes adjoints. Cette dernière question est abordée via la notion nouvelle de codes arête-identifiants.Pour la partie algorithmique, il est connu que le problème de décision associés à la notion de code identifiant est NP-complet même pour des classes de graphes restreintes. Nous étendons ces résultats à d'autres classes de graphes telles que celles des graphes split, des co-bipartis, des adjoints ou d'intervalles. Pour cela nous proposons des réductions polynomiales depuis divers problèmes algorithmiques classiques. Ces résultats montrent que dans beaucoup de classes de graphes, le problème des codes identifiants est algorithmiquement plus difficile que des problèms liés (tel que le problème des ensembles dominants).Par ailleurs, nous complétons les connaissances relatives à l'approximabilité du problème d'optimisation associé aux codes identifiants. Nous étendons le résultat connu de NP-difficulté pour l'approximation de ce problème avec un facteur sous-logarithmique (en fonction de la taille du graphe instance) aux graphes bipartis, split et co-bipartis, respectivement. Nous étendons également le résultat connu d'APX-complétude pour les graphes de degré maximum donné à une sous-classe des graphes split, aux graphes bipartis de degré maximum 4 et aux graphes adjoints. Enfin, nous montrons l'existence d'un algorithme de type PTAS pour les graphes d'intervalles unitaires. / An identifying code is a set of vertices of a graph such that, on the one hand, each vertex out of the code has a neighbour in the code (domination property), and, on the other hand, all vertices have a distinct neighbourhood within the code (separation property). In this thesis, we investigate combinatorial and algorithmic aspects of identifying codes.For the combinatorial part, we first study extremal questions by giving a complete characterization of all finite undirected graphs having their order minus one as minimum size of an identifying code. We also characterize finite directed graphs, infinite undirected graphs and infinite oriented graphs having their whole vertex set as unique identifying code. These results answer open questions that were previously studied in the literature.We then study the relationship between the minimum size of an identifying code and the maximum degree of a graph. In particular, we give several upper bounds for this parameter as a function of the order and the maximum degree. These bounds are obtained using two techniques. The first one consists in the construction of independent sets satisfying certain properties, and the second one is the combination of two tools from the probabilistic method: the Lovasz local lemma and a Chernoff bound. We also provide constructions of graph families related to this type of upper bounds, and we conjecture that they are optimal up to an additive constant.We also present new lower and upper bounds for the minimum cardinality of an identifying code in specific graph classes. We study graphs of girth at least 5 and of given minimum degree by showing that the combination of these two parameters has a strong influence on the minimum size of an identifying code. We apply these results to random regular graphs. Then, we give lower bounds on the size of a minimum identifying code of interval and unit interval graphs. Finally, we prove several lower and upper bounds for this parameter when considering line graphs. The latter question is tackled using the new notion of an edge-identifying code.For the algorithmic part, it is known that the decision problem associated to the notion of an identifying code is NP-complete, even for restricted graph classes. We extend the known results to other classes such as split graphs, co-bipartite graphs, line graphs or interval graphs. To this end, we propose polynomial-time reductions from several classical hard algorithmic problems. These results show that in many graph classes, the identifying code problem is computationally more difficult than related problems (such as the dominating set problem).Furthermore, we extend the knowledge of the approximability of the optimization problem associated to identifying codes. We extend the known result of NP-hardness of approximating this problem within a sub-logarithmic factor (as a function of the instance graph) to bipartite, split and co-bipartite graphs, respectively. We also extendthe known result of its APX-hardness for graphs of given maximum degree to a subclass of split graphs, bipartite graphs of maximum degree 4 and line graphs. Finally, we show the existence of a PTAS algorithm for unit interval graphs.

The thesis focuses on two open problems on finite partially ordered sets: the structure of order polytopes and the approximation of the number of linear extensions of a poset by mean of graph entropy. The polytopes considered here are the linear ordering polytope, the semiorder polytope, the interval order polytope, the partial order polytope and also a generalisation of the linear ordering polytope: the linear extension polytope of a fixed poset P. Various results on the structure of theses polytopes are proved in the first part of the thesis. In the second part of the thesis, we improve the existing bounds linking the entropy of the incomparability graph of the poset P and its number of linear extension. / Le but de la thèse est d'étudier deux problèmes ouverts sur les ensembles ordonnés finis: la structure des polytopes d'ordre et l'approximation du nombre d'extensions linéaires d'un ordre partiel au moyen de la notion d'entropie de graphe. Les polytopes considérés sont le polytope des ordres totaux, le polytope des semiordres, le polytope des ordres d'intervalles, le polytope des ordres partiels, ainsi qu'une généralisation du polytope des ordres totaux: le polytope des extensions linéaires d'un ensemble ordonné fixé P. Des résultats sur la structure de ces polytopes sont présentés dans la première partie de la thèse. Dans la deuxième partie de la thèse, nous améliorons les bornes existantes liant l'entropie du graphe d'incomparabilité d'un ordre partiel et son nombre d'extensions linéaires. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Avec le développement des applications temps-réel sur Internet, telles que la télévision, la voix sur IP et les jeux en ligne, les fournisseurs d'accès à Internet doivent faire face à des contraintes de plus en plus fortes quant aux performances de leurs services. Cependant, après chaque changement topologique, les protocoles de routage à état des liens, utilisés dans les réseaux de cœur de ces opérateurs, entrent dans une période de convergence durant laquelle des boucles de routage peuvent apparaître. Ce phénomène dégrade les performances du réseau (latence, congestions, pertes de paquets) et peut durer plusieurs secondes. Dans le cadre de cette thèse, nous proposons de nouvelles solutions permettant de prévenir ces perturbations dans le cas de reconfigurations sur un lien ou un routeur. Notre approche a pour particularité de ne reposer que sur les mécanismes de base des protocoles de routage à état des liens, et d’être ainsi déployable de manière incrémentale dans n’importe quel réseau. Intuitivement, il s’agit de contrôler implicitement l’ordre de mise à jour des routeurs, à travers une modification progressive du poids d’un sous-ensemble de liens. Par exemple, l’augmentation du poids d’un lien aura pour effet de forcer les routeurs les plus éloignés de ce composant à se mettre à jour avant les routeurs plus proches. En adaptant finement l’amplitude de tels changements, il est alors possible de répartir la mise à jour de routeurs potentiellement impliqués dans une boucle sur plusieurs étapes. Cette opération peut ensuite être répétée jusqu’à ce que le composant ne soit plus utilisé pour acheminer des données dans le réseau, permettant un retrait sans impact sur le routage. / The use of real time media or mission critical applications over IP networks is making strong pressure on service providers to operate disruption free networks. However, after any topological change, link-state Interior Gateway Protocols (IGPs), such as IS-IS or OSPF, enter a convergence phase during which transient forwarding loops may occur. Such loops increase the network latency and cause packet losses for several seconds. In this thesis, we propose and evaluate innovative solutions to prevent these perturbations in case a planned modification on a link or a router. Our approach only relies on core functionalities of link-state routing protocols, thus being incrementally deployable in any network. Intuitively, it consists in implicitly controlling the routers update order through successive IGP weight reconfigurations on a subset of links. For example, progressively increasing the weight of a link forces farthest routers to update their routes first, before closest ones. Hence, finely tuning such changes may allow to spread the update of routers potentially implied in a loop across multiple steps. This operation can be repeated until the component to be removed is no longer used to forward traffic in the network, thus allowing its removal with no impact on the routing decisions.

Soit un réseau comprenant des lignes de communication qui échouent indépendamment, dans lequel tous ou certains sites, appelés terminaux, doivent être capables de communiquer entre eux. Dans le modèle stochastique statique classique le réseau est représenté par un graphe probabiliste dont les arêtes sont présentes selon des probabilités connues. La mesure de fiabilité classique (CLR) est la probabilité que les terminaux appartiennent à la même composante connexe. Dans plusieurs contextes il est utile d'imposer la condition plus forte que la distance entre deux terminaux quelconques soit bornée supérieurement par un paramètre d. La probabilité que ça se produise est connue comme la fiabilité diamètre-bornée (DCR). Il s'agit d'une extension de la CLR. Les deux problèmes appartiennent à la classe NP-difficile de complexité; le calcul exact n'est possible que pour les instances de taille limitée ou topologies spécifiques. Dans cette thèse, nous contribuons des résultats concernant le problème du calcul et l'estimation de la DCR. Nous étudions la complexité de calcul de cas particuliers, paramétré par le nombre de terminaux, nœuds et le paramètre d. Nous passons en revue des méthodes pour le calcul exact et étudions des topologies particulières pour lesquelles le calcul de la DCR a une complexité polynomiale. Nous introduisons des résultats de base sur le comportement asymptotique de la DCR lorsque le réseau se développe comme un graphe aléatoire. Nous discutons sur l'impact de la contrainte de diamètre dans l'utilisation des techniques de Monte Carlo, et adaptons et testons une famille de méthodes basées sur le conditionnement de l'espace d'échantillonnage en utilisant des structures nommées d-pathsets et d-cutsets. Nous définissons une famille de mesures de performabilité qui généralise la DCR, développons une méthode de Monte Carlo pour l'estimer, et présentons des résultats expérimentaux sur la performance de ces techniques Monte Carlo par rapport é l'approche naïve. Finalement, nous proposons une nouvelle technique qui combine la simulation Monte Carlo et l'interpolation polynomiale pour les mesures de fiabilité. / Consider a communication network whose links fail independently and a set of sites named terminals that must communicate. In the classical stochastic static model the network is represented by a probabilistic graph whose edges occur with known probabilities. The classical reliability (CLR) metric is the probability that the terminals belong to a same connected component. In several contexts it makes sense to impose the stronger condition that the distance between any two terminals does not exceed a parameter d. The probability that this holds is known as the diameter-constrained reliability (DCR). It is an extension of the CLR. Both problems belong to the NP-hard complexity class; they can be solved exactly only for limited-size instances or specific network topologies. In this thesis we contribute a number of results regarding the problem of DCR computation and estimation. We study the computational complexity of particular cases parameterized by the number of terminals, nodes and the parameter d. We survey methods for exact computation and study particular topologies for which computing the DCR has polynomial complexity. We give basic results on the asymptotic behavior of the DCR when the network grows as a random graph. We discuss the impact that the diameter constraint has in the use of Monte Carlo techniques. We adapt and test a family of methods based on conditioning the sampling space using structures named d-pathsets and d-cutsets. We define a family of performability measures that generalizes the DCR, develop a Monte Carlo method for estimating it, and present numerical evidence of how these techniques perform when compared to crude Monte Carlo. Finally we introduce a technique that combines Monte Carlo simulation and polynomial interpolation for reliability metrics.