|
|
Applications of graph theory in protein function prediction
Kalábová, Nikola ; Hartman, David (advisor) ; Kratochvíl, Miroslav (referee)
The rapid development of the whole-genome sequencing methods and their reducing cost resulted in a huge number of sequenced genomes. Developing reliable methods for in- silico annotation of the expeditiously growing number of sequenced genomes is the next challenge of modern biology. We described a graph-theoretical approach for function prediction from the protein-protein interaction networks and outlined its strengths and weaknesses. We illustrate the principles of this approach on selected algorithms based on different ideas and provide their comparison and evaluation. 1
|
|
|
Lotka-Volterra competition model on graphs
Skácelová, Radka ; Šremr, Jiří (referee) ; Čermák, Jan (advisor)
This bachelor thesis analyzes several mathematical models describing the co-existence of two species, especially the classic Lotka-Volterra model and its extensions. These models are described by a system of non-linear differential equations. The goal of this thesis is to develop an extended predator-prey model using the graph theory, to find stationary states of this model and to analyze their stability. The thesis is furthermore focused on a comparison between the obtained results for this model with the existing results for the competition model on graphs.
|
|
|
Analysis of security relationships in networks of entities
Kuklisová, Anikó ; Nečaský, Martin (advisor) ; Kopecký, Michal (referee)
The goal of this master thesis is to design and implement an analytical application for Security Information Service by providing a software prototype. The solution proposes an enhancement of existing graph that allows security analytics to analyse, edit and visualize objects and relations that are saved into a relational database. In the thesis, we walk through the process of development step by step. First, we investigate the current version software and the requirements of the customer. Afterwards, we design the architecture to be easily extendable with new modules and reliable libraries. In the next step, we implement the application, present our solution to the customer and conduct excessive testing. The final step is evaluating our solution by comparing it to the current software solution in use.
|
|
|
Algorithmic aspects of intersection-defined graph classes
Jedličková, Nikola ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
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...
|
|
|
Compact I/O-Efficient Graph Representations
Tětek, Jakub ; Gavenčiak, Tomáš (advisor) ; Mareš, Martin (referee)
The objective of this thesis is to develop a fast memory-efficient representa- tion of some graphs that occur in real-world applications. We consider separable graph classes (e.g. planar graphs or graphs of bounded genus) and show how to represent them in a way that (1) makes accessing vertices in a walk cache-efficient on average and (2) is highly memory-efficient. In particular, we show a compact representation of separable graph classes with the I/O cost of a random walk of length k being O(K/(Bw)1−c ) w.h.p. In the second part of the thesis, we consider layout of trees with optimal worst-case I/O cost for root-to-leaf traversal, show an additive (+1)-approximation of I/O optimal compact layout and contrast this with a proof of NP-hardness of exact solution. In this thesis, we also prove generalisations of the recursive separator theo- rem. The first one generalises the theorem for weighted graphs and the second one replaces minimum region size by average region size in the bound. 1
|
|
|
European air hubs in the context of network and its resistance against disturbances
Šulc, David ; Marada, Miroslav (advisor) ; Kraft, Stanislav (referee)
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...
|
|
|
Logistic problems and their applications
Žlebek, Petr ; Nevrlý, Vlastimír (referee) ; Pavlas, Martin (advisor)
The thesis deals with transportation problems using optimization methods. The first part summarizes theoretical facts about the graph theory, mathematical programming, transportation problems and genetic algorithm. Those informations are used in the second part of the thesis where the specific transportation model dealing with waste collection management is described. The model is implemented in Matlab environment. Real data from the area of Czech republic are then applied to the model. Finally the results are throughly discussed.
|
|
|
Network simplex method
Khýr, Lukáš ; Janošťák, František (referee) ; Popela, Pavel (advisor)
This thesis is focused on summary knowledges relating to mathematical modeling in optimization area. We will deal with simplex method in detail and especially its network modification, which is used in various practical applications. We will solve tasks of various sizes and compare their solutions using implementation these two methods in Matlab. There is solved a task with real data provided by the Institute of Process Engineering at the end of the work.
|
|
|
Integrated method utilizing graph theory and fuzzy logic for safety and reliability assessment of airborne systems
Janhuba, Luboš ; Hlinka, Jiří ; Koštial, Rostislav
This paper presents integrated algorithm for airborne system safety and reliability assessment. In general aviation (mostly up to EASA CS-23) and non-military unmanned aerial vehicles industry, safety and reliability assessment process still relays almost exclusively on human judgment. Recommended practices define processes for system modelling and safety assessing are based on analyst understanding of a particular system. That is difficult and time-consuming process. Commercial computation aids are extremely expensive with restricted (or closed) access to the solution algorithms. Together with this problem, rapid development of modern airborne systems, their increasing complexity, elevates level of interconnection. Therefore, safety and reliability analyses have to continuously evolve and adapt to the extending complexity. Growing expansion brings in the field of unnamed aerial vehicles systems which consist of items without relevant reliability testing. Presented algorithm utilizes graph theory and fuzzy logic in order to develop integrated computerized mean for reliability analysis of sophisticated, highly interconnected airborne systems. Through the usage of graph theory, it is possible to create model of particular systems and its sub-systems in the form of universal data structure. Algorithm is conceived as fuzzy expert system, that emulates decision making of a human expert. That brings opportunity to partially quantify system attributes and criticality. Criticality evaluation increases level of assessment correlation with real state of system and its attributes.
|
|
|
The Integrated Method Utilizing Graph Theory and Fuzzy Logic for Safety and Reliability Assessment
Janhuba, Luboš ; Vališ, David (referee) ; Třetina, Karel (referee) ; Hlinka, Jiří (advisor)
Dizertační práce se zabývá návrhem integrované metody hodnocení bezpečnosti a spolehlivosti palubních leteckých systém za použití teorie grafů a fuzzy logiky. Navržená integrovaná metoda je univerzálně použitelná v oblasti hodnocení bezpečnosti a spolehlivosti, nicméně je primárně navržená pro použití v oblasti General Aviation a civilních bezpilotních prostředků. Současná podoba hodnocení spolehlivosti je téměř výhradně závislá na úsudku analytika. Použití komerčních softwarových nástrojů pro hodnocení spolehlivosti je extrémně nákladné, přičemž možnost přístupu a úpravy použitých algoritmů je minimální. Současný prudký vývoj palubních letecký systému je spojen s jejich zvyšující se komplexností a sofistikovaností. Integrovaná metoda používá teorii grafů, jako nástroj modelování funkčních závislostí mez jednotily prvky systému. Použití teorie grafu současně umožňuje daný systém analyzovat, hodnotit hustotu vzájemné funkční vazebnosti, identifikovat důsledky případných poruchových stavů. Aplikace fuzzy logiky umožňuje manipulovat s expertní znalostí a stanovit kritičnost daného prvku a systému. Kritičnost prvku zohledňuje pravděpodobnost jeho selhání, možnost detekce dané poruchy, závažnost těchto selhání vzhledem k vlivu na alokované funkce.
|
guest ::
