Cette thèse porte sur différents problèmes d'optimisation combinatoire dont nous avons caractérisé la difficulté en décrivant des réductions et des algorithmes polynomiaux exacts ou approchés.En particulier, nous étudions le problème de trouver, dans un graphe orienté sans cycle dont les sommets sont étiquetés, un chemin qui passe par un maximum d'étiquettes différentes. Nous établissons qu'il n'existe pas d'algorithme polynomial avec un facteur constant pour ce problème. Nous présentons aussi un schéma qui permet d'obtenir, pour tout $epsilon >0$, un algorithme polynomial qui calcule un chemin collectant $ O(OPT^{1-epsilon})$ étiquettes.Nous étudions ensuite des variantes du problème de l'arbre couvrant de poids minimum auquel nous ajoutons des contraintes de distance et d'intermédiarité. Nous prouvons que certaines variantes se résolvent en temps polynomial comme des problèmes de calcul d'un libre de poids minimum commun à deux matroïdes. Pour une autre variante, nous présentons un algorithme d'approximation facteur 2 et nous prouvons qu'il n'existe pas d'algorithme polynomial avec un meilleur facteur constant.Enfin, nous étudions un problème d'améliorations de réseaux du point de vue du partage des coûts. Nous montrons que la fonction de coût associée à ce problème est sous-modulaire et nous utilisons ce résultat pour déduire un mécanisme de partage des coûts qui possède plusieurs bonnes propriétés. / In this thesis, we investigate several combinatorial optimization problems and characterize their computational complexity and approximability by providing polynomial reductions and exact or approximation algorithms.In particular, we study the problem of finding, in a vertex-labeled directed acyclic graph, a path collecting a maximum number of distinct labels. We prove that no polynomial time constant factor approximation algorithm exists for this problem. Furthermore, we describe a scheme that produces, for any $epsilon >0$, a polynomial time algorithm that computes a solution collecting $O(OPT^{1-epsilon})$ labels. Then, we study several variants of the minimum cost spanning tree problem that take into account distance and betweenness constraints. We prove that most of these problems can be solved in polynomial time using a reduction to the weighted matroid intersection problem. For an other problem, we give a factor 2 approximation algorithm and prove the optimality of this ratio.Finally, we study a network improvement problem from a cost sharing perspective. We establish that the cost function corresponding to this problem is submodular and use this result to derive a cost sharing mechanism having several good properties.

De nos jours on utilise de plus en plus les aciers pré-revêtus dédiés aux applications pour emboutissage à chaud afin de protéger la surface de l’acier contre la décarburation et l’oxydation durant le traitement thermique. Le revêtement est déposé à chaud en continu par immersion de la bande d’acier dans un bain d’Al-Si. Pendant l’austénitisation le revêtement Al-Si se transforme par réactions d’inter-diffusion et de solidification. Ces réactions conditionnent la microstructure finale et en particulier la surface du revêtement, responsable des propriétés d’emploi telles que le soudage par point et l’adhérence peinture.A l’état de livraison le revêtement Al-Si contient les phases suivantes : des grains d’Al, l’eutectique ternaire Al-Fe-Si, une couche intermétallique ternaire Al-Fe-Si et une couche intermétallique binaire Al-Fe. Après austénitisation les phases se transforment en deux types d’intermétalliques : intermétalliques ternaires riches en Si et intermétalliques binaires pauvre en Si.Durant cette étude une identification complète des différentes phases a été établie. Les phases initialement riches en Si se transforment en phases fusibles par réactions eutectique ou péritectique. La présence de phase liquide accélère la diffusion locale de fer permettant aux phases riches en Si de garder leur contenu en Si pendant tout le traitement thermique. C’est la diffusion du fer qui stabilise les gradients en Si dans le revêtement, malgré les lois de diffusion classiques. En utilisant le diagramme de phases ternaire il a été démontré comment l’enrichissement en fer s’établit dans le revêtement tout en gardant l’équilibre aux interfaces entre les phases riches et pauvres en Si / Nowadays more and more pre-coated steels are applied in hot-stamping process to prevent the steel surface against iron oxidation and decarburization during the heat-treatment. The coating is deposited by hot-dipping the coil in an Al-Si bath. During the austenitization, the Al-Si coating transforms completely by inter-diffusion and solidification reactions, which define the final microstructure and particularly the top layer responsible for the in-use properties like spot welding and painting adhesion.At the delivery state, the Al-Si coating is a multiphase coating containing the following phases: Al-grains, Al-Fe-Si ternary eutectic phase, an Al-Fe-Si intermetallic layer and a binary Al-Fe interfacial layer. After the heat-treatment, all the phases transform into two types of intermetallic compounds: Si-rich ternary and Si-poor binary compounds.During this study, a complete identification of the different intermetallic phases has been conducted. Initial ternary Al-Fe-Si phases transform into fusible phases by eutectic or peritectic reaction. The presence of liquid state enables rapid local iron diffusion which allows to the Si-rich phases to keep their high Si content during the whole treatment. So the iron diffusion stabilizes the Si gradients in the coating despite the classical diffusion laws. Using the ternary phase diagram it was shown how iron enrichment in the coating proceeds by keeping thermodynamical equilibrium along the interfaces between Si-rich ternary and Si-poor binary phases. A phenomenological model of phase transformations explaining the formation of differente coating microstructures during the austenitization step is proposed

The aim of this thesis is to evaluate beer tourism potential of Jihočeský kraj. The first part of this thesis deals with the characteristics of gastronomy and beer tourism. The first chapter also presents successful foreign projects of gastronomy tourism. The second chapter presents tourism infrastructure and beer industry in Jihočeský kraj. In this chapter there are described and evaluated breweries in the region. The third chapter identifies possible reasons for Jihočeské pivní stezky project failure. Last chapter suggests beer cycle trails and beer packages on the ground of previous chapters.

abstract: C*-algebras of categories of paths were introduced by Spielberg in 2014 and generalize C*-algebras of higher rank graphs. An approximately finite dimensional (AF) C*-algebra is one which is isomorphic to an inductive limit of finite dimensional C*-algebras. In 2012, D.G. Evans and A. Sims proposed an analogue of a cycle for higher rank graphs and show that the lack of such an object is necessary for the associated C*-algebra to be AF. Here, I give a class of examples of categories of paths whose associated C*-algebras are Morita equivalent to a large number of periodic continued fraction AF algebras, first described by Effros and Shen in 1980. I then provide two examples which show that the analogue of cycles proposed by Evans and Sims is neither a necessary nor a sufficient condition for the C*-algebra of a category of paths to be AF. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2020

La presente tesis tiene como objetivo determinar si la implementación de ciclovías en el Distrito de San Juan de Lurigancho, durante los años 2020 y 2021, tiene relación con lo establecido en los objetivos de desarrollo sostenible “salud y bienestar” y “ciudades y comunidades sostenibles”. Al respecto, la Municipalidad Metropolitana de Lima es la encargada de implementar las ciclovías en la ciudad. El diseño de la investigación es no experimental, de tipo descriptiva y correlacional, con un enfoque cualitativo, para ello se realizó una entrevista semiestructurada, además de la aplicación de una encuesta virtual a través de Google Forms. Las respuestas se procesaron en el programa estadístico SPSS. Asimismo, se realizó un análisis legal de la diversa normativa aplicable al uso de la bicicleta en el Perú. Los resultados arrojados demuestran que la población objetivo identifica una relación directa débil a media entre la implementación de ciclovías en el distrito de San Juan de Lurigancho durante los años 2020 y 2021 y el desarrollo sostenible, enmarcado en los objetivos de desarrollo sostenible de “salud y bienestar” y “ciudades y comunidades sostenibles”. Asimismo, en el análisis legal se determina, entre otros hallazgos, que en los últimos años se consideró una regulación más específica y práctica del uso de la bicicleta como medio alternativo de transporte sostenible, como componente de un sistema de movilidad urbano basado en un enfoque más extenso que la sostenibilidad. / The objective of this thesis is to determine if the bikeway implementation in San Juan de Lurigancho, during the years 2020 and 2021, is related to the Sustainable Development Goals "health and well-being” and “sustainable cities and communities". In this regard, the Metropolitan Municipality of Lima is responsible of bikeway implementation along the city. The research design is non-experimental, descriptive and correlational, with a qualitative approach, for which a semi-structured interview was carried out, in addition to the application of a virtual survey through Google Forms. The responses were processed in the SPSS statistical program. Likewise, the legal analysis determines, among other findings, that in recent years a more specific and practical regulation of the use of bicycles as an alternative means of sustainable transport was considered, as a component of an urban mobility system based on a broader approach than sustainability. / Trabajo de investigación

Increasing demand for freshwater and energy is pushing towards the development of alternative technologies that are sustainable. One of the realistic solutions to address this is utilization of the renewable resources like wastewater. Conventional wastewater treatment processes can be highly energy demanding and can fails to recover the full potential of useful resources such as energy in the wastewater. As a consequence, there is an urgent necessity for sustainable wastewater treatment technologies that could harness such resources present in wastewaters. Advanced treatment process based on microbial electrochemical technologies (METs) such as microbial fuel cells (MFCs) and microbial electrolysis cells (MECs) have a great potential for the resources recovery through a sustainable wastewater treatment process. METs rely on the abilities of microorganisms that are capable of transferring electrons extracellularly by oxidizing the organic matter in the wastewater and producing electrical current for electricity generation (MFC) or H2 and CH4 production (MEC). Propionate is an important volatile fatty acid (VFA) (24-70%) in some wastewaters and accumulation of this VFA can cause a process failure in a conventional anaerobic digestion (AD) system. To address this issue, MECs were explored as a novel, alternative wastewater treatment technology, with a focus on a better understanding of propionate oxidation in the anode of MECs. Having such knowledge could help in the development of more robust and efficient wastewater treatment systems to recover energy and produce high quality effluents. Several studies were conducted to: 1) determine the paths of electron flow in the anode of propionate fed MECs low (4.5 mM) and high (36 mM) propionate concentrations; 2) examine the effect of different set anode potentials on the electrochemical performance, propionate degradation, electron fluxes, and microbial community structure in MECs fed propionate; and 3) examine the temporal dynamics of microbial communities in MECs fed with low or high concentration of acetate or propionate relating to the reactor performance. Overall, the findings from these studies provides new knowledge on propionate oxidation in MECs. The discovery of such findings may shed light on the development of an energy positive wastewater treatment process capable of producing a high quality effluent.

Master’s thesis proposes a new algorithm which enables efficient conversion of graphical representation of warehouse into graph theory representation and consequently accelerates estimation for route costs. The proposed algorithm computes route distances between any places in warehouse based on Breadth first search, image processing „skeletonization“ and Dijkstra algorithm. Using the proposed algorithm it is possible to search routes in a warehouse effectively and fast using precomputed routing table. Searching time is less then milisecond using routing table and even size of warehouse doesn’t affect it significantly instead of using Dijkstra algorithm.

This thesis examines the problem of counting and describing walks in graphs, and the problem when such walks have modular restrictions on how many timesit visits each vertex. For the special cases of the path graph, the cycle graph, the grid graph and the cylinder graph, generating functions and regular languages for their walks and walks with modular restrictions are constructed. At the end of the thesis, a theorem is proved that connects the generating function for walks in a graph to the generating function for walks in a covering graph.

https://dc.etsu.edu/digital-animation-videos-oer/1038/thumbnail.jpg

The study of matrices have been of interest to mathematicians for some time. Recently the use of matrices has assumed greater importance also in the fields of management, social science, and natural science because they are very useful in the organization and presentation of data and in the solution of linear equations. The theory of matrices is yet another type of mathematical model which we can use to solve many problems that arise in these fields. The aim of this paper is to show how we can use matrices and their mathematical model to solve some problems in the process of routing. First we will introduce the term of routing and the new approach in the process of selecting paths. We will show some simple examples. We will also pint out how we can learn about matrices in the classroom. At the end we will discuss about advantages and potential disadvantages that may occur in the described technique.