Academic literature on the topic 'Digrafia'

En este trabajo se vincula la Teoría de Matrices con la Teoría de Grafos, en particular se trabaja con polinomios característicos de matrices de precedencia y con el espectro de digrafos (h, j) adjuntos. El mismo tiene como objetivo enunciar y demostrar, mediante representaciones matriciales adecuadas, un teorema que permite determinar los autovalores de un digrafo (h, j) adjunto de un multidigrafo k–regular, dándose las respectivas multiplicidades y también la forma de los autovectores asociados.

In this paper we present the state of development of DIGRAMA, a system of electronic dictionaries and grammars of Portuguese. We describe briefly the general characteristics of the system, concentrating then on the analysis of two dictionary modules: DIGRAS and DIGRAF. The former is a dictionary of simple words, the latter is a dictionary of inflected forms. To each lexical entry of DIGRAS has been associated a code corresponding to the formal description of the morphological properties of the entries. This information constitutes the basis for a program of automatic generation of inflected forms. DIGRAF is made up of all the inflected forms from the words of DIGRAS.

This article explores modern Korean digraphia, its chracteristics, duality and formation. The author posits that the essential axis of argumentation of the Korean digraphic debate related to the applications of Chinese characters and Korean phonetic script was formed by the early part of the twentieth century, and would be recapitulated in the two Koreas against the backdrop of post-colonial metanarration and Cold War politics. The author asserts that the functional and synchronic nature of modern Korean digraphia was formed under the influence of the Lyotardian modernity emancipation and speculative (science) metanarratives, as well as the discourse of modern Korean nationalism, which synchronically formed in the Korean assertion of national identity and idependence, during Koreaʼs struggle against imperialism.

Artaxa digramma is a lepidopteran pest distributed throughout southern China, Myanmar, Indonesia, and India. Artaxa digramma nucleopolyhedrovirus (ArdiNPV) is a specific viral pathogen of A. digramma and deemed as a promising biocontrol agent against the pest. In this study, the complete genome sequence of ArdiNPV was determined by deep sequencing. The genome of ArdiNPV contains a double-stranded DNA (dsDNA) of 161,734 bp in length and 39.1% G+C content. Further, 149 hypothetical open reading frames (ORFs) were predicted to encode proteins >50 amino acids in length, covering 83% of the whole genome. Among these ORFs, 38 were baculovirus core genes, 22 were lepidopteran baculovirus conserved genes, and seven were unique to ArdiNPV, respectively. No typical baculoviral homologous regions (hrs) were identified in the genome. ArdiNPV had five multi-copy genes including baculovirus repeated ORFs (bros), calcium/sodium antiporter B (chaB), DNA binding protein (dbp), inhibitor of apoptosis protein (iap), and p26. Interestingly, phylogenetic analyses showed that ArdiNPV belonged to Clade II.b of Group II Alphabaculoviruses, which all contain a second copy of dbp. The genome of ArdiNPV was the closest to Euproctis pseudoconspersa nucleopolyhedrovirus, with 57.4% whole-genome similarity. Therefore, these results suggest that ArdiNPV is a novel baculovirus belonging to a newly identified cluster of Clade II.b Alphabaculoviruses.

Prispevek obravnava nekatere aspekte glasovnega sistema tistega razvojnega stadija pamfilskega dialekta, kije izpričan na silionskem napisu iz četrtega stoletja pr. n. št. V prvem delu se članek ukvarja z vzroki za sporadično palatalizacijo glasu u, relevantnostjo prehoda ερ > αρ za dialektalno umestitev pamfilščine ter z razlogi za ne beleženje aspirate v nekaterih besedah. V nadaljevanju se prispevek posveča določitvi glasovne vrednosti grafemov ϝ, W, ψ in digrafa υh ter etimologiji besede διϝια.

Turnamen tereduksi T adalah turnamen yang himpunan titiknya dapat dipartisi menjadi sub himpunan A dan B dimana setiap titik di sub himpunan A mengalahkan setiap titik di sub himpunan B. Digraf eksentris ED(T) dari turnamen T adalah digraf yang memiliki titik yang sama dengan T dan terdapat busur u ke v jika dan hanya jika v adalah titik dengan jarak terjauh dari u. Pada tulisan ini akan dibahas sifat-sifat digraph eksentris turnamen tereduksi T dengan sub turnamen yang diinduksi oleh sub himpunan A dan B diganti menjadi kelas turnamen yang khusus yaitu turnamen regular dan transtitif.

Kim Il Sung’s 1964 and 1966 conversations with linguists are appropriately deemed important as the establishment of the North’s “cultured language” as a standard, as well as guidance related to language purification and script. In the analysis of inflection point related to language planning and policy in the North, is the often guidance on re-enshrinement of teaching “Chinese characters” (hanja) in North Korean education. Clearly this was official pronouncement of functional, synchronic digraphia, which has been preserved and operationalized down to the present. Scholarship on these conversations, amounting to policy guidance, attribute the shift in policy related to script as an inflection point. The author of this article concurs with its importance, but with respect to digraphia in the North, the conversations related to hanja instruction served as a confirmation for what was a broad trend in North Korean language planning during the years 1953-1964, a language planning and policy fait accompli, diminishing the portrayal of the conversations as a digraphic inflection point in North Korea.

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.

Neste artigo, são mostrados resultados de uma re-implementação da busca em largura na linguagem C++ com estrutura bag e interface OpenMP. A implementação é baseada em uma proposta existente na bibliografia que utilizou a linguagem Cilk++, que foi descontinuada. Para os experimentos realizados neste presente trabalho, foram utilizados 10 grafos não direcionados e 10 digrafos em uma máquina composta de oito núcleos, com duas threads por núcleo. Em relação à versão serial, a nova implementação apresentou aceleração de 3,2 a 5,7x ao utilizar oito threads e de aproximadamente 3 a 8x ao utilizar 16 threads.

Determinar se uma rede possui um fluxo viável é um problema amplamente estudado e que pode ser resolvido em tempo polinomial. Investigamos um tipo específico de fluxo, o fluxo ramificado, que pode ser aplicado na busca por ramificações em digrafos. Consideramos o problema de encontrar múltiplos fluxos ramificados arco-disjuntos em uma rede e estudamos a complexidade deste problema com diferentes capacidades nos arcos. Um resultado anterior prova que, sob uma suposição teórica conhecida (ETH), em redes com n vértices tais que todos os arcos possuem capacidade n f (n), para uma função limitada f , o problema é difícil. Estendemos este resultado mostrando que, sob a mesma hipótese, o problema também é difícil quando as capacidades são iguais a f (n).