Orientador: Tânia Baier. / Com.: Produto educacional: Caderno do estudante: Teoria dos grafos para o ensino fundamental: desafios lúdicos. / Dissertação (Mestrado em Matemática) - Universidade Regional de Blumenau, Centro de Ciências Exatas e Naturais, Programa de Pós-Graduação em Ensino de Ciências Naturais e Matemática, Blumenau,

Orientador: Mauro de Souza Ventura / Caroline Kraus Luvizotto / Alan Cesar Belo Angeluci / Resumo: A mudança na relação que o espectador estabelece com os veículos de comunicação e que o jornalista determina com a própria profissão depois do surgimento da conexão sem fio com a Internet e dos sites de redes sociais online são o ponto de partida deste estudo. Para investigar esse novo cenário, toma-se como objeto o veículo brasileiro Catraca Livre, que publica matérias produzidas por sua redação e complementa seu conteúdo com o auxílio de uma rede de colaboradores. Apoiados nos conceitos de sociedade em rede, cultura participativa e curadoria, entende-se que o espectador deixa de ser passivo e se torna produser, bem como o jornalista abandona o posto de gatekeeper e assume a função de curador. E, repensando a recepção e definindo-a agora como disseminação, este estudo investiga como se desenha a rede centrada na fanpage da Catraca Livre, com o auxílio da Teoria dos Grafos e de métricas de nós e rede, para entender de que maneira as informações publicadas pelo perfil da Catraca Livre no Facebook circulam através das conexões estabelecidas entre os diversos nós, tornando a sua fanpage um recurso técnico de spreadable media - para, assim, apontar que o modelo de negócio proposto pelo site é viável e adaptado à sociedade em rede; o jornalista assume a função de curador, mas não abandona seus afazeres tradicionais; e, apesar de ainda explorar pouco o seu potencial nas RSO, a Catraca Livre consegue disseminar seu conteúdo na rede. / Abstract: The change in the relationship between the public and the media and also between the journalist and its own profession after the emergence of the wireless connection to the Internet and the online social networking sites are the starting point of this study. To investigate this new scenario, we take as object the Brazilian vehicle Catraca Livre, which publishes material produced by its journalists and complements its content with the help of a network of collaborators. Based on the concepts of network society, participatory culture and curation, we understand that the public stops being passive and becomes a produser, and also the journalist leaves the position of gatekeeper and assumes the role of curator. And, rethinking the reception and defining it now as a dissemination, we investigate how the network centered on the fanpage of Catraca Livre, with the help of Graph Theory and node and network metrics, in order to understand how the information published by Catraca Livre profile on Facebook circulate through the connections established among the various nodes, making the vehicle fanpage a technical resource of spreadable media. At the end, we point out that the business model proposed by the site is viable and adapted to the networked society; the journalist assumes the role of curator, but does not abandon his traditional duties; and although its potential in RSO is still poorly explored, Catraca Livre is able to disseminate its content in the network. / Mestre

Orientador: Candido Ferreira Xavier de Mendonça Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-11-01T11:47:37Z (GMT). No. of bitstreams: 1 Nascimento_HugoAlexandreDantasdo_M.pdf: 3105105 bytes, checksum: 1db649275d731767fbcb044c4fb5008c (MD5) Previous issue date: 1997 / Resumo: Desenho de Grafos é uma área recente que trata do desenvolvimento de técnicas e de algoritmos para construir representações geométricas de grafos, atendendo, em geral, a critérios estéticos. A atividade de desenhar grafos implica em muitas dificuldades; entre elas, verificamos que a satisfação de alguns critérios estéticos envolve freqüentemente problemas NP-difíceis e que, em muitos casos, os critérios são conflitantes entre si. Em função disso, heurísticas têm sido desenvolvidas e amplamente utilizadas para obter bons desenhos. No presente trabalho, descrevemos uma nova abordagem para desenhar grafos, que se baseia na combinação de heurísticas utilizando um tipo de organização de agentes conhecido como Time Assíncrono. A abordagem é capaz de produzir desenhos melhores do que as heurísticas isoladas, e é flexível pois pode ser aplicada para trabalhar com muitos critérios estéticos e com várias classes de grafos / Abstract: Graph Drawing is a new area that deals with the development of techniques and algorithms whose major concern is the geometric representations of graphs. These geometric representations must follow a set of aesthetic criteria in a "nice" way. The activity of drawing graphs run into many dificulties, for example: the problem of satisfying some aesthetic criteria is often NP-hard and, in mostcases, there are some conflitcs among the criteria. This justifies the wide use of heuristics to produce good drawings. In this work we show a new approach to draw graphs. This approach focuses on the combination of different heuristics in a specific organization of agents, called Asynchronous Team. The approach achieves better drawings than the heuristics alone, and it can be applied to work with severa! aesthetic criteria for drawing many classes of graphs / Mestrado / Mestre em Ciência da Computação

Contém uma errata / Tese de Mestrado. Inteligência Artificial e Sistemas Inteligentes. Faculdade de Engenharia. Universidade do Porto, Faculdade de Economia. Universidade do Porto. 2007

Made available in DSpace on 2013-08-07T18:43:16Z (GMT). No. of bitstreams: 1 000397342-Texto+Completo-0.pdf: 6244320 bytes, checksum: 1ad9082d42e6883bb7678a8782a81d49 (MD5) Previous issue date: 2007 / During parallel applications development, besides analysis regarding performance aspects, it is also important to analyze the system's functional properties to assure, for example, that the parallel strategy chosen is adequate for the problem being approached, or that it may converge to an expected result, or even to identify the possibility of a deadlock scenario. The correction guarantee over a parallel application model, besides improving the results reliability, also can be an economic factor, since it allows to reduce the time consumed for the application development and debugging. However, once identi ed the problems and corrections into the model analyzed, there is still the need to map the changes needed to the original application. In this sense, modelchecking and automatic code generation can be used as complementary tools during development, allowing the system behavior analysis and a fast generation of the model's corresponding code. This work presents the use of Object-Based Graph Grammars (OBGG) for parallel applications development, through the de nition of a method to translate OBGG models to C code, using MPI as communication platform. / No desenvolvimento de aplicações paralelas, além da análise de aspectos ligados ao desempenho, torna-se também importante a análise das propriedades funcionais do sistema para garantir, por exemplo, que a estratégia de paralelização escolhida é adequada ao problema sendo abordado, ou que ela pode convergir para um resultado esperado, ou mesmo para identificar a possibilidade de um cenário de bloqueio na computação. A garantia de correção sobre o modelo de uma aplicação paralela, além de aumentar o grau de confiança nos resultados, pode também ser um fator de economia, já que possibilita a redução no tempo despendido no desenvolvimento e depuração da aplicação. Porém, uma vez identificados os problemas e correções no modelo analisado, ainda existe a necessidade de se mapear as mudanças necessárias à aplicação original. Nesse sentido, verificação formal e geração automática de código podem ser utilizadas como ferramentas complementares durante o desenvolvimento, possibilitando tanto a análise do comportamento do sistema quanto a rápida geração do código correspondente ao modelo proposto. Este trabalho apresenta o uso de Gramática de Grafos Baseada em Objetos (GGBO) para a construção de aplicações paralelas, a partir da definição de um método de tradução de modelos GGBO para código C, utilizando MPI como plataforma de comunicação.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2015. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-06-14T16:45:15Z No. of bitstreams: 1 2015_RebecaChuffiSaccochi.pdf: 2226603 bytes, checksum: 275216e3b040d9494ba5dc90e65922d1 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2017-01-18T20:09:53Z (GMT) No. of bitstreams: 1 2015_RebecaChuffiSaccochi.pdf: 2226603 bytes, checksum: 275216e3b040d9494ba5dc90e65922d1 (MD5) / Made available in DSpace on 2017-01-18T20:09:53Z (GMT). No. of bitstreams: 1 2015_RebecaChuffiSaccochi.pdf: 2226603 bytes, checksum: 275216e3b040d9494ba5dc90e65922d1 (MD5) / Um grupo G é dito central-por-finito se o índice do centro [G:Z(G)] é finito. É possível caracterizar a classe dos grupos central-por-finito de várias maneiras. Uma dessas, devida a R. Baer, assegura que um grupo é central-por-finito se, e somente se ele admite uma cobertura finita por subgrupos abelianos. A partir de um problema de teoria dos grafos proposto por Paul Erdös, B. H. Neumann caracterizou os grupos central-por-finito de outra maneira, assegurando que um grupo é central-por-finito se, e somente se ele é um PE-grupo, isto é, um grupo cujo grafo não-comutativo Г(G)não possui subgrafos completos infinitos. Essas duas caracterizações levam a considerar, de maneira natural, três indicadores numéricos relacionados a um grupo central por finito. Primeiro, [G:Z(G)], o índice do centro, segundo, a(G), o número mínimo de subgrupos abelianos necessários para cobrir o grupo G de forma irredundante, e terceiro, ω(G), o tamanho do maior subgrafo completo de Г(G), isto é, o tamanho do maior clique do grafo Г(G). Um problema interessante então é relacionar essas três quantidades, encontrando cotas de uma em função de outra e também determinar condições sob as quais valem as igualdades. Em geral, dado G um grupo central-por-finito, sempre temos que ω(G) ≤ a(G) ≤ [G:Z(G)] ≤c^ω(G) , onde c é uma constante. Além disso, quando G é finito, é natural relacionar os indicadores [G:Z(G)], a(G) e ω(G)não só entre eles, mas também com a ordem de G. Portanto, neste trabalho vamos estudar as duas caracterizações de grupos central-por-finito mencionadas anteriormente, relacionar os três indicadores numéricos ω(G), a(G) e [G:Z(G)] e apresentar vários exemplos, entre eles a família de grupos extraespeciais de ordemp^(2n+1). / A group G is said to be central-by-finite if the index of the center [G:Z(G)] is finite. It is possible to characterize the class of central-by-finite groups in many ways. One of them, due to R. Baer, guarantees that a group G is central-by-finite if and only if G can be covered by finitely many abelian subgroups. Motivated by a question on graph theory proposed by Paul Erdös, B. H. Neumann has characterized central-by-finite groups in a different way, ensuring that a group G is central-by-finite if and only if G is a PE-group, that is, a group whose non-commuting graph Г(G) contains no infinite complete subgraph. Both characterizations lead us to consider, in a natural manner, three numerical indicators related to a central-by-finite group. First, [G:Z(G)], the index of the center, second, a(G), the minimum number of abelian subgroups necessary to cover the group G in an irredundant way, and finally, ω(G), the size of the biggest complete subgraph of Г(G), that is, the size of the biggest clique of Г(G). It is interesting, then, to relate those three quantities, finding bounds of one in function of the other and also determining conditions under which equalities hold. In general, for a central-by-finite group G we have that ω(G) ≤ a(G) ≤ [G:Z(G)] ≤c^ω(G) , where c is a constant. Besides that, when G is finite, it is natural to relate the indicators [G:Z(G)], a(G) e ω(G)not only with each other, but also with the order of G. Therefore, in this essay we are going to study the two characterizations mentioned above, relate the three numerical indicators ω(G), a(G) and [G:Z(G)], and present many examples, among them, the class of extraspecial p-groups of order p^(2n+1).

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-08-30T17:24:15Z No. of bitstreams: 1 texto completo.pdf: 4232344 bytes, checksum: 570158c74aae3b6b7b1e909cc8bc8bce (MD5) / Made available in DSpace on 2016-08-30T17:24:15Z (GMT). No. of bitstreams: 1 texto completo.pdf: 4232344 bytes, checksum: 570158c74aae3b6b7b1e909cc8bc8bce (MD5) Previous issue date: 2015-08-28 / Um tema de estudo do ensino médio ́e a relação entre os números de vértices, arestas e faces, para poliedros convexos regulares, conhecida como Teorema de Euler. No caso geral esta relação ́e conhecida como característica de Euler. Neste trabalho apresentaremos exemplos de poliedros não convexos que satisfazem o Teorema de Euler e algumas formas de calcular a característica de Euler para poliedros no caso em geral, com o objetivo de fornecer um material mais acessível para professores que trabalham com este tema. / One topic of study in the high school is the relation between the number of vertices, the number of edges and the number of faces, for regular convex polyedra, known as Euler’s theorem. In the general case this relationsship is known as Euler characteristic. In this paper we present examples of non-convex polyhedrons which satisfies the Euler’s Theorem. We present some ways to computer the Euler characteristic to polyhedrons in the general case.

O objetivo principal deste trabalho é apresentar uma. descrição detalhada sobre as diversas abordagens do Problema do Caixeiro Viajante, a complexidade na sua resolução e as aplicações nas diversas áreas do conhecimento. O Problema do Caixeiro Viajante é um dos mais conhecidos e estudados problemas da Teoria dos Grafos e sua importância é tanta teórica quanto prática. O resultado teórico mais importante que apresentamos neste trabalho é a prova de que o PCV é -P-Completo, usando (e provando) o Teorema de Cook, como ponto de partida e a Máquina de Turing como o modelo computacional para as provas da complexidade dos problemas envolvidos. O PCV é equivalente ao problema de encontrar um circuito Hamiltoniano de peso mínimo em um grafo ponderado. Uma das questões principais envolvidas neste problema, e na verdade uma das principais indagações da Ciência da Comput ação, é saber se existe um algoritmo eficiente de tempo polinomial para calcular tal circuito, ou se tal algoritmo não existe, caracterizando-o, assim, como um problema impossível de ser resolvido. Quando não se pode encontrar uma solução eficiente para um dado problema e também não pode ser demonstrado que tal solução existe, deve-se usar técnicas que permitam construir um algoritmo que forneça soluções aproximadas. Neste trabalho, apresentamos um algoritmo de tempo polinomial que nos fornece soluções aproximadas para o PCV. / The main objective of this work is to present a detailed description on the various approaches to the Traveling Salesperson Problem (TSP), the complexity of its solution and its applications to the various knowledge area.s. The Traveling Salesperson Problem is one of the most known and studied problems in graph theory and its importance is theoretical as well as practical. The theory result more important who we will introduce in this work is the proof of the TSP is NP-complete, using (and proving) of Cook's Theorem like point of departure and the Turing Machine like the model computational for the tests of complexity of problems involved. The TSP is equivalent to the problem of finding a Hamiltonian circuit of minimal weight in a weighted graph. One of the main questions involved in this problem, and actually one of the main questions of the whole Computing Science, is to know if there exists an polynomial-time efficient algorithm to compute such a circuit, or if such an algorithm can not exist, then characterizing it as an impossible problem. When one can not find an efficient solution for a given problem and also can not show that such a solution exists, we must use techniques that aid us to construct an algorithm providing approximate solutions. In this work, we will present a polynomial-time algorithm that gives approximate solutions for the solution of the Traveling Salesperson Problem.

Freitas, L. I. B. A conjectura de Tuza sobre triângulos em grafos. 2014. 83 f. Dissertação (Mestrado Ciência da Computação) - Instituto de Computação, Universidade Estadual de Campinas, Campinas, 2014. / Submitted by Juliana Almeida (julianaufc@gmail.com) on 2014-10-30T18:26:55Z No. of bitstreams: 1 2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) / Approved for entry into archive by Juliana Almeida(julianaufc@gmail.com) on 2014-10-30T18:28:27Z (GMT) No. of bitstreams: 1 2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) / Made available in DSpace on 2014-10-30T18:28:27Z (GMT). No. of bitstreams: 1 2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) Previous issue date: 2014 / In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza’s conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K5 minor. / Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação¸ nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contraexemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K5.

SOARES, R. P. Jogos de perseguição-evasão, decomposições e convexidade em grafos. 2013. 206 f. (Doutorado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T18:11:52Z No. of bitstreams: 1 2013_tese_rpsoares.pdf: 1865132 bytes, checksum: e9214578093ec3c62c3eee11e731fdc6 (MD5) / Approved for entry into archive by José Jairo Viana de Sousa(jairo@ufc.br) on 2015-11-25T13:04:50Z (GMT) No. of bitstreams: 1 2013_tese_rpsoares.pdf: 1865132 bytes, checksum: e9214578093ec3c62c3eee11e731fdc6 (MD5) / Made available in DSpace on 2015-11-25T13:04:50Z (GMT). No. of bitstreams: 1 2013_tese_rpsoares.pdf: 1865132 bytes, checksum: e9214578093ec3c62c3eee11e731fdc6 (MD5) Previous issue date: 2013 / Esta tese é centrada no estudo de propriedades estruturais de grafos cujas compressões permitem a concepção de algoritmos eficientes para resolver problemas de otimização. Estamos particularmente interessados em decomposições, em jogos de perseguição-evasão e em convexidade. O jogo de Processo foi definido como um modelo para a reconfiguração de roteamento em redes WDM. Muitas vezes, jogos de perseguição-evasão, em que uma equipe de agentes tem como objetivo limpar um grafo não direcionado, estão intimamente relacionados com decomposições em grafos. No caso de grafos direcionados, mostramos que o jogo de Processo é monotônico e definimos uma nova decomposição em grafos equivalente a tal jogo. A partir de então, investigamos outras decomposições em grafos. Propomos um algoritmo FPT para calcular vários parâmetros de largura em grafos. Em particular, este é o primeiro algoritmo FPT para calcular a largura em árvore especial e a largura em árvore q-ramificada de um grafo. Em seguida, estudamos um outro jogo perseguição-evasão que modela problemas de pré-obtenção. Nós introduzimos uma versão mais realista do jogo de Vigilância a versão on-line. Estudamos a diferença entre o jogo de Vigilância clássico e suas versões conectadas e on-line, fornecendo novos limites para essa diferença. Nós, então, definimos um modelo geral para o estudo de jogos perseguição-evasão, com base em técnicas de programação linear. Este método permite-nos dar os primeiros resultados de aproximação para alguns desses jogos. Finalmente, estudamos outro parâmetro relacionado com a convexidade e a propagação da infecção em redes, o “hull number”. Nós fornecemos vários resultados de complexidade computacional, dependendo das propriedades estruturais do grafo de entrada e usando decomposições em grafos. Alguns destes resultados respondem problemas em aberto na literatura.