En este trabajo se estudia, mediante la Teoría de Grafos, el diseño de redes de interconexión para sistemas distribuidos. Los principales temas tratados son: 1. Se propone una metodología general para la obtención de redes de interconexión; 2. Aplicando dicho método, se obtienen nuevas topologías, tanto para redes locales como para sistemas multimicroprocesadores;3. A partir del nuevo concepto de congruencia en Zn, se optimizan las llamadas estructuras en doble lazo para redes locales. Asimismo, se estudia la aplicación de este concepto a otros problemas planteados en las Ciencias de la Computación, tales como el diseño de esquemas lineales para el almacenamiento de datos en memorias paralelas; 4. Se presenta el método del desdoblamiento de nodos para la obtención de redes de interconexión para multiprocesadores, y se estudia su relación con la técnica del digrafo línea aplicado a la resolución del Problema(Δ;D); 5. Se resuelve el problema de la reducción de conexiones en sistemas multibús caracterizando las configuracions mínimas mediante el Teorema de las Bodas de Hall,y se estudian varios problemas relacionados con el tema. / This work deals with the applications of Graph Theory to the study and design of interconnection networks for distributed systems. The main subjects addressed are: 1. A general methodology for obtaining interconnection networks is proposed; 2. From such a method, new topologiesfor both local networks and multiprocessor systems are obtained; 3. From the new concept of congruence in Zn, the so-called double-loop networks for local networks are optimized. Moreover, such a concept is applied to study some other problems in Computer Science, such as the design of skewing schemes for the storage of data in parallel memories; 4. The method os doubling nodes is proposed to obtain interconnection networks for multiprocessor systems, and its relation with the line digraph technique is studied in order to solve the (Δ;D) Problem; The problem of the reduction of connections in multibus systems is solved by using the Hall Marriage Theorem, and several related problems are also considered.

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

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