El principal objectiu d'aquesta tesi és el de contribuir a l'estudi de l'existència i classificació dels grafs i digrafs que puguin admetre el màxim nombre de vèrtexs sota determinades condicions donats el grau i el diàmetre. Aquest estudi consta de tres parts ben diferenciades, una sobre digrafs i dos sobre grafs. En el treball relacionat amb els digrafs demostrem que els digrafs quasi de Moore de diàmetre k = 3 i qualsevol grau no existeixen. Així mateix provem la no existència dels digrafs quasi de Moore de diàmetre 4 i qualsevol grau assumint la irreductibilitat en Q[x] de certs polinomis. En quan als grafs ens hem centrat en l'existència dels de grau d, diàmetre 2 i defecte 2, anomenats (d,2,2)-grafs i assumint la irreductibilitat en Q[x] de certs polinomis provem que no existeixen per a cap grau. A més provem que no existeixen per a graus entre 4 i 50. Finalment estudiem els grafs radials de Moore de grau d i radi k. Proposem diferents mesures per classificar-los d'acord a la proximitat de les seves propietats a les d'un graf de Moore i ordenem segons aquestes mesures tots els grafs radials de Moore en els casos (d,k) = {(3,2), (3,3), (4,2)}. / El principal objetivo de esta tesis es el de contribuir al estudio de la existencia y clasificación de los grafos y digrafos que puedan admitir el máximo número de vértices bajo determinadas condiciones dados el grado y el diámetro. Este estudio consta de tres partes bien diferenciadas, una sobre digrafos y dos sobre grafos. En el trabajo relacionado con los digrafos demostramos que los digrafos casi de Moore de diámetro k = 3 y cualquier grado no existen. Asimismo probamos la no existencia de los digrafos casi de Moore de diámetro 4 y cualquier grado suponiendo la irreducibilidad en Q[x] de ciertos polinomios. En cuanto a los grafos nos hemos centrado en la existencia de los de grado d, diámetro 2 y defecto 2, llamados (d,2,2)-grafos y suponiendo la irreducibilidad en Q[x] de ciertos polinomios probamos que no existen para ningún grado. Además probamos que no existen para grados entre 4 y 50. Finalmente estudiamos los grafos radiales de Moore de grado d y radio k. Proponemos diferentes medidas para clasificarlos de acuerdo a la proximidad de sus propiedades a las de un grafo de Moore y ordenamos según estas medidas todos los grafos radiales de Moore en los casos (d, k) = {(3,2), (3,3), (4,2)}. / The main goal of this thesis is to contribute to the study of the existence and classification of graphs and digraphs that can achieve the maximum number of vertices under certain conditions given the degree and the diameter. This study consists of three differenciated parts, one on digraphs and two on graphs. The work on digraphs focuses on almost Moore digraphs. We prove that they do not exist for diameter 3 and any degree. Besides, we prove the non-existence of almost Moore digraphs of diameter 4 assuming the irreducibility in Q[x] of certain polynomials. Concerning graphs, we discuss the existence of graphs of degree d, diameter 2 and defect 2. Assuming the irreducibility in Q[x] of certain polynomials we prove their non existence. We also show they do not exist for degrees between 4 and 50. Finally we study radial Moore graphs of degree d and radius k. We propose different measures for classifying them in terms of their proximity to extremal properties of a Moore graph. By means of our measures, we are able to enumerate all radial Moore graphs for the cases (d, k) = {(3.2), (3.3), (4.2)}.

Every knapsack problem may be relaxed to a cyclic group problem. In 1969, Gomory found the subadditive characterization of facets of the master cyclic group problem. We simplify the subadditive relations by the substitution of complementarities and discover a minimal representation of the subadditive polytope for the master cyclic group problem. By using the minimal representation, we characterize the vertices of cardinality length 3 and implement the shooting experiment from the natural interior point. The shooting from the natural interior point is a shooting from the inside of the plus level set of the subadditive polytope. It induces the shooting for the knapsack problem. From the shooting experiment for the knapsack problem we conclude that the most hit facet is the knapsack mixed integer cut which is the 2-fold lifting of a mixed integer cut. We develop a cutting plane algorithm augmenting cutting planes generated by shooting, and implement it on Wong-Coppersmith digraphs observing that only small number of cutting planes are enough to produce the optimal solution. We discuss a relaxation of shooting as a clue to quick shooting. A max flow model on covering space is shown to be equivalent to the dual of shooting linear programming problem.

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2. / Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem. At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed. Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.

We define a variation of injective oriented colouring as reflexive injective oriented colouring, or rio-colouring for short, which requires an oriented colouring to be injective on the neighbourhoods of the underlying graph, without requiring the colouring to be proper. An analysis of the complexity of the problem of deciding whether an oriented graph has a k-rio-colouring is considered, and we find a dichotomy for the values of k below 3 and above, being in P or NP-complete, respectively. Characterizations are given for the oriented graphs resulting from the polynomial-time solvable cases, and bounds are given for the rio-chromatic number in terms of maximum in-degree and out-degree, in general, and for oriented trees. Also, a polynomial-time algorithm is developed to aid in the rio-colouring of oriented trees.

Made available in DSpace on 2014-07-29T12:05:38Z (GMT). No. of bitstreams: 1 Tese_Maria_Socorro.pdf: 6409428 bytes, checksum: a9c7fda760fff59683cd1cc07cf49788 (MD5) Previous issue date: 2009-03-22 / Item withdrawn by Carla Ferreira (carlaferreira66@gmail.com) on 2014-07-29T13:37:22Z Item was in collections: Doutorado em Ciências Ambientais (PRPG) (ID: 53) No. of bitstreams: 1 Tese_Maria_Socorro.pdf: 6409428 bytes, checksum: a9c7fda760fff59683cd1cc07cf49788 (MD5) / Item reinstated by Carla Ferreira (carlaferreira66@gmail.com) on 2014-07-29T13:40:12Z Item was in collections: Doutorado em Ciências Ambientais (PRPG) (ID: 53) No. of bitstreams: 1 Tese_Maria_Socorro.pdf: 6409428 bytes, checksum: a9c7fda760fff59683cd1cc07cf49788 (MD5) / The efforts to minimize the growing loss of habitats and threatens to biodiversity are increasingly based on objective criteria, which allow prioritize areas and species in need of preservation, taking into account the limitations in both natural and economic resources. These criteria are fundamental for the reserve selection and design, mainly at regions severely affected by land use intensification. In particular, the use of mathematical modeling, enabling the identification of more efficient alternatives, is an important subsidy to conservation challenge. Specifically, in this dissertation we present a new approach for the selection of priority areas for conservation, which considers both the quality and ecological feasibility of the remnant vegetation in the Cerrado areas of the State of Goiás, as well as the practical and legal aspects regarding the use of watersheds for territorial management. This proposal, based on a non-linear mathematical model, allows the parameters to vary according to the socialeconomical and environmental interests, thus generating distinct solutions and scenarios. Among the possible outcomes, we highlight as an "optimum" solution, the one with a large number remnant vegetation areas within riparian environments, which serves the purpose of strengthening spatial connectivity and natural corridors. In fact, this model can be used either to promote the conservation of large remnant vegetation patches, as well as to optimize the restoration of degraded areas, mainly in riparian environments, through the generation of alternative spatial patterns aiming at a more efficient connectivity in highly converted areas / Os esforços para amenizar a crescente perda da biodiversidade e de habitats estão sendo baseados, cada vez mais, na adoção de critérios objetivos, os quais permitem priorizar áreas e/ou espécies a serem preservadas, levando em consideração a limitação de recursos naturais e econômicos. Estes critérios são fundamentais para a seleção de reservas, principalmente para as regiões onde ocorre maior intensificação do uso do solo. Em particular, o uso de modelagem matemática, ao possibilitar a identificação de alternativas mais eficazes, constituise em importante subsídio aos problemas de conservação. Especificamente, nesta tese, apresentamos um modelo matemático não-linear de seleção de áreas prioritárias para conservação, que considerou tanto a qualidade e viabilidade ecológica das áreas de vegetação remanescente do Cerrado goiano a partir do uso de dados e critérios ambientais por meio da paisagem, quanto à praticidade e a legalidade do uso de bacias hidrográficas para gestão. Este modelo permite variar parâmetros de acordo com os interesses sócio-econômicos e ambientais, gerando distintas soluções e cenários. Entre estas soluções, destacamos uma solução ótima que prioriza as áreas de vegetação remanescente com elevada porcentagem de ambientes ripários, valorizando a vizinhança e a conectividade entre elas, formando corredores naturais ou viabilizando sua formação. O modelo proposto pode contribuir tanto para valorização das áreas de vegetação remanescente em propostas de conservação, quanto otimizar a restauração de áreas degradadas, principalmente de ambientes ripários, que favorecem a sua interligação

Neste trabalho consideramos um problema da Antropologia. A modelagem de sociedades e casamentos de indivíduos é feita com grafos mistos e encontrar caminhos disjuntos é uma questão central no problema. O problema é NP-completo e, quando visto como um problema parametrizado, ele é W[1]-difícil. Alguns subproblemas que surgem durante o processo de obter uma solução para o problema, envolvem caminhos disjuntos e podem ser resolvidos em tempo polinomial. Implementamos algoritmos polinomiais que são usados em uma ferramenta desenvolvida para solucionar o problema na Antropologia considerado. Nossa solução funcionou bem para as sociedades fornecidas pelos nossos parceiros. / In this work we consider a problem from the Anthropology. The model of the societies and the marriages of individuals is done with mixed graphs and to find disjoint paths is a central question in the problem. The problem is NP-complete and W[1]-hard when it is considered a parameterized problem. Some subproblems that arise during the process to obtain a solution for the problem, involve disjoint paths and can be solved in polynomial time. We implemented some polynomial algorithms that are used in a tool developed to solve the problem in the Anthropology considered. Our solution worked well for the societies provided by our partners.

Modelagem e controle de execução são duas abordagens do gerenciamento de processos de negócio que, embora complementares, têm se desenvolvido independentemente. Por um lado, a modelagem é normalmente conduzida por especialistas de negócio e explora aspectos semânticos do processo. Por outro lado, o controle de execução estuda mecanismos consistentes e eficientes de implementação. Este trabalho apresenta um método algorítmico que relaciona modelagem e controle de execução, por meio da geração de expressões algébricas a partir de digrafos acíclicos. Por hipótese, assumimos que modelos de processos de negócio são formados por estruturas baseadas em grafos, e mecanismos de controle de execução são baseados na interpretação de expressões de álgebra de processos. Para a geração de expressões algébricas, esta tese apresenta as propriedades topológicas de digrafos série-paralelo e define um sistema de transformação baseado em redução de digrafos. Além disso, um algoritmo de identificação de digrafos série-paralelo e geração de expressões algébricas é apresentado. O texto também discute o tratamento de digrafos que não são série-paralelo e apresenta, para alguns desses casos, soluções baseadas em mudanças topológicas. Finalmente, o algoritmo é ilustrado com o estudo de caso de uma aplicação real. / Modeling and execution control are complementary approaches of business process management that have been developed independently. On one hand, modeling is usually performed by business specialists and explores semantical aspects of the business process. On other hand, execution control studies consistent and efficient mechanisms for implementation. This work presents an algorithmic method which joins modeling and execution control through algebraic expression generation from acyclic digraphs. By hypothesis, we assume that business process models are defined by graph structures, and execution control mechanisms are based on interpretation of process algebra expressions. For algebraic expression generation, this thesis presents the topological properties of series-parallel digraphs and defines a transformation system based on digraph reduction. Therefore, we present an algorithm for identification of series-parallel digraphs and generation of algebraic expressions. This work also discusses the treatment of non-series-parallel digraphs and presents solutions based on topological changing for some cases. Finally, the algorithm is illustrated with a case study based on a real system.

No description available.

The orthography of Östergötland’s 11th century runic inscriptions varies widely, in part due to the lack of spelling norms at the time. This thesis seeks to identify other causes for the observed variation, based on the frequency and distribution of aspects of inscription orthography. The Old Norse words ræisa and stæin in the phrase “raised the stone” were analyzed based on the main vowel and its status as a monograph or digraph. The presence or absence of þ in inflected ræisa was also included as an indicator of age. All runic inscriptions in Östergötland with definite key word orthography were included, 169 in total. The analysis reveals that most inscriptions are clustered in three regions, each with a dominant vowel. By region, these are ei (west), i (central) and ai (east), with vowel consistency between ræisa and stæin the norm. The consonant þ in inflected ræisa is most common in the west and east. The vowel orthography together with the distribution of þ implies a relative chronology for Östergötland’s runic inscriptions, where the ongoing monophthongization is reflected in digraphs and monographs. The detailed orthography distribution of these variables shows that the main clusters align with the known 11th century quarries at Borghamn (west) and Vreta (central). Stoneworking at a shared site resulted in a transfer of knowledge, including runestone design and orthography which became a local norm as it spread. The lack of a unifying quarry in eastern Östergötland resulted in a more diverse local orthography, and possibly hampered the building of the first stone churches during the early 12th century. / Östergötlands runinskrifter från 1000-talet varierar stort i sin ortografi, delvis på grund av bristen på stavningsnormer när de ristades. Uppsatsen eftersträvar att identifiera andra orsaker för denna variation, baserat på frekvensen och distributionen av vissa aspekter i inskrifternas ortografi. De fornnordiska orden ræisa och stæin i inskriftsfrasen “reste sten” analyserades baserat på huvudvokalen samt om den var en monograf eller digraf. Användning av þ i böjda former av ræisa inkluderades som ett tecken på inskriftens ålder. Samtliga runinskrifter i Östergötland med en säker nyckelordsortografi analyserades, totalt 169 stycken. Resultaten visar att de flesta inskrifterna är grupperade i tre regioner som har varsin dominant vokal. Vanligast i väster är ei, i den centrala regionen råder i och i öster råder ai, med normen att samma vokal används i både ræisa och stæin. Konsonanten þ i böjd ræisa är vanligast i väster och i öster. Vokalortografin tillsammans med þ-distributionen indikerar en relativ kronologi för Östergötlands runinskrifter, där vokalernas monoftongering under 1000-talet återspeglas i digrafer och monografer. De analyserade variablernas distribution visar att huvudgrupperingarna sammanfaller med de kända stenbrotten från 1000-talet vid Borghamn (i väster) och Vreta (centrala regionen). Att stenarbetet skedde vid en gemensam site ledde till en omedveten kunskapsöverlämning mellan ristare. Inskriftsortografi kopierades och blev lokala normer allt efter att den spreds. Bristen på ett större stenbrott som informell, gemensam arbetsplats i östra Östergötland ledde till en mer varierad lokalortografi. Detta kan ha hindrat stenkyrkobygget lokalt under tidigt 1100-tal.

Many problems in applied mathematics and physics are formulated most naturally in terms of matrices, and can be solved by computing functions of these matrices. For example, in quantum mechanics, the coherent dynamics of physical systems is described by the matrix exponential of their Hamiltonian. In state of the art experiments, one can now observe such unitary evolution of many-body systems, which is of fundamental interest in the study of many-body quantum phenomena. On the other hand the theoretical simulation of such non-equilibrium many-body dynamics is very challenging. In this thesis, we develop a symbolic approach to matrix functions and quantum dynamics based on a novel algebraic structure we identify for sets of walks on graphs. We begin by establishing the graph theoretic equivalent to the fundamental theorem of arithmetic: all the walks on any finite digraph uniquely factorise into products of prime elements. These are the simple paths and simple cycles, walks forbidden from visiting any vertex more than once. We give an algorithm that efficiently factorises individual walks and obtain a recursive formula to factorise sets of walks. This yields a universal continued fraction representation for the formal series of all walks on digraphs. It only involves simple paths and simple cycles and is thus called a path-sum. In the second part, we recast matrix functions into path-sums. We present explicit results for a matrix raised to a complex power, the matrix exponential, matrix inverse, and matrix logarithm. We introduce generalised matrix powers which extend desirable properties of the Drazin inverse to all powers of a matrix. In the third part, we derive an intermediary form of path-sum, called walk-sum, relying solely on physical considerations. Walk-sum describes the dynamics of a quantum system as resulting from the coherent superposition of its histories, a discrete analogue to the Feynman path-integrals. Using walk-sum we simulate the dynamics of quantum random walks and of Rydberg-excited Mott insulators. Using path-sum, we demonstrate many-body Anderson localisation in an interacting disordered spin system. We give two observable signatures of this phenomenon: localisation of the system magnetisation and of the linear magnetic response function. Lastly we return to the study of sets of walks. We show that one can construct as many representations of series of walks as there are ways to define a walk product such that the factorisation of a walk always exist and is unique. Illustrating this result we briefly present three further methods to evaluate functions of matrices. Regardless of the method used, we show that graphs are uniquely characterised, up to an isomorphism, by the prime walks they sustain.