An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. The smallest number of colours needed to colour a graph G with a star edge colouring is called the star chromatic index of G and is denoted <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(G)" />. This paper proves an upper bound of the star chromatic index of bipartite graphs in terms of the maximum degree; the maximum degree of G is the largest number of edges incident to a single vertex in G. For bipartite graphs Bk with maximum degree <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?k%5Cgeq1" />, the star chromatic index is proven to satisfy<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%20%5Cchi'_%7Bst%7D(B_k)%20%5Cleq%20k%5E2%20-%20k%20+%201" />. For bipartite graphs <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?B_%7Bk,n%7D" />, where all vertices in one part have degree n, and all vertices in the other part have degree k, it is proven that the star chromatic index satisfies <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(Bk,n)%20%5Cleq%20k%5E2%20-2k%20+%20n%20+%201,%20k%20%5Cgeq%20n%20%3E%201" />. We also prove an upper bound for a special case of multipartite graphs, namely <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?K_%7Bn,1,1,%5Cdots,1%7D" /> with m parts of size one. The star chromatic index of such a graph satisfies<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(K_%7Bn,1,1,%5Cdots,1%7D)%20%5Cleq%2015%5Clceil%5Cfrac%7Bn%7D%7B8%7D%5Crceil%5Ccdot%5Clceil%5Cfrac%7Bm%7D%7B8%7D%5Crceil%20+%20%5Cfrac%7B1%7D%7B2%7Dm(m-1),%5C,m%20%5Cgeq%205" />. For complete multipartite graphs where m &lt; 5, we prove lower upper bounds than the one above.

The increasing demand for mineral-based resources that face supply risks calls for managing the supply chains for these resources at the regional level. Cobalt is a widely used cathode material in lithium-ion batteries, which form the major portion of batteries used for renewable energy storage - a necessary technology for electrifying mobility and overcoming the challenge of intermittency, thus making renewable energy more reliable and energy generation more sustainable. This necessitates understanding cobalt's supply risks and for the Untied States, identifying sources of cobalt available for future use via recycling or mining. These needs are addressed in this work using single and multiregional input-output (MRIO) analysis in combination with graph theory. An MRIO-based approach is developed to obtain the trade network of cobalt and offer a more expedient way to identify potential critical material sources embodied in commodities made domestically. Commodities containing cobalt were disaggregated from two input-output (IO) models and the trade structure of cobalt at the national and state level was observed and compared. The significance of identified key sectors is measured according to several criteria and differences in sectors highlighted in the national versus subnational networks suggests that analysis at the two regional aggregation levels provides alternative insights. Results from mining the IO networks for cobalt highlight the geographical distribution of its use and industries to further investigate as potential sources for secondary feedstock.

Magisterská práce se zabývá stochastickou optimalizací síťových úloh. Teoretická část pokrývá tři témata - teorii grafů, optimalizaci a progressive hedging algoritmus. V rámci optimalizace je hlavní část věnována stochastickému programování a dvoustupňovému programování. Progressing hedging algoritmus zahrnuje také metodu přiřazování scénářů a modifikaci obecného algoritmu na dvou stupňové úlohy. Praktická část je věnována modelům na reálných datech z oblasti svozu odpadu v rámci České republiky. Data poskytl Ústav procesního inženýrství.

This master’s thesis deals with the distributed computing and mathematical tools for modelling the distributed systems. Firstly, my attention is focused on a description of the distributed algorithms, characteristic failures for the distributed systems, and mathematical tools for an analysis of the distributed systems.The experimental part is concerned with the impact of stochastic link failures on the chosen parameters of the protocol Push-sum, namely the deviation of the final states from the average value, the convergence rate of the protocol, the distribution of the final states, and the distribution of the convergence rates. My intention is demonstrated using Matlab on a tree, a ring, a line, a star, and a fully-connected mesh topology. Was analyzed two functionalities of the protocol Push-sum, namely an estimation of the average value and an estimation of sum.

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.

The brain; complex system people want to know about but still they are at the beginning of understanding it. There has been a lot of neuroimaging systems since developement of modern technologies and magnetic resonance imaging is one of them. In last days it isn't enough to examine only structural character of brain, the scientists are dealing with functional states more and more; the functional magnetic resonance imaging is perfectly good tool for this. There is a big amount of researches concerning individual brain regions but also a lot of them dealing with communication across the brain to clear up the causes of human behavior and functional failures. This thesis introduces the brain connectivity exploration, it uses the parcellation by anatomical atlases and it tries to use the knowledge of graph theory as one of the options to determine relations between brain centres and regions. The thesis introduces the software created for extraction of connectivity matrix resulting in graph processing and visualization.

Tato disertační práce se zaměřuje na problematiku investování a podporu rozhodování pomocí moderních metod. Zejména pokud jde o analýzu, hodnocení a výběr tzv. brownfieldů pro jejich redevelopment (revitalizaci). Cílem této práce je navrhnout univerzální metodu, která usnadní rozhodovací proces. Proces rozhodování je v praxi komplikován též velkým počet relevantních parametrů ovlivňujících konečné rozhodnutí. Navržená metoda je založena na využití fuzzy logiky, modelování, statistické analýzy, shlukové analýzy, teorie grafů a na sofistikovaných metodách sběru a zpracování informací. Nová metoda umožňuje zefektivnit proces analýzy a porovnávání alternativních investic a přesněji zpracovat velký objem informací. Ve výsledku tak bude zmenšen počet prvků množiny nejvhodnějších alternativních investic na základě hierarchie parametrů stanovených investorem.

The thesis introduces the basic concepts of graph theory and graph representation both in mathematics and programming. Furthermore, it presents basic methods and problems of graphs searching and theory in general. There are presented graph data management capabilities of different database systems including those directly based on the graph theory. In the practical part, there is designed an efficient method of graphs traversing in PostgreSQL database. The method was tested and demonstrated by the graph search algorithms, coloring and isomorphism.

This master's thesis deals with mathematical model building for routing problems and ways to solve them. There are discussed and implemented deterministic and heuristic approaches that are suitable to be utilized. A big effort is put into building of the mathematical model describing a real world problem from the field of waste management. Appropriate algorithms are developed and modified to solve a particular problem effectively. An original graphical environment is created to illustrate acquired results and perform testing computations.

Depuis 2004, les médias sociaux en ligne ont connu une croissance considérable. Ce développement rapide a eu des effets intéressants pour augmenter la connexionet l'échange d'informations entre les utilisateurs, mais certains effets négatifs sont également apparus, dont le nombre de faux comptes grandissant jour après jour.Les sockpuppets sont les multiples faux comptes créés par un même utilisateur. Ils sont à l'origine de plusieurs types de manipulations comme la création de faux comptes pour louer, défendre ou soutenir une personne ou une organisation, ou pour manipuler l'opinion publique. Dans cette thèse, nous présentons SocksCatch, un processus complet de détection et de groupage des sockpuppets composé de trois phases principales : la première phase a pour objectif la préparation du processus et le pré-traitement des données; la seconde phase a pour objectif la détection des comptes sockpuppets à l'aide d'algorithmes d'apprentissage automatique; la troisième phase a pour objectif le regroupement des comptes sockpuppets créés par un même utilisateur à l'aide d'algorithmes de détection de communautés. Ces phases sont déclinées en trois étapes : une étape "modèle" pour représenter les médias sociaux en ligne, où nous proposons un modèle général de médias sociaux dédié à la détection et au regroupement des sockpuppets ; une étape d'adaptation pour ajuster le processus à un média social spécifique, où nous instancions et évaluons le modèle SocksCatch sur un média social sélectionné ; et une étape en temps réel pour détecter et grouper les sockpuppets en ligne, où SocksCatch est déployé en ligne sur un média social sélectionné. Des expérimentations ont été réalisées sur l'étape d'adaptation en utilisant des données réelles extraites de Wikipédia anglais. Afin de trouver le meilleur algorithme d'apprentissage automatique pour la phase de détection de sockpuppet, les résultats de six algorithmes d'apprentissage automatique sont comparés. En outre, ils sont comparés à la littérature où les résultats de la comparaison montrent que notre proposition améliore la précision de la détection des sockpuppets. De plus, les résultats de cinq algorithmes de détection de communauté sont comparés pour la phase de regroupement de Sockpuppet, afin de trouver le meilleur algorithme de détection de communauté qui sera utilisé en temps réel. / Since 2004, online social medias have grown hugely. This fast development had interesting effects to increase the connection and information exchange between users, but some negative effects also appeared, including fake accounts number growing day after day. Sockpuppets are multiple fake accounts created by a same user. They are the source of several types of manipulation such as those created to praise, defend or support a person or an organization, or to manipulate public opinion. In this thesis, we present SocksCatch, a complete process to detect and group sockpuppets, which is composed of three main phases: the first phase objective is the process preparation and data pre-processing; the second phase objective is the detection of the sockpuppet accounts using machine learning algorithms; the third phase objective is the grouping of sockpuppet accounts created by a same user using community detection algorithms. These phases are declined in three stages: a model stage to represent online social medias, where we propose a general model of social media dedicated to the detection and grouping of sockpuppets; an adaptation stage to adjust the process to a particular social media, where we instantiate and evaluate the SocksCatch model on a selected social media; and a real-time stage to detect and group the sockpuppets online, where SocksCatch is deployed online on a selected social media. Experiments have been performed on the adaptation stage using real data crawled from English Wikipedia. In order to find the best machine learning algorithm for sockpuppet's detection phase, the results of six machine learning algorithms are compared. In addition, they are compared with the literature, and the results show that our proposition improves the accuracy of the detection of sockpuppets. Furthermore, the results of five community detection algorithms are compared for sockpuppet's grouping phase, in order to find the best community detecton algorithm that will be used in real-time stage.