Tese de doutoramento. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 2005

En este trabajo hemos realizado un estudio completo sobre la vulnerabilidad del diámetro de dos familias de grafos:Los grafos impares y los n-cubo plegados. En el caso de los grafos impares, hemos probado que la eliminación de cualquier conjunto de vértices o ramas de cardinalidad k menor que el grado incrementa el diámetro de los subgrafos resultantes a lo sumo en dos unidades.Asimismo, hemos estudiado como varían los parámetros d'k y d'k' cuando eliminamos k vértices o ramas del grafo.Análogamente, para los grafos cubo plegado hemos estudiado como varían estos parámetros cuando eliminamos k vértices o ramas del grafo, para valores de k inferiores al grado del grafo. Por los resultados obtenidos podemos afirmar que ambas familias de grafos son adecuadas para la implementación de redes de interconexión tolerantes a fallos.Otro estudio que hemos realizado en esta tesis trata sobre el diseño de redes densas fiables. Y hemos obtenido cuatro grafos (A,D,D,1) que mejoran cinco cotas presentadas en la tabla de grandes grafos (A,D,D,1).

El grafo de intersección de una familia de conjuntos es un grafo cuyos vértices son los miembros de la familia y la adyacencia es definida por la intersección no vacía de los correspondientes miembros. Los grafos de intersección son bastante conocidos y muy estudiados. Algunas clases de grafos definidas como intersección son hereditarias y pueden ser caracterizadas por subgrafos inducidos prohibidos minimales. Los elementos de las familias y las propiedades que las definen aparecen en varios contextos, modelando diferentes situaciones, inclusive de la vida real, lo que es un incentivo adicional para el estudio de estas clases. Ejemplos clásicos son los grafos de intervalos y los grafos cordales. Un grafo de intervalos es el grafo de intersección de una familia de intervalos en la recta real, o, en forma equivalente, el grafo vértice intersección de una familia de subcaminos de un camino. Llamamos Intervalos a la clase formada por los grafos de intervalos. Un grafo cordal es un grafo sin ciclos inducidos de longitud al menos cuatro. Llamamos Cordal a la clase formada por los grafos cordales. Gavril probó que un grafo es cordal si y sólo si es el grafo vértice intersección de una familia de subárboles de un árbol. Ambas clases han sido cuidadosamente estudiadas en la literatura. Con el fin de definir nuevas clases de grafos representadas por subárboles, se imponen condiciones en los árboles, subárboles y en el tamaño de la intersección. Sean h, s y t enteros positivos; una (h,s,t)-representación de un grafo G consiste de un árbol huésped T y una colección (T_v), siendo v un vértice de G, de subárboles de T, tal que: el grado máximo de T es a lo sumo h; todo subárbol T_v tiene grado máximo a lo sumo s; dos vértices v y w son adyacentes en G si y sólo si los correspondientes subárboles T_v y T_w tienen al menos t vértices en común en T. La clase de grafos que tiene una (h,s,t)-representación es denotada [h,s,t]. Cuando no hay restricción en el grado máximo de T o en el grado máximo de los subárboles, usamos h=∞ y s=∞ respectivamente. De ahí que, [∞, ∞,1] = Cordal y [2,2,1] = Intervalos. Las clases [∞,2,1] y [∞,2,2] son llamadas VPT (vertex intersection graph of paths in a tree) y EPT (edge intersection graph of paths in a tree) respectivamente. VPT y EPT son clases incomparables de grafos. Sin embargo, cuando el grado máximo del árbol huésped es tres la clase de los grafos VPT coincide con la clase de los grafos EPT. Los grafos VPT son útiles en muchas áreas, entre las cuales cabe destacar la genética, arqueología y ecología. Los grafos EPT son usados en aplicaciones de redes, donde el problema de planificación de llamadas no dirigidas en una red que es un árbol es equivalente al problema de colorear un grafo EPT. La red de comunicación está representada como un grafo no dirigido de interconexión, donde cada arista es asociada con una conexión física entre nodos. Una llamada no dirigida es un camino en la red. Cuando la red es un árbol, este modelo es claramente una representación EPT. Colorear el grafo EPT de forma tal que dos vértices adyacentes tengan distintos colores, significa que llamadas no dirigidas que comparten una conexión física tienen que planificarse en distintos momentos. En los últimos años, el estudio de las clases [h,s,t] ha merecido varias publicaciones en la literatura. El mínimo t tal que un grafo dado pertenece a [3,3,t] ha sido estudiado. Se ha demostrado que [3,3,1] = Cordal. Los [4,4,2] grafos han sido caracterizados y se da un algoritmo polinomial para su reconocimiento. Las clases [4,2,2] y [4,3,2] han sido estudiadas. La relación entre diferentes clases de grafos de intersección de caminos en un árbol también ha sido analizada. Gravril mostró que el problema de reconocer a los grafos VPT es polinomial. Por otro lado, el reconocimiento de los grafos EPT es un problema NP-completo. Esta Tesis está organizada de la siguiente forma: El Capítulo 2 contiene definiciones que serán utilizadas en los capítulos siguientes y que son necesarias para entender el texto. En el Capítulo 3 nos enfocamos en las clases [h,2,1] para cualquier h>2 fijo; estas son todas subclases de VPT. Caracterizamos a los grafos [h,2,1] usando el número cromático. Mostramos que el problema de decidir si un grafo VPT dado pertenece a [h,2,1] es NP-completo, mientras que el problema de decidir si el grafo dado pertenece a [h,2,1]-[h-1,2,1] es NP-difícil. Ambos problemas permanecen difíciles aún cuando nos restringimos a la clase VPT ∩ Split. Adicionalmente, presentamos una subclase no trivial de VPT ∩ Split en la cual estos problemas son polinomiales. El caso h=2 no es considerado porque [2,2,1]= Intervalos. Nuestros resultados se aplican para cualquier h>2 fijo, pueden ser vistos como una generalización del caso h=3 el cual coincide con la clase [3,2,1]=[3,2,2]= VPT ∩ EPT = EPT ∩ Cordal. Las clases [h,2,1], son cerradas por subgrafos inducidos, de ahí que cada una puede ser caracterizada por una familia de subgrafos inducidos prohibidos minimales. Tal familia es conocida sólo para h=2 y hay algunos resultados parciales para h=3. En este Capítulo asociamos los subgrafos inducidos prohibidos minimales para [h,2,1] que son VPT con los grafos (color) críticos. Describimos cómo obtener subgrafos inducidos prohibidos minimales a partir de los grafos críticos, más aún, mostramos que la familia de grafos obtenida usando nuestro procedimiento es exactamente la familia de subgrafos inducidos prohibidos minimales para [h,2,1] que son VPT. Esta familia junto con la familia de subgrafos inducidos prohibidos minimales para VPT, es la familia de subgrafos inducidos prohibidos minimales para [h,2,1], con h>2. En el Capítulo 4 caracterizamos la clase [h,2,1] por subgrafos inducidos prohibidos minimales para cada h>2 fijo. Cabe destacar que, tomando h=3, obtenemos una caracterización por subgrafos inducidos prohibidos minimales para la clase VPT ∩ EPT = EPT ∩ Cordal=[3,2,2]=[3,2,1]. En el Capítulo 5 damos una nueva condición necesaria para ser un grafo EPT. Para esto nos basamos en la estructura de los cliques de un grafo EPT. Además, encontramos una nueva familia de subgrafos inducidos prohibidos minimales para la clase EPT. En el Capítulo 6 nos enfocamos en los grafos EPT que pueden ser representados en un árbol con grado acotado. Respondemos negativamente una pregunta que Golumbic, Lypshteyn y Stern dejaron abierta, basándonos en la representación EPT que tienen los ciclos de un grafo EPT. Finalmente, en el Capítulo 7, damos algunas conclusiones y analizamos cuáles son los trabajos futuros que nos gustaría realizar.

Esta pesquisa visa a modelagem de clusters de computadores, utilizando um modelo analítico simples que é representado por um grafo valorado denominado grafo da arquitetura. Para ilustrar tal metodologia, exemplificou-se a modelagem do cluster Myrinet/SCI do Instituto de Informática da UFRGS, que é do tipo heterogêneo e multiprocessado. A pesquisa visa também o estudo de métodos e tecnologias de software para o particionamento de grafos de aplicações e seu respectivo mapeamento sobre grafos de arquiteturas. Encontrar boas partições de grafos pode contribuir com a redução da comunicação entre processadores em uma máquina paralela. Para tal, utilizou-se o grafo da aplicação HIDRA, um dos trabalhos do GMCPAD, que modela o transporte de substâncias no Lago Guaíba. Um fator importante é o crescente avanço da oferta de recursos de alto desempenho como os clusters de computadores. Os clusters podem ser homogêneos, quando possuem um arquitetura com nós de mesma característica como: velocidade de processamento, quantidade de memória RAM e possuem a mesma rede de interconexão interligando-os. Eles também podem ser heterogêneos, quando alguns dos componentes dos nós diferem em capacidade ou tecnologia. A tendência é de clusters homogêneos se tornarem em clusters heterogêneos, como conseqüência das expansões e atualizações. Efetuar um particionamento que distribua a carga em clusters heterogêneos de acordo com o poder computacional de cada nó não é uma tarefa fácil, pois nenhum processador deve ficar ocioso e, tampouco, outros devem ficar sobrecarregados Vários métodos de particionamento e mapeamento de grafos foram estudados e três ferramentas (Chaco, Jostle e o Scotch) foram testadas com a aplicação e com a arquitetura modeladas. Foram realizados, ainda, vários experimentos modificando parâmetros de entrada das ferramentas e os resultados foram analisados. Foram considerados melhores resultados aqueles que apresentaram o menor número de corte de arestas, uma vez que esse parâmetro pode representar a comunicação entre os processadores de uma máquina paralela, e executaram o particionamento/mapeamento no menor tempo. O software Chaco e o software Jostle foram eficientes no balanceamento de carga por gerarem partições com praticamente o mesmo tamanho, sendo os resultados adequados para arquiteturas homogêneas. O software Scotch foi o único que permitiu o mapeamento do grafo da aplicação sobre o grafo da arquitetura com fidelidade, destacando-se também por executar particionamento com melhor qualidade e pela execução dos experimentos em um tempo significativamente menor que as outras ferramentas pesquisadas.

Atualmente, a World Wide Web (WWW) já se estabeleceu como um dos meios de divulgação mais difundidos. Sendo um meio de publicação de custo relativamente baixo, muitas iniciativas foram desenvolvidas no sentido de estendê-la e transformá-la também numa ferramenta de apoio. Assim, uma série de pesquisas foi realizada no sentido de promover e facilitar o gerenciamento das informações da WWW, que são estruturadas, em sua maioria, como conjuntos de documentos inter-relacionados. Grafos são estruturas utilizadas para a representação de objetos e seus múltiplos relacionamentos. Nesse sentido, pode-se afirmar que hiperdocumentos podem ser modelados através de grafos, onde uma página representa um nodo e um link para outra página é representado por uma aresta. Considerando estas características, e dada a crescente complexidade dos materiais publicados na WWW, desenvolveu-se, ao longo da última década, o uso de técnicas e recursos de Visualização de Grafos com larga aplicação na visualização da estrutura e da navegação na WWW. Técnicas de visualização de grafos são aplicáveis especificamente para representar visualmente estruturas que possam ser modeladas por meio de objetos relacionados, sendo investigadas técnicas para a abstração de modo a facilitar tanto o processo de compreensão do contexto da informação, quanto a apreensão dos dados relacionados. Este trabalho tem como objetivo a investigação de técnicas de Visualização de Grafos aplicadas a autômatos finitos com saída. Este direcionamento se deve ao fato de alguns autores utilizar a abordagem de autômatos finitos com saída para as estruturas de hiperdocumentos. Se for considerado que um documento da WWW (ou o estado de um autômato) é composto por fragmentos de informação (ou saídas) tais como trechos de texto, imagens, animações, etc e que este documento é relacionado a outros por meio de links (ou transições), tem-se a verificação de sua representatividade por meio destas estruturas. Em trabalho anterior, no âmbito do PPGC da UFRGS, a ferramenta Hyper-Automaton foi desenvolvida com o objetivo de estender o uso da Internet no sentido de prover uma ferramenta de apoio à publicação de materiais instrucionais. Por adotar a notação de autômatos finitos com saída, possibilita, além da criação e gerenciamento de hiperdocumentos, a reutilização de fragmentos de informação sem que haja qualquer interferência de um autômato que utilize este fragmento sobre outro. O Hyper-Automaton foi selecionado como caso de estudo motivador deste trabalho. As técnicas aqui desenvolvidas têm como intuito diminuir a complexidade visual da informação, assim como permitir a navegação através dos autômatos finitos com saída de forma que seja possível visualizar detalhes como as saídas e informações relacionadas a cada uma delas, mantendo a visualização do contexto da informação. Foram analisadas técnicas de agrupamento como forma de redução da complexidade visual, e técnicas do tipo foco+contexto, como alternativa para prover a visualização simultânea do contexto e dos detalhes da informação.

O aumento da escala e funcionalidade dos sistemas de computação e sua crescente complexidade envolvem um aumento significante de custos e exigem recursos humanos altamente qualificados para o desenvolvimento de software. Integrando-se o uso de métodos formais ao desenvolvimento de sistemas complexos, permite-se realizar análises e verificações destes sistemas, garantindo assim sua correção. Existem diversos formalismos que permitem descrever sistemas, cada qual com diferentes níveis de abstração. Quando consideramos sistemas complexos, surge a necessidade de um modelo que forneça construções abstratas que facilitem o entendimento e a especificação destes sistemas. Um modelo baseado em objetos fornece um nível de abstração que tem sido muito aplicado na prática, onde os dados e os processos que os manipulam são descritos juntos em um objeto. Gramática de Grafos Baseada em Objetos (GGBO) é um modelo baseado em objetos, que além de ser uma linguagem visual, apresenta a vantagem de as especificações adquirirem um estilo baseado em objetos, que é bastante familiar à maioria dos desenvolvedores. Porém, as GGBOs não possuem ainda ferramentas para verificação automática de propriedades desejadas nos sistemas modelados. Uma alternativa para resolver isso é definir uma tradução (que preserve a semântica) desta linguagem para outra, para a qual existam verificadores automáticos. Um formalismo bastante conhecido e estabelecido para descrição de sistemas concorrentes, para o qual existem verificadores automáticos, é o cálculo-π. Porém, sob o aspecto de especificação de sistemas complexos, GGBOs parecem ser mais adequadas como linguagem de especificação que o cálculo-π, pois são visuais, mais intuitivas e possuem um estilo baseado em objetos. Neste trabalho foi definido um formalismo (baseado nas GGBOs), denominado Gramática de Hipergrafos Baseada em Objetos e uma tradução deste formalismo para o cálculo-π, aliando assim as vantagens desses dois métodos. Além disso, para validar a tradução definida, foram feitas provas de que a semântica das gramáticas de hipergrafos baseadas em objetos é preservada na tradução.

Submitted by LIVIA FREITAS (livia.freitas@ufba.br) on 2013-10-08T15:47:13Z No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Approved for entry into archive by LIVIA FREITAS(livia.freitas@ufba.br) on 2013-10-08T15:47:22Z (GMT) No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Made available in DSpace on 2013-10-08T15:47:22Z (GMT). No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Arvores Steiner são comumente utilizadas para modelar restrições na execução da operação de multicast. Nesta dissertação nós tratamos um novo problema denominado árvore Steiner com Grau Mínimo e fator de dilatação k em Grafos Direcionados (cujo acrônimo em inglês é DSMDStP). Este problema consiste em: dado um grafo direcionado G(V,E), um n´o origem s ∈ V , um fator de dilatação k (k ∈ R+, k ≥ 1) e um conjunto de terminais T ⊆ V \ {s}, encontrar uma arborescência onde o custo entre o nó de origem s em G e cada t ∈ T é menor ou igual a k vezes o custo da menor distância entre este par de nós, ao passo que o grau máximo de saída é minimizado. DSMDStP não admite aproximação sublogarítmica (a menos que NP ⊂ DTIME(nlog log n). Nós descrevemos um algoritmo de aproximação que gera uma arborescência com grau máximo de saída limitado por 2q|T| + 2 + O(log |T|) · d∗, onde d∗ consiste no grau máximo da solução ótima e a arborescência é uma spanner com fator de dilatação (a partir da raiz) de k ·1 + maxt2T {dist(s,t,G)}mint2T dist(s,t,G)}, onde dist(s, t,G) representa o caminho de menor custo entre s e t em G. Embora nosso fator de dilata¸c˜ao viole k, nos experimentos, a restrição de spanner foi satisfeita ou, em média, quase satisfeita. Além disso, o grau de saída medido nos experimentos foi baixo. Nós também descrevemos uma heurística que garante um fator de dilatação de k · (⌊q|T|⌋ + 2), mas não limita o grau máximo de saída. Nos experimentos, a heurística mostrou-se extensível com relação ao grau máximo, além de sempre superar os outros algoritmos nesta métrica. A heurística gerou, adicionalmente, uma spanner com fator de violaçãao baixo. / Salvador

Associadas a um grafo G, temos a matriz de adjacência A(G) e a matriz laplaciana L(G). Este trabalho descreve algumas propriedades dessas matrizes e de seus autovalores em relação a características estruturais do grafo. Veremos que, em geral, somente o espectro de G, isto é, conjunto de autovalores de A(G), não é capaz de revelar todas as informações a respeito do grafo. Apresentaremos também uma nova cota superior para a soma dos k maiores autovalores laplacianos de uma árvore com n vértices, para k {1, . . . , ng}. Esse limite nos permitirá demonstrar que, dentre todas as árvores de n vértices, a árvore com energia laplaciana máxima é a estrela Sn, o que foi conjecturado por Radenkovi¢ e Gutman [18]. / Associated with a graph G, we have the adjacency matrix A(G) and the Laplacian matrix L(G). This work relates properties of these matrices and their eigenvalues to structural characteristics of the graph. We will see that, in general, the spectrum of G, namely the set of eigenvalues of A(G), does not reveal all the information about the graph. We will also present a new upper bound on the sum of the k largest Laplacian eigenvalues of a tree with n vertices, where k {1, . . . , ng}. This result is used to establish that the n-vertex star Sn has the highest Laplacian energy over all n-vertex trees, which answers a rmatively to a question raised by Radenkovi¢ and Gutman [18].

Dissertação (mestrado profissional) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas, Programa de Pós-Graduação em Matemática, Florianópolis, 2017. / Made available in DSpace on 2018-02-13T03:09:45Z (GMT). No. of bitstreams: 1 349816.pdf: 1651899 bytes, checksum: 9dc7a5c2aff28a0457dfc5d52fe8e2af (MD5) Previous issue date: 2017 / Este trabalho tem por objetivo apresentar um pouco da Teoria de Grafos para, com isto, termos uma fundamentação teórica que mostrará a viabilidade da aplicação no Ensino Médio, em destaque o Algoritmo de Dijkstra, onde o educando poderá modelar situações problemas num grafo, para obtenção do caminho mais curto. Este algoritmo tem uma vasta aplicação em diversas áreas do conhecimento, em especial na área de tecnologia, como por exemplo, em redes de comunicação. Proporcionando assim, uma oportunidade única de aplicações em problemas reais, atuais e do interesse do educando. Não só estudamos a questão do caminho mais curto, mas também consideramos o problema da conexidade em grafos e a existência de caminhos disjuntos, demonstrando o famoso teorema de Menger. Por exemplo, no caso de uma rede de comunicação é interessante saber qual é o ponto vulnerável do sistema e verificar a existência de um caminho alternativo, caso um destes pontos venha a falhar, uma aplicação imediata do Teorema de Menger. / Abstract : We give a brief presentation of Graph Theory in a way that a student without any knowledge in graphs can learn the basic definitions, examples and properties and can apply these in a real life situation. In particular, we study the Dijkstra algorithm, where the student can apply this algorithm to find the shortest path between nodes in a graph. This algorithm has a lot of real life applications, especially in technology such as paths in a network communication. This gives a unique opportunity of solving current real problems. Not only we study the problem of finding the shortest path, we also consider the problem of connectedness in a graph and the existence of different paths which do not intersect, proving the famous Menger's Theorem. For instance, in the case of a network communication, it is interesting to know the problem points where the system is vulnerable and of one these points fail, one can try to verify the existence of an alternative path, an immediate application of Menger's Theorem.

ARAUJO, Samuel Nascimento de. Número de dominação romana em grafos. 2016. 51 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Anderson Silva Pereira (anderson.pereiraaa@gmail.com) on 2017-01-25T17:42:43Z No. of bitstreams: 1 2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2017-01-26T20:23:42Z (GMT) No. of bitstreams: 1 2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5) / Made available in DSpace on 2017-01-26T20:23:42Z (GMT). No. of bitstreams: 1 2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5) Previous issue date: 2016 / In a Roman domination of a graph, vertices are assigned a value from {0,1,2} in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment. In this dissertation, we show the history of the problem and prove that the Roman domination number is NP-Complete even for induced subgraphs of grids and it is APX-hard even for bipartite graphs with maximum degree 4. We also prove that the Roman domination number is fixed parameter tractable for graphs with bounded local treewidth, as graphs with bounded maximum degree or bounded genus (like planar graphs or toroidal graphs). We also obtain complexity results when we consider digraphs as an input for the problem such as bipartite tournaments and planar digraphs. / No problema de dominação romana de um grafo, os vértices são atribuídos um valor de {0,1,2}, de tal maneira que cada vértice atribuído o valor 0 é adjacente a um vértice que foi atribuído o valor 2. O número de dominação romana é a menor soma possível de todos os valores dos vértices em tal atribuição. Nesta dissertação apresentamos a história do problema, e provamos que o número dominação romana é NP-Completo mesmo para subgrafos induzidos de grids e é APX-difícil mesmo para grafos bipartidos com o grau máximo 4. Nós também provamos que o número de dominação romana é tratável por parâmetro fixo para grafos com treewidth local limitada, como grafos com grau máximo limitado ou genus limitado (como por exemplo grafos planares). Nós também obtivemos resultados de complexidade quando consideramos digrafos como entrada para o problema, tais como torneios bipartidos e digrafos planares.