EUROPEAN AIR HUBS IN THE CONTEXT OF NETWORK AND ITS RESISTANCE AGAINST DISTURBANCES Abstract The submitted master thesis is addressing the theme of connectivity of European Air Transport Network, its properties and resistance against negative influences based on data from flight schedules for winter season 2018. The main objective of the thesis is to analyse European Air Transport Network from the point of connectivity in order to find out the most important airport hubs according to their geographic conditions, community structure and resistance of the whole network. Used methods are based on the Graph Theory and the centrality measures as indicators of connectivity. The empiric part of the thesis is divided into three parts. The aim of the first part is to find out, what airports are the most important in the European Air Transport Network. In the second part are explored properties and structure of the network. The last part is aiming to analyse the resistance of the European Air Transport Network from the view of robustness and resilience. Among the most important air hubs in Europe belong airports, that are serving world cities and tourist attractive localities. There is a strong dominance of the Schiphol airport in Amsterdam, the El Prat airport in Barcelona and the Frankfurt Airport. The European Air...

Neste trabalho estudamos um pouco de Teoria dos Grafos, abordando diversas definições e teoremas interessantes. Apresentamos o Teorema das Quatro Cores, desde o surgimento do problema com Francis Guthrie. Analisamos a demonstração do teorema realizada por Alfred Bray Kempe e sua refutação através do contraexemplo de Percy John Heawood. Analisamos também a demonstração do Teorema das Cinco Cores de Percy John Heawood. Porém, apresentamos a primeira demonstração válida do Teorema das Quatro Cores, como sua particularidade de ter sido feita com o auxílio de um computador. O trabalho é concluído com uma análise sobre os benefícios que o conhecimento de Teoria dos Grafos pode render aos alunos do Ensino Básico, e como professor o pode trabalhar este assunto em sala de aula, inclusive abordando o problema de coloração de mapas. / In this paper we study Graph Theory, addressing various definitions and interesting theorems. We present the Four Color Theorem, since the origin of the problem with Francis Guthrie. We analyze the proof of the theorem presented by Alfred Bray Kempe, and its refutation by Percy John Heawood counter-example. We also analyze the Percy John Heawood demonstration of the Five Color Theorem. Finally, we present the first valid proof of the Four Colors Theorem, with its peculiarity of having been done with the aid of a computer. We conclude with an analysis of the beneficial that the knowledge of Graph Theory can render students of Basic Education, and how a teacher can work this topic in the classroom, including addressing the problem of map coloring.

O Problema do Multicorte Dirigido Mínimo é um problema clássico em otimização combinatória. Ele é NP-difícil mesmo para instâncias muito simples. Este trabalho faz uma análise dos algoritmos exatos e de aproximação para resolver o problema. Também implementa alguns desses algoritmos e compara seus desempenhos. / The directed multicut problem is a classical problem in combinatorial optimization. It is NP-hard even for very simple families of instances. This work makes an analysis of the exact and approximation algorithms for the problem. It also implements some of these algorithms and compares their performances.

Les réseaux sont présents dans plusieurs domaines scientifiques et d’ingénierie tels que la biologie, la physique, la sociologie ainsi que la robotique ou la théorie de la communication. L’étude de ces réseaux montre qu’ils sont souvent structurés en sous-groupes. Entre eux il n’y a pas ou il y a très peu d’interaction. Par conséquent, un accord local au sein de chaque groupe est naturellement atteint alors que le consensus associé à un tel réseau doit être imposé par une loi de commande spécifique. Nous proposons donc un contrôleur discret quasi-périodique pour échanger des informations entre les groupes. Un agent de chaque groupe est choisi le « leader » et, à certains moments, ces leaders communiquent entre eux à travers un nouveau réseau. Ceci permet d’obtenir le consensus dans tout le réseau mais engendre des réinitialisation/sauts dans l’état de leaders. La première contribution de la thèse est la caractérisation de la valeur de consensus dans le cadre des systèmes linéaires impulsifs. Il est remarquable que la valeur de consensus dépende seulement des conditions initiales et des topologies des réseaux impliqués. Elle n’est donc pas sensible aux instants de réinitialisation des états de leaders. Afin d’étudier la stabilité de la valeur de consensus obtenue, nous proposons une méthode fondée sur la vérification d’une condition LMI. Cela peut être adaptée pour la conception du réseau d’interaction entre les leaders permettant d’atteindre une valeur de consensus a priori choisie. Il est aussi possible d’utiliser la condition LMI afin de garantir une vitesse de convergence désirée vers le consensus. Pour ces derniers objectifs, la topologie du réseau continue à être considérée comme fixe et connue pour chaque groupe. L’ensemble des valeurs de consensus qui peuvent être atteintes est contenu dans l’intervalle défini par le minimum et le maximum des accords locaux initiaux. Ensuite nous présentons l’étude d’un problème pratique. Des robots mobiles non-holonome, séparés dans des groupes, doivent atteindre une formation donnée. L’algorithme de consensus à pour mission de définir les trajectoires de référence pour ces robots en prenant en compte juste les informations locale. Le robot poursuit la trajectoire de référence en utilisant une commande classique pour cela. / Networks appear in several areas of science and engineering such as biology, physics, sociology as well as robotics and communication theory. Studying these networks it is possible to see cluster-like structures, which are disconnected or very weakly connected one to another. The presence of these clusters hampers consensus throughout the overall network. Instead, local agreement is reached within each cluster. To enforce consensus we have to design an appropriate decentralized controller that imposes interactions between clusters. While the interactions inside each cluster are continuous, we propose a quasi-periodic discrete controller to exchange information between clusters. A single agent from each cluster is chosen to be the leader, and at certain moments, the leaders communicate with each other through a new network. This allows consensus in the entire network but generates resets/jumps on the leaders’ state. The first contribution of this manuscript is related to the characterization of the consensus value in the linear impulsive dynamics framework. It is noteworthy that the consensus value depends only on the initial conditions and the topologies of the involved networks. Therefore, the consensus value does not depend on the reset sequence used for the leaders’ states. To study the stability of the consensus value a LMI based condition is proposed. The main advantage of this approach is its flexibility. Indeed with some modifications to the LMI condition it is possible to analyse the convergence speed of the network or to design the leaders’ network. The purpose of leaders’ network design is to reach an a priori specified consensus value with a specified convergence speed. Whatever is the objective, throughout the manuscript we consider that the network topology is fixed and known for each cluster. The set of consensus values that can be reached is restricted to the interval defined by the minimum and maximum initial local agreements. A last contribution is related to the application of the proposed methodology to a practical situation. We consider a fleet of non-holonomic mobile robots separated in clusters. The communication inside each cluster are secured and cheap while between clusters it is expensive and not securely to communicate. Nevertheless the robots have to reach a given formation. In this case our consensus algorithm is in charge of providing reference trajectories to each robot by using only the available local information. The robot follows the reference by using a classical trajectory tracking control.

Dans cette thèse, nous étudions des problèmes de transversaux d'un point de vue tant algorithmique que combinatoire. Etant donné un hypergraphe, un transversal est un ensemble de sommets qui touche toutes les hyperarêtes. Un packing est un ensemble d'hyperarêtes deux à deux disjointes. Alors que la taille minimale d'un transversal est au moins égale à la taille maximale d'un packing on ne peut pas dans le cas général borner la taille minimale d'un transversal par une fonction du packing maximal. Dans un premier temps, un état de l'art rappelle les différentes conditions qui assurent l'existence de bornes supérieures sur la taille des transversaux, en particulier en fonction de la taille d'un packing. La plupart d'entre elles sont valables lorsque la VC-dimension de Vapnik-Chervonenkis de l'hypergraphe, est bornée. L'originalité de la thèse consiste à utiliser ces outils d'hypergraphes pour obtenir des résultats sur des problèmes de graphes. Nous prouvons notamment une conjecture de coloration de Scott dans le cas des graphes sans-triangle maximaux; ensuite, nous généralisons un résultat de Chepoi, Estellon et Vaxès traitant de domination à grande distance; enfin nous nous attaquons à une conjecture de Yannakakis sur la séparation des cliques et des stables d'un graphe.Dans un second temps, nous étudions les transversaux d'un point de vue algorithmique. On se concentre plus particulièrement sur les problèmes de séparation de graphe où on cherche des transversaux à un ensemble de chemin. En combinant des outils de connexité, les séparateurs importants et le théorème de Dilworth, nous obtenons un algorithme FPT pour le problème Multicut paramétré par la taille de la solution. / In this manuscript we study hitting sets both from a combinatorial and from an algorithmic point of view. A hitting set is a subset of vertices of a hypergraph which intersects all the hyperedges. A packing is a subset of pairwise disjoint hyperedges. In the general case, there is no function linking the minimum size of a hitting set and a maximum size of a packing.The first part of this thesis is devoted to present upper bounds on the size of hitting sets, in particular this upper bounds are expressed in the size of the maximum packing. Most of them are satisfied when the dimension of Vapnik-Chervonenkis of the hypergraph is bounded. The originality of this thesis consists in using these hypergraph tools in order to obtain several results on graph problems. First we prove that a conjecture of Scott holds for maximal triangle-free graphs. Then we generalize a result of Chepoi, Estellon and Vaxès on dominating sets at large distance. We finally study a conjecture of Yannakakis and prove that it holds for several graph subclasses using VC-dimension.The second part of this thesis explores algorithmic aspects of hitting sets. More precisely we focus on parameterized complexity of graph separation problems where we are looking for hitting sets of a set of paths. Combining connectivity tools, important separator technique and Dilworth's theorem, we design an FPT algorithm for the Multicut problem parameterized by the size of the solution.

L’accouchement prématuré est l’un des problèmes majeurs en obstétrique. Par suite, il a été un sujet d'intérêt pour de nombreux chercheurs. Parmi les nombreuses méthodes utilisées pour enregistrer la contractilité utérine, le plus utilisé est l'EHG abdominal, comme étant un outil facile à utiliser et non invasif. De nombreuses études ont indiqué que l'utilisation de ce signal pourrait être un outil très puissant pour surveiller la grossesse et pour détecter le travail. Il permet en effet d'accéder à l'utérus ainsi que la synchronisation de l'activité utérine, en utilisant des signaux multiples. Il a été démontré que l'analyse de connectivité des signaux EHG a donné des résultats prometteurs en application clinique, comme la classification des contractions de travail et de grossesse. Cependant, dans presque toutes les études antérieures, les matrices de corrélation EHG étaient souvent réduites en ne gardant que leur moyenne et les écarts-types, ce qui a peut aboutir à perdre des informations pertinentes en raison de ce moyennage, ce qui peut induire le taux de classification relativement faible jusqu'à présent. Pour caractériser précisément la matrice de corrélation et quantifier la connectivité associée, nous avons proposé dans cette thèse d'utiliser une technique de mesure de réseau basée sur la théorie des graphes. Selon cette approche, la matrice de corrélation obtenue peut être représentée sous forme de graphiques constitués d'un ensemble de nœuds (électrodes) interconnectés par des arêtes (valeurs de connectivité / corrélation entre électrodes). La nouvelle procédure de l'analyse des signaux EHG enregistrés pendant la grossesse et le travail se base sur la caractérisation de la corrélation entre les activités électriques utérines et sur sa quantification précise en utilisant l'approche de la théorie des graphes. Le pipeline de traitement inclut i) l'estimation des dépendances statistiques entre les différents signaux EHG enregistrés, ii) la quantification des matrices de connectivité obtenues à l'aide de l'analyse théorique des graphes et iii) l'utilisation clinique des mesures de réseau pour la surveillance de la grossesse ainsi que la classification entre les éclosions d'EHG de grossesse et de travail. Une comparaison avec les paramètres déjà existants utilisés pour la détection du travail et la détection d’accouchement prématuré sera également effectuée. Nous étudions également une nouvelle méthode pour étudier la connectivité source EHG, afin de surmonter le problème du calcul de la connectivité au niveau de la surface abdominale. Les résultats de cette thèse montrent que cette approche basée sur la théorie de graphe est un outil très prometteur pour quantifier la synchronisation utérine, lorsqu'elle est appliquée à l'abdomen, pour une meilleure surveillance de la grossesse. Nous espérons que cette approche soit utilisée pour le suivi de la grossesse et contribuerait ainsi à la prédiction précoce de l’accouchement prématuré. / Preterm birth remains a major problem in obstetrics. Therefore, it has been a topic of interest for many researchers. Among the many methods used to record the uterine contractility, the most used is the abdominal EHG, as being an easy to use and a non-invasive tool. Many studies have reported that the use of this signal could be a very powerful tool to monitor pregnancy and to detect labor. It indeed permits to access the uterine as well as the synchronization of the uterine activity, by using multiple signals. It has been shown that the connectivity analysis gave promising results when using EHG recordings in clinical application, such as the classification labor/pregnancy contractions. However, in almost all previous studies EHG correlation matrices were often reduced keeping only their mean and standard deviations thus relevant information may have been missed due to this averaging, which may induce the relatively low classification rate reported so far. To characterize precisely the correlation matrix and quantify the associated connectivity, we proposed in this thesis to use a network measure technique based on graph theory. According to this approach, the obtained correlation matrix can be represented as graphs consisting of a set of nodes (electrodes) interconnected by edges (connectivity/correlation values between electrodes). The new framework, to analyze the EHG signals recorded during pregnancy and labor, is based on the characterization of the correlation between the uterine electrical activities and on its precise quantification by using graph theory approach. The processing pipeline includes i) the estimation of the statistical dependencies between the different recorded EHG signals, ii) the quantification of the obtained connectivity matrices using graph theory-based analysis and iii) the clinical use of network measures for pregnancy monitoring as well as for the classification between pregnancy and labor EHG bursts. A comparison with the already existing parameters used in the state of the art for labor detection and preterm labor prediction will also be performed. We also investigate a new method to study the EHG source connectivity, to overcome the problem of computing the connectivity at the abdominal surface level. The results of this thesis showed that this network-based approach is a very promising tool to quantify uterine synchronization, when applied at the abdominal level, for a better pregnancy monitoring. We expect this approach to be further used for the monitoring of pregnancy and would thus help for the early prediction of preterm labor.

A capacidade das células para responder corretamente a sinais externos e perceber mudanças no seu microambiente é a base do desenvolvimento, reparação de tecidos e de imunidade, bem como a homeostase do tecido normal. Transdução de sinal é o principal meio pelo qual as células respondem a sinais externos de seu ambiente e coordenam alterações celulares complexas. O estudo das vias de sinalização molecular permite-nos tentar compreender o funcionamento dessas transduções de sinais e, consequentemente, as respostas celulares a estímulos externos. Uma abordagem adequada para tais estudos é o uso de modelos matemáticos para simular a cinética das reações químicas que descrevem uma dada via de sinalização, o que nos permite gerar predições testáveis de processos celulares. Construir modelos cinéticos preditivos de vias de sinalização molecular através de dados de alto rendimento produzidos utilizando técnicas ômicas (i.e., genômica, transcriptômica, (fosfo-)proteômica) constitui um dos atuais desafios enfrentados pelos pesquisadores na área de Biologia Molecular. Recentemente, para lidar com este desafio, o arcabouço de e-Science SigNetSim foi introduzido pelo Grupo de Biologia Computacional e de Bioinformática do Instituto Butantan. Esse arcabouço permite fazer a descrição de vias de sinalização molecular através da descrição da estrutura de um modelo através de um conjunto de reações químicas, que por sua vez é mapeado para um sistema de Equações Diferencias Ordinárias (EDOs), numericamente simuladas e avaliadas. Todavia, modificações na estrutura das vias precisam ser feitas manualmente, o qual restringe severamente o número de estruturas da via que precisam ser testadas, especialmente no caso de modelos grandes. Portanto, diante desse panorama, este trabalho propõe o desenvolvimento de um método para modificar vias de sinalização molecular. Esse método se baseia no uso de bancos de dados de interatomas para fornecer um conjunto de espécies químicas candidatas para serem incluídas na via de sinalização. Um componente integrado ao arcabouço SigNetSim capaz de testar diferentes hipóteses de modificação de vias foi desenvolvido neste projeto utilizando a metodologia de heurística incremental. Para avaliar a eficiência do componente implementado, utilizamos como estudo de caso um modelo de vias sinalização de MAPKs e PI3K/Akt para realizar testes experimentais e analisar os resultados obtidos. / The ability of cells to respond correctly external signals and to perceive changes in their microenvironment is the basis for development, tissue repair and immunity as well as normal tissue homeostasis. Signal transduction is the primary means by which cells respond to external signals from their environment and coordinate complex cellular changes. The study of molecular signaling pathways allows us to understand the operation of each process of cellular signal transduction. The use of mathematical models to simulate the kinetics of chemical reactions that describe a given signaling pathway, allow us to generate testable predictions of the cell processos. To Build Kinetic predictive models to molecular signaling pathways through massive data omics produced using modern techniques, Genomics, transcriptomics, (Phospho) proteomics, is one of the current challenges faced by researchers in the field of molecular biology. Recently, the \\textit SigNetSim e-Science was introduced by the Biological Computacional and Bioinformatical Group from the Butantan Institute to face this challenge. This \\textit makes the description of molecular signaling pathways through a set of chemical reactions, which are mapped into a system of ordinary differential equations, this system will be numerically simulated and evaluated . However, changes in the structure of the pathways need to be updated manually presented in this work, which severely restricts the number of track structures that need to be tested, especially for the large models. Therefore, given this background, we present the method to modify the molecular signaling pathways. This method relies on the use of interactome database to provide a set of chemical species candidates to be included in the signaling pathway. An component integrated to SigNetSim framework able to test different hypotheses of pathways modification was developed in this project using the incremental heuristic methodology. To evaluate the implemented component, we used the MAPKs and PI3K/Akt pathways model as case study, in order to perform experimental tests and to analyze the obtained results.

Nesta tese apresentamos uma metodologia de mapeamento capaz de gerar representações em termos de grafos para sistemas biológicos de conectividade complexa. Tais sistemas são inicialmente armazenados na forma de imagens digitais e em seguida submetidos a um pré-processamento com objetivo de padronizar as imagens. As imagens pré-processadas são então utilizadas para gerar modelos tridimensionais dos sistemas de interesse. Um algoritmo de propagação de rótulos é utilizado para extrair os esqueletos dos modelos volumétricos e estes esqueletos são por fim, representados por um grafo, composto por vértices e arestas. Os vértices e arestas desse grafo armazenam propriedades do sistema original, como posição, comprimento e diâmetro, bem como as características topológicas de tais sistemas. Finalmente, os grafos resultantes são estudados através da teoria das redes complexas, dentro de um contexto específico para cada sistema. Nossos procedimentos foram aplicados com sucesso a diferentes sistemas biológicos, como artérias caríotidas, árvores arteriais, estruturas mitocondriais e poros em amostras de solo. / In the present work, we developed a mapping methodology able to build a graph representation for biological branched systems. Initially, such systems are stored as digital images and then they undergo a pre-processing in order to standardize the images. The pre-processed imagens are used to build tridimensional models of the interested systems. A label-propagation algorithm is used to extract the skeleton from the volumetric models and these skeletons are then represented by a graph, composed by nodes and edges. The nodes and edges of these graphs store properties of the original system, such as spatial position, lengths and diameter, as well as the topological features of such systems. Finally, the graphs are studied by using the complex networks theory within a specific context for each system. Our procedures were apllied sucefully to different biological systems, such as carotid artery, arterial trees, mitocondrial structure and pores in soil samples.

Geometrically representable graphs are extensively studied area of research in contempo- rary literature due to their structural characterizations and efficient algorithms. The most frequently studied class of such graphs is the class of interval graphs. In this thesis we focus on two problems, generalizing the problem of recognition, for classes related to interval graphs. In the first part, we are concerned with adjusted interval graphs. This class has been studied as the right digraph analogue of interval graphs. For interval graphs, there are polynomial algorithms to extend a partial representation by given intervals into a full interval representation. We will introduce a similar problem - the partial ordering extension - and we will provide a polynomial algorithm to extend a partial ordering of adjusted interval digraphs. In the second part, we show two NP-completeness results regarding the simultaneous representation problem, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some k graphs can be represented so that every vertex is represented by the same object in each representation. We prove that it is NP-complete to decide this for the class of interval and circular-arc graphs in the case when k is a part of the input and graphs...

Convex geometries are combinatorial structures; they capture in an abstract way the essential features of convexity in Euclidean space, graphs or posets for instance. A convex geometry consists of a finite ground set plus a collection of subsets, called the convex sets and satisfying certain axioms. In this work, we study two natural problems on convex geometries. First, we consider the maximum-weight convex set problem. After proving a hardness result for the problem, we study a special family of convex geometries built on split graphs. We show that the convex sets of such a convex geometry relate to poset convex geometries constructed from the split graph. We discuss a few consequences, obtaining a simple polynomial-time algorithm to solve the problem on split graphs. Next, we generalize those results and design the first polynomial-time algorithm for the maximum-weight convex set problem in chordal graphs. Second, we consider the realizability problem. We show that deciding if a given convex geometry (encoded by its copoints) results from a point set in the plane is ER-hard. We complete our text with a brief discussion of potential further work. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished