Dissertations / Theses on the topic 'Digrafia'

Orientador: Claudina Izepe Rodrigues
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-07-26T16:57:25Z (GMT). No. of bitstreams: 1 Carvalho_MarceloDantasde_M.pdf: 1298387 bytes, checksum: 14167c08257e5465066717df5f9963e6 (MD5) Previous issue date: 2000
Resumo: 0 objetivo principal deste trabalho é apresentar uma classificação para os dígrafos semicompletos hamiltonianos, extendendo os resultados obtidos para os torneios. Para isso utilizamos da teoria da homotopia regular de grafos de Davide C. Demaria, apresentando resultados sobre torneios simplemente desconexos, a caracterização de torneios por 3-ciclos e o conceito de ciclo conado e não-conado para dígrafos, introduzido por Kiihl e Tironi. Com a noção de ciclo minimal e característico para dígrafo uma classificação para os dígrafos semicompletos hamiltonianos surge então naturalmente. Esses resultados, quando encontrados para torneios, proporcionaram a obtenção de uma classe de torneios reconstrutíveis (torneios normais) e pesquisa nesse sentido deve ser efetuada para dígrafos. Apresentamos em apêndice a matriz de um dígrafo, os torneios de moon, normais e, brevemente, o problema da reconstrução de grafos
Abstract: The main target in this work is to present a classification for the hamiltonian semicomplete digraphs, extending the results previously obtained for the tournaments. In this way we apply the regular homotopy of finite directed graphs theory developed by Davide G. Demaria, presenting results on simply disconnected tournaments, on the caracterization of tournaments by 3-cicles and the concept of coned and non-coned cicle for digraphs, introduced by Kiihl and Tironi. With the notion of minimal and caracteristic cicle we naturally get a classification of the semicomplete hamiltonian digraphs. These results, when used for tournaments led to a new class of reconstructible ones (named normal) and future research on the extension of these results for digraphs in general seems to be interesting. We present in appendixes the array of a digraph, the tournaments of Moon, Normal and, briefly, the reconstruction problem for graphs
Mestrado
Mestre em Matemática

Orientador: Orlando Lee
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-23T03:38:43Z (GMT). No. of bitstreams: 1 Pereira_LuizFernandodeFaria_M.pdf: 862122 bytes, checksum: 06f038348723d2201293366e75808ffd (MD5) Previous issue date: 2013
Resumo: Uma partição em caminhos de um grafo dirigido é uma partição do conjunto de vértices deste grafo em caminhos dirigidos. Dada uma métrica sobre partições em caminhos chamada k-norma, o problema de interesse é estabelecer para um dado grafo quais das suas partições em caminhos tem a menor k-norma dentre todas as suas possíveis partições em caminhos. Chamamos estas partições de k-ótimas. Na década de 1980, Claude Berge conjecturou que para toda partição k-ótima, existe um conjunto de k conjuntos independentes disjuntos que, em certo sentido, interceptam o maior número possível de caminhos desta partição. A validade ou a falsidade desta proposição ainda não foi demonstrada, e ela é conhecida como a conjectura de Berge sobre partições em caminhos. Nesta dissertação, fizemos um estudo geral sobre a conjectura de Berge, sua história recente, e o trabalho matemático que foi desenvolvido sobre ela. Exibimos demonstrações para diversos casos particulares da conjectura que já foram resolvidos, como para grafos bipartidos, hamiltonianos, acíclicos, partições compostas somente de caminhos curtos, partições compostas somente de caminhos longos, e para valores fixos de k. Uma parte significativa do trabalho foi dedicada à reescrita da demonstração recente do caso particular onde k = 2, feita por Eli Berger e Irith Hartman, e uma análise do método usado
Abstract: A path partition of a directed graph is a partition of its vertex set into directed paths. Given a metric over path partitions called the k-norm, the problem we are interested in is to determine for a given graph which of its path partitions have the smallest k-norm among all possible path partitions. These partitions are called k-optimal. In the 1980's, Claude Berge conjectured that for every k-optimal path partition, there exists a set of k disjoint independent sets which intercepts the maximum number of paths in this partition. The validity of this proposition has not yet been demonstrated, and it is known as Berge's conjecture on path partitions. In this work, we consider Berge's conjecture, its recent history, and the related mathematical work that has been accomplished. We show proofs for many particular cases of the conjecture, including for acyclic graphs, bipartite graphs, hamiltonian graphs, partitions which include only short paths, partitions which include only long paths, and for fixed values of k. A significant part of this work was dedicated to the rewriting of a recent proof for the particular case where k = 2 by Eli Berger and Irith Hartman, and an analysis of their method
Mestrado
Ciência da Computação
Mestre em Ciência da Computação

La ricerca intende illustrare le modalità applicative attraverso le quali si possono esprimere in lingua cinese le terminologie specialistiche dei campi tecnici e scientifici del XXI secolo. Un percorso che attraversa la storia delle scienze in Cina dal terzo secolo a.C. fino ai nostri giorni, ricostruisce le regole che passo dopo passo, non senza deviazioni e ripensamenti, gli studiosi cinesi hanno stabilito per creare e gestire le loro “parole” composte con innumerevoli caratteri, gli hanzi, simbolo della cultura e della civiltà cinese, icone che ancora oggi “parlano” ai lettori, espressioni grafiche di oggetti e di concetti. La presentazione dell'opera di Feng Zhiwei, uno tra i maggiori esponenti della terminologia cinese contemporanea, ci accompagna nell'approfondimento degli orientamenti degli studi terminologici cinesi e nel confronto con quelli euro americani, a partire dagli studi svolti da Eugen Wüster all'inizio del XX secolo. L'analisi della terminologia cinese nella tecnologia del fotovoltaico e nel mondo economico-finanziario, costituisce il terreno di verifica delle pratiche terminologiche in essere nella lingua cinese e delle tendenze nella costruzione neologica e neonimica.
This research aims to illustrate the methodes used for creation of the specialized terminologies in the technical and scientific fields in the XXI century’s Chinese language. A pathway crossing the history of sciences in China from the III century B.C. until our days, reconstructs the rules that step after step the Chinese scholars have established in order to create and manage their “words” with the lot of characters, the hanzi, symbol of the Chinese culture and civilization, icons that still today “speak” to the readers, graphical expressions of objects and concepts. The presentation of the work of Feng Zhiwei, one among the greatest exponents of the contemporary Chinese terminology, is our guideline in a close examination of the Chinese terminological studies’ orientations, in comparison with the euro-americans ones, starting from the studies developed by Eugen Wüster at the beginning of the XX century. The analysis of the Chinese terminology in the photovoltaic technology and in the economic-financial world, constitutes the ground of verification of the actual terminological practices in the Chinese language and the tendencies in the neological and neonymical construction.

La ricerca intende illustrare le modalità applicative attraverso le quali si possono esprimere in lingua cinese le terminologie specialistiche dei campi tecnici e scientifici del XXI secolo. Un percorso che attraversa la storia delle scienze in Cina dal terzo secolo a.C. fino ai nostri giorni, ricostruisce le regole che passo dopo passo, non senza deviazioni e ripensamenti, gli studiosi cinesi hanno stabilito per creare e gestire le loro “parole” composte con innumerevoli caratteri, gli hanzi, simbolo della cultura e della civiltà cinese, icone che ancora oggi “parlano” ai lettori, espressioni grafiche di oggetti e di concetti. La presentazione dell'opera di Feng Zhiwei, uno tra i maggiori esponenti della terminologia cinese contemporanea, ci accompagna nell'approfondimento degli orientamenti degli studi terminologici cinesi e nel confronto con quelli euro americani, a partire dagli studi svolti da Eugen Wüster all'inizio del XX secolo. L'analisi della terminologia cinese nella tecnologia del fotovoltaico e nel mondo economico-finanziario, costituisce il terreno di verifica delle pratiche terminologiche in essere nella lingua cinese e delle tendenze nella costruzione neologica e neonimica.
This research aims to illustrate the methodes used for creation of the specialized terminologies in the technical and scientific fields in the XXI century’s Chinese language. A pathway crossing the history of sciences in China from the III century B.C. until our days, reconstructs the rules that step after step the Chinese scholars have established in order to create and manage their “words” with the lot of characters, the hanzi, symbol of the Chinese culture and civilization, icons that still today “speak” to the readers, graphical expressions of objects and concepts. The presentation of the work of Feng Zhiwei, one among the greatest exponents of the contemporary Chinese terminology, is our guideline in a close examination of the Chinese terminological studies’ orientations, in comparison with the euro-americans ones, starting from the studies developed by Eugen Wüster at the beginning of the XX century. The analysis of the Chinese terminology in the photovoltaic technology and in the economic-financial world, constitutes the ground of verification of the actual terminological practices in the Chinese language and the tendencies in the neological and neonymical construction.

Un digrafo o grafo dirigido se dice que es k-arco transitivo si tiene grupo de automorfismos que actúa transitivamente en el conjunto de k-arcos. Para un entero positivo k, un k-arco de un digrafo es una secuencia (x0,x1,.,xk) de k+1 vértices del digrafo tal que para cada i=0,.,k, (xi,xi+1) es un arco del digrafo. Los digrafos de esta clase tienen una alta simetría y por lo tanto pueden ser útiles como modelos de transmisión y de difusión de la información. Uno de los problemas de que nos ocupamos en esta Tesis es la modelización de topologías de redes de interconexión altamente simétricas mediante digrafos k-arco transitivos. Así, una primera parte de la tesis se dedica precisamente a la construcción de digrafos k-arco transitivos, que es una de las principales contribuciones de la tesis.

La forma en que se estructura esta memoria es la siguiente:

En los primeros Capítulos incluimos la notación y terminología básica de digrafos que utilizaremos a lo largo de la Tesis, así como un estado del arte de otras construcciones de digrafos k-arco transitivos conocidas hasta la fecha. Introducimos también las herramientas claves para nuestra construcción de digrafos k-arco transitivos como son las 1-factorizaciones y los recubrimientos de digrafos. En particular, definimos los recubrimientos de Cayley de digrafos arco-coloreados.

En el Capítulo 3 presentamos nuestra construcción de digrafos k-arco transitivos, que es también una técnica de construcción de recubrimientos k-arco transitivos de digrafos conexos regulares arbitrarios para cada entero positivo k. Como técnica de contrucción de recubrimientos k-arco transitivos, generaliza los resultados de Babai de 1985 para los casos k=0,1. La idea de la construcción consiste en escoger recubrimientos vértice transitivos "apropiados" del digrafo línea k-línea iterado del digrafo de partida, de manera que estos recubrimientos sean también digrafos k-línea iterados. Además, los digrafos k-arco transitivos de los que son k-línea iterados resultan ser además recubrimientos del digrafo de partida. Los recubrimientos "apropiados" de los digrafos k-línea iterados son recubrimientos de Cayley de los digrafos con 1-factorizaciones k-uniformes. Previamente, definimos las 1-factorizaciones k-uniformes de digrafos k-línea iterados y probamos que todo digrafo k-línea iterado admite 1-factorizaciones de este tipo.

En el Capítulo 4 introducimos el concepto de cuadrado latino uniforme y damos una caracterización de las 1-factorizaciones 1-uniformes de digrafos línea en términos de cuadrados latinos uniformes. En particular, obtenemos el número de 1-factorizaciones 1-uniformes de un digrafo línea en función del número de cuadrados latinos uniformes de manera constructiva. Se demuestra también que los cuadrados latinos uniformes son isomorfos al cuadrado latino de la tabla de composición de un grupo del mismo orden. Como consecuencia, calculamos explicítamente los cuadrados latinos uniformes de orden pequeño y obtenemos las 1-factorizaciones 1-uniformes de digrafos línea de grado pequeño de algunas familias de digrafos. La última parte del capítulo la dedicamos a la representación de grupos de permutaciones que actúan regularmente en el conjunto de arcos de un digrafo.

En el Capítulo 5 estudiamos el grupo de automorfismos de los recubrimientos k-arco transitivos que obtenemos con nuestra técnica. Se dan resultados interesantes en términos de la normalidad para los recubrimientos de Cayley de grado dos. Por último en este capítulo, estudiamos la estructura del grupo de automorfismos de los digrafos k-arco transitivos que son homeomorfos a un ciclo y en particular, vemos que un digrafo de Cayley es homeomorfo a un ciclo si y sólo si existe un subgrupo normal del grupo base tal que los generadores están contenidos en una de las clases laterales del subgrupo.
A digraph or directed graph is said k-arc transitive if it has automorphism group that acts transitively on the set of k-arcs. For a positive integer k, a k-arc of a digraph is a sequence (x0,x1,.,xk) of k+1 vertices of the digraph such that for each i=0,.,k, (xi,xi+1) is an arc of the digraph. Digraphs in this class have high symmetry and so they can be useful as models of transmission and diffusion of the information. One of the problems we work on this Thesis is the modelation of topologies of highly symmetric interconnection networks using k-arc transitive digraphs. Thus, the first part of the Thesis is devoted to the construction of k-arc transitive digraphs, which is one of the main contributions of this Thesis.

The memory of the Thesis is structured as follows.

In the firstly chapters we introduced the notation and basic terminology about graphs that we are going to use throughout the Thesis. Moreover, we include a short background about another constructions of k-arc transitive digraphs known up to now. We also include the main ingredients for our construction of k-arc transitive digraphs as the 1-factorizations and covers of digraphs. In particular, we define the Cayley covers of arc-colored digraphs.

In Chapter 3 we present our construction of k-arc transitive digraphs, which is also a technique to construct k-arc transitive covers of connected regular arbitrary digraphs for every positive integer k. As a construction tecnique of k-arc transitive digraphs, it generalizes results of Babai of 1995 for the cases k=0,1. The idea of the construction consists of choosing 'appropiate' vertex transitive covers of the k-line iterated digraph of the starting digraph in such a way that this covers are also k-line iterated digraphs. Furthermore, the k-arc transitive digraphs of which they are k-line iterated digraphs turn out to be covers of the starting digraph. The 'appropiate' covers of k-line iterated digraphs are Cayley covers of digraphs with k-uniform 1-factorization. Previously, we define a k-uniform 1-factorization of a k-line iterated digraph and we prove that every regular digraph admits 1-factorizations of this kind.

In Chapter 4 we introduce the concept of uniform latin square and we give a characterization of the 1-uniform 1-factorizations of line digraphs in terms of uniform latin squares. In particular, we obtain the number of 1-uniform 1-factorizations of a line digraph as a function of the number of uniform latin squares in a constructive way. We also prove that uniform latin squares are isomorphic to a latin square of the composition table of a group of the same size (in fact, the group is the complete set of discordant permutations obtained by the columns of the latin square). As a consequence, we calculate explicitly the uniform latin squares of small order and we obtain the 1-uniform 1-factorization of line digraphs of small degree of some families of digraphs. The last part of this chapter is devoted to the representation of permutation groups that acts regularly on the set of arcs of a digraph.

In Chapter 5 we study the automorphism group of the k-arc transitive covers we obtain with our technique. We give some results in terms of the normality for the Cayley covers of degree two. Finally in this chapter, we study the structure of the automorphism group of the k-arc transitive digraphs homomorphic to a directed cycle. In particular, we see that a Cayley digraph is homomorphic to a cycle if and only if there exists a normal subgroup of the base group such that the generators are contained in one of the cosets of the subgroup.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido.
In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.

Normalment les grans xarxes d'interconnexió o de comunicacions estan dissenyades utilitzant tècniques de la teoria de grafs. Aquest treball presenta algunes contribucions a aquest tema. Concretament, presentem dues noves operacions: el "producte Jeràrquic" de grafs i el "producte Manhattan" de digrafs. El primer és una generalització del producte cartesià de grafs i ens permet construir algunes famílies amb un alt grau de jerarquia, com l'arbre binomial, que és una estructura de dades molt utilitzada en algorísmica. El segon dóna lloc a les conegudes Manhattan Street Networks, les quals han estat extensament estudiades i utilitzades per modelar algunes classes de xarxes òptiques. En el nostre treball, definim formalment i analitzem el cas multidimensional d'aquestes xarxes. Estudiem algunes propietats dels grafs o digrafs obtinguts mitjançant les dues operacions esmentades, especialment: els paràmetres estructurals (les propietats de l'operació, els subdigrafs induïts, la distribució de graus i l'estructura de digraf línia), els paràmetres mètrics (el diàmetre, el radi i la distància mitjana), la simetria (els grups d'automorfismes i els digrafs de Cayley), l'estructura de cicles (els cicles hamiltonians i la descomposició en cicles hamiltonians arc-disjunts) i les propietats espectrals (els valors i vectors propis). En el darrer cas, hem trobat, per exemple, que la família dels arbres binomials tenen tots els seus valors propis diferents, "omplint" tota la recta real. A més a més, mostrem la relació del seu conjunt de vectors propis amb els polinomis de Txebishev de segona espècie. També hem estudiat alguns protocols de comunicació, com els enrutaments locals i els algorismes de difusió. Finalment, presentem alguns models deterministes (com les xarxes Sierpinski i d'altres), els quals presenten algunes propietats pròpies de les xarxes complexes reals (com, per exemple, Internet).
Large interconnection or communication networks are usually designed and studied by using techniques from graph theory. This work presents some contributions to this subject. With this aim, two new operations are proposed: the "hierarchical product" of graphs and the "Manhattan product" of digraphs. The former can be seen as a generalization of the Cartesian product of graphs and allows us to construct some interesting families with a high degree of hierarchy, such as the well-know binomial tree, which is a data structure very used in the context of computer science. The latter yields, in particular, the known topologies of Manhattan Street Networks, which has been widely studied and used for modelling some classes of light-wave networks. In this thesis, a multidimensional approach is analyzed. Several properties of the graphs or digraphs obtained by both operations are dealt with, but special attention is paid to the study of their structural parameters (operation properties, induced subdigraphs, degree distribution and line digraph structure), metric parameters (diameter, radius and mean distance), symmetry (automorphism groups and Cayley digraphs), cycle structure (Hamilton cycles and arc-disjoint Hamiltonian decomposition) and spectral properties (eigenvalues and eigenvectors). For instance, with respect to the last issue, it is shown that some families of hypertrees have spectra with all different eigenvalues "filling up" all the real line. Moreover, we show the relationship between its eigenvector set and Chebyshev polynomials of the second kind. Also some protocols of communication, such as local routing and broadcasting algorithms, are addressed. Finally, some deterministic models (Sierpinsky networks and others) having similar properties as some real complex networks, such as the Internet, are presented.

Los estudios desarrollados se enmarcan, dentro de la teoría de grafos, en el análisis de condiciones suficientes para obtener algunas medidas de conectividad optima.se han estudiado condiciones de tipo mixto para el caso de dígrafos bipartitos que mejoran los conocidos hasta el momento.se han estudiado la t-distancia conectividad, construyendo dígrafos que muestran la independencia de los parámetros que le definen y obteniendo cotas superiores sobre el diámetro que garantizan valores óptimos para las mismas.se ha introducido el concepto de diámetro condicional que ha permitido la ampliación de las cotas conocidas sobre el diámetro, así como la mejora de algunas de ellas. Por último se han obtenido nuevas condiciones de tipo chartrand para la conectividad y la superconectividad de dígrafos s-geodeticos.

Orientador : Clovis Perin Filho
Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica.
Made available in DSpace on 2018-07-13T23:49:57Z (GMT). No. of bitstreams: 1 Machado_ArleneFortunato_D.pdf: 7694121 bytes, checksum: 0d9d500491ffd36e83900ea3de723bc0 (MD5) Previous issue date: 1991
Resumo: Este trabalho apresenta um estudo de uma generalização de um problema de seleção de vértices em digrafos e propõe a resolução deste problema através de métodos iterativos, em que em cada iteração, um problema de seleção é resolvido. A importância deste problema é devida ao seu relacionamento com alguns problemas clássicos de otimização (designação, bemparelhamento bipartido de custo máximo, fluxo de custo mínimo). É também, apresentado um estudo para um problema de seleção de vértices de um digrafo, estabelecendo relações entre este problema e o de b-emparelhamento máximo bipartido. Algoritmos para os problemas de b-emparelhamento máximo bipartido, seleção de vértices e seleção de vértices generalizada são desenvolvidos. Os algoritmos apresentados para um mesmo problema são comparados entre si
Abstract: A generalization of a vertex selection problem is presented and a resolution of this problem using an iterative method is proposed. A vertex selection problem is solved in each iteration of this method. The importance of this problem lies on its relationship to some classical optimization problems (assignment, maximum cost bipartite b-matching, minimum cost flow). A study of a vertex selection problem in a digraph is also presented. A relationship between this problem and the maximum bipartite b-matching problem is established. Algorithms to solve the maximum bipartite b-matching, the vertex selection and the generalized vertex selection problems are developed and the algorithms for each of the problems are compared.
Doutorado
Doutor em Engenharia Elétrica

La conectividad condicional, definida por Harary en 1983, mide el mínimo número de vértices (o ramas) que hay que eliminar de un grafo o digrafo de forma que todas las componentes conexas resultantes tengan una propiedad prefijada de antemano. La importancia de los diferentes tipos de conectividad condicional está unida al concepto de supervivencia de las componentes que se determinan cuando la red se interrumpe, lo que se expresa especificando las propiedades de estas componentes. Engloban tanto la conectividad estándar como la superconectividad ya que pueden ser interpretadas como conectividades condicionales con respecto a la propiedad que consiste en tener más de cero vértices o un vértice respectivamente.

En esta tesis presentamos condiciones suficientes de dos tipos que garantizan altas conectividades condicionales: cotas superiores sobre diámetro y cotas inferiores sobre el orden, ambas formuladas en términos del girth en el caso de grafos, o bien en función del semigirth l en el caso de digrafos.

El primer tipo de conectividad condicional abordada es la t-distancia conectividad que juega un papel importante a la hora de medir la fiabilidad de la red como una función de la distancia entre los nodos que queremos comunicar. En este caso se requiere que los conjuntos desconectadotes separen vértices que estaban suficientemente alejados en el (di)grafo original. Se define el t-grado y se muestra que los parámetros que miden la t-distancia conectividad la arco t-distancia conectividad y el t-grado están relacionados por desigualdades que generalizan las desigualdades conocidas para las conectividades estándar. Además, se prueba que otra de las propiedades que estos nuevos parámetros mantienen es la independencia.

El trabajo realizado previamente permite profundizar en el estudio de la superconectividad de (di)grafos y de digrafos bipartitos. Se aborda el problema de desconectar de manera no trivial un digrafo superconectado, centrándonos en calcular la máxima distancia a la que se encuentra alejado un vértice de un conjunto desconectador no trivial de cardinal relativamente pequeño. Se introducen los parámetros que miden la superconectividad de un digrafo superconectado, y se estudian condiciones suficientes sobre el diámetro y el orden para obtener cotas inferiores sobre estas medidas de superconectividad. Por último se desarrolla un estudio en el caso de grafos, paralelo al realizado en el caso dirigido. Se expone una tabla en cuyas entradas figuran los órdenes de los grafos con el mayor número de vértices que se conocen hasta el momento junto con sus conectividades respectivas.

La última parte de la tesis está dedicado al estudio de grafos que modelan redes conectadas de forma óptima con respecto a la siguiente propiedad de tolerancia a fallos: Cuando algunos nodos o uniones fallan, se exige que en las componentes que se determinan en la red haya un número mínimo de nodos conectados entre sí. Esta conectividad condicional se denomina extraconectividad, que corresponde con la propiedad consistente en tener al menos un cierto número de vértices. Desde este punto de vista, tanto la conectividad estándar como la superconectividad, constituyen medidas de conectividad condicional. El trabajo llevado a cabo mejora sustancialmente las primeras condiciones suficientes sobre el diámetro dadas por Fiol y Fàbrega quienes ya habían conjeturado que la cota superior sobre el diámetro que se había encontrado era posible mejorarla.
The conditional connectivity defined by Harary in 1983, gives the minimum number of vertices or edges which have to be eliminated from a graph or a digraph in such a way all the resulting connected components satisfy a determined property The importance of the different types of conditional connectivity is linked to the concept of survival of the components that determine when the network is interrupted, which is expressed by specifying the properties of these components. They include both connectivity standard as superconectividad as they can be interpreted as a conditional connectivities with respect to the property that is to have more than zero points or a vertex respectively.

In this thesis we present sufficient conditions of two types that guarantee high conditional connectivities: upper bounds on diameter and lower bounds on the order, both in terms of girth made in the case graph, or in terms of semigirth l in the directed case.

The first type of conditional connectivity addressed is the t-distance connectivity that plays an important role in measuring the reliability of the network as a function of the distance between the nodes that we want to communicate. In this case disconnecting sets are required to separate vertices that were sufficiently distant in the original (di)graph. The t-degree is defined and it is shown that the parameters that measure the t-distance connectivity the arc t-distance connectivity and t-degree inequalities are related by the same inequalities known for standard connectivities. In addition, it is proved that another of the properties that these new parameters keep is the independence.

The work done previously allows to study in depth the superconectivity of digraphs and bipartite digraphs. It addresses the problem of disconnecting in a non-trivial way a superconnected digraph, focusing on calculating the maximum distance that is a remote vertex from a non-trivial disconnecting set of cardinality relatively small. The superconnectivity parameters are introduced and sufficient conditions on the diameter and on the order to obtain good measures of superconnectivity are given. Finally, there has been a case study in graphs, conducted in parallel to the directed case addressed. A table whose entries include orders of the graph with the largest number of vertices that are known so far along with their respective connectivities is exposed.

The last part of the thesis is devoted to the study of connected graphs modeling networks in an optimal way with respect to the following property of fault tolerance: When some nodes or links fail, it is required that all the components that are determined by the network have a minimum number of nodes connected to each other.
This kind of conditional connectivity is called extraconectivity, and corresponds to the property of having at least a certain number of vertices. From this point of view, both as the standard connectivity and superconectivity constitute measures of conditional connectivity. The work carried out substantially improves the early sufficient conditions on the diameter given by Fiol and Fàbrega who had already conjetured that the upper bound on the diameter, which they had been found could be improved.

El objetivo de la tesis es el estudio de diversosaspectos de redes de interconexión que pueden sermodeladas mediante la teoría de grafos, y masconcretamente, mediante dígrafos línea iterados enparticular se presentan, para estos grafos, protocolos dediseminación de la información (broadcasting) que mejorantodos los resultados anteriores en cuanto a lavulnerabilidad, esta se estudia bajo dos aspectos: encuanto a la vulnerabilidad del encaminamiento, sepresentan nuevas cotas superiores para el diámetro deldígrafo de supervivencia para dígrafos línea iterados;por lo que respecta a la vulnerabilidad del diámetro, sedefinen nuevas familias de dígrafos que resultan seroptimas de forma asintótica respecto al grado, para elproblema (delta,d',s).

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.

Formulación matemática de un método general para el diseño de redes y su aplicación para resolver problemas de optimización en algunas familias de redes conocidas así como para nuevas familias definidas.

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)}.

L'objectiu d'aquesta tesi és aprofondir en l'estudi d'una certa família de dígrafs, els dígrafs de prefix-cicle, donant nous detalls sobre la seva estructura, noves maneres d'enfocar el seu estudi, i dissenyant bons esquemes de comunicació. Es completa d'aquesta forma l'estudi iniciat per altres autors i s'en refoça el seu interès com a bon model de xarxa d'interconnexió.

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.

La conectividad condicional, definida por Harary en 1983, mide el mínimo número de vértices (o ramas) que hay que eliminar de un grafo o digrafo de forma que todas las componentes conexas resultantes tengan una propiedad prefijada de antemano. La importancia de los diferentes tipos de conectividad condicional está unida al concepto de supervivencia de las componentes que se determinan cuando la red se interrumpe, lo que se expresa especificando las propiedades de estas componentes. Engloban tanto la conectividad estándar como la superconectividad ya que pueden ser interpretadas como conectividades condicionales con respecto a la propiedad que consiste en tener más de cero vértices o un vértice respectivamente.En esta tesis presentamos condiciones suficientes de dos tipos que garantizan altas conectividades condicionales: cotas superiores sobre diámetro y cotas inferiores sobre el orden, ambas formuladas en términos del girth en el caso de grafos, o bien en función del semigirth l en el caso de digrafos.El primer tipo de conectividad condicional abordada es la t-distancia conectividad que juega un papel importante a la hora de medir la fiabilidad de la red como una función de la distancia entre los nodos que queremos comunicar. En este caso se requiere que los conjuntos desconectadotes separen vértices que estaban suficientemente alejados en el (di)grafo original. Se define el t-grado y se muestra que los parámetros que miden la t-distancia conectividad la arco t-distancia conectividad y el t-grado están relacionados por desigualdades que generalizan las desigualdades conocidas para las conectividades estándar. Además, se prueba que otra de las propiedades que estos nuevos parámetros mantienen es la independencia.El trabajo realizado previamente permite profundizar en el estudio de la superconectividad de (di)grafos y de digrafos bipartitos. Se aborda el problema de desconectar de manera no trivial un digrafo superconectado, centrándonos en calcular la máxima distancia a la que se encuentra alejado un vértice de un conjunto desconectador no trivial de cardinal relativamente pequeño. Se introducen los parámetros que miden la superconectividad de un digrafo superconectado, y se estudian condiciones suficientes sobre el diámetro y el orden para obtener cotas inferiores sobre estas medidas de superconectividad. Por último se desarrolla un estudio en el caso de grafos, paralelo al realizado en el caso dirigido. Se expone una tabla en cuyas entradas figuran los órdenes de los grafos con el mayor número de vértices que se conocen hasta el momento junto con sus conectividades respectivas.La última parte de la tesis está dedicado al estudio de grafos que modelan redes conectadas de forma óptima con respecto a la siguiente propiedad de tolerancia a fallos: Cuando algunos nodos o uniones fallan, se exige que en las componentes que se determinan en la red haya un número mínimo de nodos conectados entre sí. Esta conectividad condicional se denomina extraconectividad, que corresponde con la propiedad consistente en tener al menos un cierto número de vértices. Desde este punto de vista, tanto la conectividad estándar como la superconectividad, constituyen medidas de conectividad condicional. El trabajo llevado a cabo mejora sustancialmente las primeras condiciones suficientes sobre el diámetro dadas por Fiol y Fàbrega quienes ya habían conjeturado que la cota superior sobre el diámetro que se había encontrado era posible mejorarla.
The conditional connectivity defined by Harary in 1983, gives the minimum number of vertices or edges which have to be eliminated from a graph or a digraph in such a way all the resulting connected components satisfy a determined property The importance of the different types of conditional connectivity is linked to the concept of survival of the components that determine when the network is interrupted, which is expressed by specifying the properties of these components. They include both connectivity standard as superconectividad as they can be interpreted as a conditional connectivities with respect to the property that is to have more than zero points or a vertex respectively.In this thesis we present sufficient conditions of two types that guarantee high conditional connectivities: upper bounds on diameter and lower bounds on the order, both in terms of girth made in the case graph, or in terms of semigirth l in the directed case.The first type of conditional connectivity addressed is the t-distance connectivity that plays an important role in measuring the reliability of the network as a function of the distance between the nodes that we want to communicate. In this case disconnecting sets are required to separate vertices that were sufficiently distant in the original (di)graph. The t-degree is defined and it is shown that the parameters that measure the t-distance connectivity the arc t-distance connectivity and t-degree inequalities are related by the same inequalities known for standard connectivities. In addition, it is proved that another of the properties that these new parameters keep is the independence.The work done previously allows to study in depth the superconectivity of digraphs and bipartite digraphs. It addresses the problem of disconnecting in a non-trivial way a superconnected digraph, focusing on calculating the maximum distance that is a remote vertex from a non-trivial disconnecting set of cardinality relatively small. The superconnectivity parameters are introduced and sufficient conditions on the diameter and on the order to obtain good measures of superconnectivity are given. Finally, there has been a case study in graphs, conducted in parallel to the directed case addressed. A table whose entries include orders of the graph with the largest number of vertices that are known so far along with their respective connectivities is exposed.The last part of the thesis is devoted to the study of connected graphs modeling networks in an optimal way with respect to the following property of fault tolerance: When some nodes or links fail, it is required that all the components that are determined by the network have a minimum number of nodes connected to each other.This kind of conditional connectivity is called extraconectivity, and corresponds to the property of having at least a certain number of vertices. From this point of view, both as the standard connectivity and superconectivity constitute measures of conditional connectivity. The work carried out substantially improves the early sufficient conditions on the diameter given by Fiol and Fàbrega who had already conjetured that the upper bound on the diameter, which they had been found could be improved.

Les parasites présentant une large distribution géographique et un cycle de vie complexe offrent une rare occasion pour l'étude des mécanismes de spéciation et d'évolution. Ligula intestinalis (Cestoda, Diphyllobothriidea) présente une large distribution géographique et évolue dans un cycle de vie à plusieurs hôtes. Les études montrent que le spectre d'hôte varie en fonction des populations étudiées et qu'il existe des différences de pathologie entre des espèces hôtes vivant en sympatrie. En outre, le tableau de L. Intestinalis est d'autant plus complexe du fait de la paraphylie de cette espèce avec les espèces Ligula colymbi et Digramma interrupta. Le but de cette étude est de comprendre l'origine des différences écobiologiques et des discordances phylogénétiques et de tester l'hypothèse de l'existence de différentes lignées/espèces de ce parasite. Pour ce faire, nous avons analysé la phylogénie et la structure génétique de plérocercoides de ligules appartenant à différentes espèces hôtes et régions géographiques à large échelle. Les résultats basés sur les séquences génomiques montrent l'existence de différents patrons évolutifs: A l'échelle locale, une structure génétique plate a été trouvée et est vraisemblablement due à la migration de l'hôte définitif empêchant la formation d'entités génétiques différentes. A contrario, à large échelle des groupes génétiquement distants et bien isolés sont présents montrant une forte correspondance entre la structuration génétique et l'isolement géographique. De plus, une structuration liée à l'espèce hôte est également observée. Les spécimens de ligules identifiés comme des individus de l'espèce L. Colymbi se répartissent dans différents clades de L. Intestinalis tandis que les individus de Digramma montrent une différentiation claire du reste des individus de Ligula. Cependant, leur clade monophylétique apparaît au sein des spécimens de L. Colymbi et L. Intestinalis. Ainsi le genre Digramma devra être reconsidéré
Parasite species with global distribution and complex life cycle offer a rare opportunity to study mechanisms of speciation and evolution. Ligula intestinalis (L. ) (Cestoda, Diphyllobothriidea) has a widespread distribution and a life cycle with several hosts Available records indicate that the host spectra used by this species is not uniform across the investigated populations and show differences in the pathology between sympatric cyprinid species. Furthermore, complication of L. Intestinalis picture stems from the indication that this species may be paraphyletic with the species Ligula colymbi and Digramma interrupta. The aim of this study was to understand the origin of eco-biological differences and phylogenetic discrepancies and to test the hypothesis of the existence of several strains/species. . For this purpose, phylogeny and genetic structure have been analyzed for Ligula plerocercoids native to different host species and geographic regions at a global scale. Data based on genomic sequences and hypervariable markers show different evolutionary patterns: At a local scale, a flat genetic structure was found and is most likely due to bird migration preventing the creation of different genetic strains/species. In contrast, at a global scale, genetically distant and well separated clusters are present, indicating a conspicuous correspondence between genetics and geography. Beside geography, obvious host-specific-based structures are found. Ligula specimens identified as L. Colymbi are partitioned in separate clades of L. Intestinalis thus questions the reliability of species identification primarily based on definitive host species when morphological characters are inconclusive. Samples of Digramma show a clear differentiation from the analysed Ligula specimens. However, their monophyletic clade appears within Ligula specimens indicating that D. Interrupta may well represent a valid species of the genus Ligula rather than of Digramma

My thesis analyses the relationship between writing systems and ethnic cohesion in the processes of national identity construction in Bulgaria and Croatia. I investigate the role played by alphabetic questions in the course of some critical moments of socio-politic passage in both of the countries, corresponding to the inter-war and post-imperial period and to the most recent post-socialist one. With such aim, I consider several texts related to “alphabetic disputes” (in reference with the Cyrillic/Latin debate), coming from representatives of the intellectual and cultural field, integrated in some cases with official legal documents related to writing matters and inscribed in the respective signification space at a national and international ideological level. The aim is to highlight the fact that delicate questions in the field of writing systems with the respective choices on the matter reflect the positioning of the countries in different political and cultural contexts, representing the attempt to construct a national narrative in line with the historical moment and the dominant identitary ideology. In addition to this, I will prove that the national construction serves itself of the element of the alphabet in order to affirm in a highly symbolic way its identity in relation to a significant “Other”, in what can be interpreted as a symptom of an assimilatory fear that has never been appeased, characteristic of the Balkan area.

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

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs.
O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.

Dissertação de mestrado em Contabilidade
A Universidade de Coimbra (UC) (Portugal), fundada no século XIII, foi um dos principais pólos científicos a nível mundial. Pioneira no ensino superior público português manteve-se num regime de protetorado, num período marcado pelo Absolutismo e pela centralização do poder. No entanto, em 1772, durante a governação de D. José I, o ensino foi sujeito a uma profunda reforma, sendo reestruturada a Universidade pedagógica e economicamente. Neste sentido, abordamos o governo económico da pré e pós-reforma pombalina, onde evidenciamos a adoção da partida dobrada e de novos livros de escrituração, assim como a mudança na informação produzida e dos destinatários da mesma. Através de um estudo de caso exploratório ao arquivo da Universidade, analisamos sistemas, técnicas e procedimentos contabilísticos estabelecidos nos estatutos e na legislação publicada entre os anos de 1750 a 1800. Posteriormente, verificamos e interpretamos como e em que circunstâncias foram escriturados os livros de contabilidade que serviram na prestação de contas, assim como os inventários e outra documentação administrativa e contabilística existente em arquivo. Assim, os registos contabilísticos da segunda metade de setecentos foram interpretados como fenómenos socialmente construídos e, como tal, não independentes dos aspetos sociais, económicos e políticos que envolveram a produção da informação financeira (Adams, Hoque, & McNicholas, 2006). Vivia-se uma época de crise económica em que a racionalização se impunha como medida política, sendo por isso disciplinadas e burocratizadas as principais organizações públicas do reino. Neste contexto, foi adotada tecnologia sofisticada de contabilidade na produção da informação financeira, facilitando a supervisão dos órgãos centrais (Ezzamel & Bourn, 1990). A adoção da partida dobrada, como mecanismo eficiente de supervisão à distância, incrementou a fiabilidade da informação financeira (Lemarchand, 1999). Contudo, mantiveram a partida simples para a vigilância diária dos fluxos de caixa na Tesouraria da Universidade, no que resultou num aumento de livros de escrituração e de mão-de-obra especializada, que se refletiu na hierarquia, na escrituração e na supervisão panóptica da contabilidade.
The University of Coimbra (UC) (Portugal), founded in the 13th century, was one of the major scientific centers in the world. Pioneer in the Portuguese public higher learning system, it remained in a protectorate system, in a period marked by Absolutism and the centralization of power. However, in 1772, during the rule of Joseph I, it was subject to an in-depth reform, being that the University was restructured pedagogical and economically. In this sense, we will approach the economic government of the pre and post reform, where we will highlight the adoption of double entry bookkeeping and new accounting books, as well as the change in the way information was produced and to whom it was directed. Through an exploratory case study we will analyze the University’s accounting system and the techniques and procedures laid down in the statutes and legislation published between 1750 and 1800. Then, we analyze how and under what circumstances the accounting books used in accountability, as well as the inventories and other administrative and accounting documentation that exist on file were created. Thus, the accounting records from the second half of seventeen hundreds were interpreted as a socially constructed phenomenon and therefore not independent of the social, economic and political aspects involving the production of financial information (Adams et al., 2006). It was a time of economic crisis in which rationalization was necessary as a political measure, and as such the main public organizations of the Kingdom were disciplined and bureaucratized. In this context the accounting sophisticated technology adopted in the production of financial information was improved, facilitating the control of the main authorities (Ezzamel & Bourn, 1990). The adoption of double entry bookkeeping as an efficient mechanism of control increased the reliability of the financial information (Lemarchand, 1999). However, single entry bookkeeping was maintained in the daily monitoring of cash flows in the University’s treasury. This resulted in an increase in accounting books and skilled labor to refine the hierarchy, the registration and panoptic control of accounting.

Tese mest. , Matemática, 2007, Universidade do Algarve
Key-words: matrix, graph, digraph. The way of relating matrices and graphs or digraphs is well known. Many properties of matrices are re ected in characteristics of their associated graphs (digraphs), and, conversely, to certain types of graphs correspond matrices with peculiar properties. The objective of this dissertation is to collect, systematize, and present some results already known about relationships be- tween graphs (digraphs) and matrices. Basic connections between graphs (digraphs) and matrices are presented along the rst chapters. In the fol- lowing chapters, concrete situations where properties of matries are deduced from the charateristics of their associated graphs (digraphs), and vice-versa, are presented. In this scope, properties of matrices related with chordal graphs, CDUM and cyclic digraphs are explored and, nally, properties of graphs associated to Fiedler matrices are studied.

Umieszczenie grafu w książce jest definiowane przez kolejność jego wierzchołków na grzbiecie książki i przyporządkowanie jego krawędzi stronom książki tak, aby na żadnej stronie krawędzie nie przecinały się. Umieszczenie zbioru częściowo uporządkowanego (posetu) P w książce polega na umieszczeniu jego digrafu pokrycia (diagramu Hassego), z elementami zbioru P na grzbiecie tworzącymi rozszerzenie liniowe zbioru P. Problemem jest umieszczenie posetu P na możliwie najmniejszej liczbie stron. Problem liczby stron dla posetów wydaje się być znacznie trudniejszy niż dla grafów. Na dwóch stronach można umieścić graf planarny, który jest podgrafem hamiltonowskiego grafu planarnego, natomiast nie jest znana charakteryzacja posetów dających się umieści na dwóch stronach. Ponadto, każdy graf planarny można umieścić na co najwyżej czterech stronach, natomiast przypuszcza się, ze w przypadku posetów planarnych liczba stron nie jest ograniczona. Wyniki w pracy dotyczą tych dwóch problemów. W Rozdziale 4 zamieszczono algorytm do umieszczania posetów drzewiastych na jednej stronie, który tworzy ramy dla algorytmów umieszczania posetów o rozbudowanej strukturze drzewiastej. W Rozdziale 5 rozważa się klasę posetów planarnych, w których każdy blok jest cyklem. Mimo swej prostoty, dwie strony nie wystarczają do ich umieszczenia. Każdy taki poset może być umieszczony na trzech stronach i trzy strony czasem są niezbędne. Najobszerniejsza cześć pracy stanowią Rozdziały 6 i 7, poświęcone posetom N-wolnym, pojawiającym się w wielu obszarach badan nad posetami. Rozważania w tych Rozdziałach bazują na podejściu teorio-grafowym, w którym digraf pokrycia posetu N-wolnego jest interpretowany jako digraf łukowy. Podano wzór na liczbę stron dla posetów N-wolnych o strukturze drzewiastej, oszacowano liczbę stron dla dowolnego posetu N-wolnego i przedstawiono algorytm umieszczania w książce dowolnych posetów, bazujący na przekształceniu posetu do posetu N-wolnego. W Rozdziale 7 są rozważane posety planarne. Podano lokalne warunki konieczne na to, aby N-wolny poset był planarny, skąd wywnioskowano, ze N-wolne posety planarne o strukturze drzewiastej można umieścić na dwóch stronach. Ta cześć pracy zawiera najważniejszy wynik pracy, ze N-wolny poset planarny, reprezentowany przez swój do góry płaski digraf pokrycia, można umieścić na dwóch stronach. Jako dowód tego twierdzenia przedstawiono algorytm o złożoności wielomianowej i udowodniono jego poprawność. Rozważania dotyczące posetów są prowadzone w języku (di)grafów z nimi związanych oraz z wykorzystaniem technik dowodzenia i konstrukcji algorytmicznych pochodzących z teorii grafów. Niektóre wyniki były prezentowane na kilku konferencjach [39], [41], [42]. MCS 2010: 05C10, 5C62, 05C76, 05C85, 06Axx, 06A06, 06A07, 68Q25 ACM CCS: 6.2.1, 6.2.2 Słowa kluczowe: zbiór częściowo uporządkowany (poset), digraf, zbiór i digraf N-wolny, zbiór i digraf planarny, drzewo, umieszczanie posetów w książce
In this Thesis we deal with the book embedding problem for partially ordered sets (posets). A book embedding of a graph G consists of two assignments: the vertices of G to the spine of a book in some order and the edges of G to the pages of the book so that the edges on the same page do not intersect. In a book embedding of a poset (P; ), the covering digraph (the Hasse diagram) of P is embedded with the elements of P on the spine as a linear extension of P. The objective is to minimize the number of pages used. The page number problem for posets seems to be more challenging and difficult than for graphs. It is known that the page number equals 2 for planar graphs which are subgraphs of Hamiltonian planar graphs, but no characterization of 2-page posets is known. Moreover, each planar graph can be embedded in 4 pages and it is conjectured that the page number for planar posets is unbounded. We focus in the Thesis on these two problems. In Section 4, an algorithm for 1-page embedding of tree-posets is presented which in the next sections is extended to run for several tree-structured posets. In Section 5, one such family of planar posets – tree-combinations of cycles – is introduced. Despite the simplicity of such posets, it is shown that in general they need 3 pages. In Sections 6 and 7, which are the main parts of the Thesis, the page number problem is considered in the family of N-free posets. Such posets have been recently investigated in the connection with various problems on graphs, digraphs, and posets. Our approach is based on the interpretation of covering digraphs of N-free posets as line digraphs. The page number is determined exactly for tree-structured N-free posets and some bounds are provided for arbitrary N-free posets. Moreover a book embedding algorithm is presented for arbitrary posets which is based on transformation of posets to N-free posets. In Section 7, our attention is focused on planar posets. Necessary conditions for an N-free poset to be planar are formulated and as a consequence we show that the page number of tree-structured N-free planar posets equals 2. Then we present the main result of the Thesis which states that any N-free planar poset given as its upward plane representation (drawing) can be embedded into 2 pages. The proof of this result is fully constructive – we provide a polynomial time algorithm for such embeddings. The investigations in this Thesis are carried on in the language and terms of graphs and digraphs related to posets and we use proof and algorithmic techniques from graph theory. Some of the results were presented at combinatorial meetings [39], [41], [42]. MCS 2010: 05C10, 5C62, 05C76, 05C85, 06Axx, 06A06, 06A07, 68Q25 ACM CCS: 6.2.1, 6.2.2 Key words: partially ordered set (poset), digraph, N-free digraph and poset, planar digraph and poset, tree, page number of graphs, digraphs, and posets