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, 2015. / Made available in DSpace on 2016-10-19T13:16:17Z (GMT). No. of bitstreams: 1 338254.pdf: 521472 bytes, checksum: 0de8b7f4b116405482ddf4f65b71477c (MD5) Previous issue date: 2015 / Dados um corpo K e o grafo dirigido E, definido por (E 0, E 1, r, s), em que r e s são funções aplicadas nas arestas de E, vamos definir as K-Álgebras de Caminhos e as K-Álgebras de Caminhos de Leavitt do grafo E, que denotaremos respectivamente por A(E) e L_K(E), como as K-álgebras geradas a partir dos conjuntos de arestas e vértices do grafo E, e com relações que serão definidas neste trabalho. Iremos mostrar exemplos de grafos que geram Álgebras de Caminhos e Álgebras de Caminhos de Leavitt isomorfas a estruturas matemáticas já conhecidas, de forma a entender melhor como se comportam estas álgebras. Além disso, iremos provar resultados destas álgebras que são obtidos através de informações do grafo E. O principal resultado que iremos verificar neste trabalho diz como o grafo E pode implicar nas Álgebras de Caminhos de Leavitt serem simples, ou não.<br> / Abstract : Given K a field and the directed graph E, defined by (E 0,E 1,r,s), such that r and s are functions applied to the edges of E, we'll define the Path K-Algebras and the Leavitt Path K-Algebras of the graph E, that we are going to respectively call A(E) and L_K(E), as the K-algebras generated by the sets of edges and vertices of E, with relations that will be defined in this work. We'll be seeing examples of graphs that generate Path Algebras and Leavitt Path Algebras that are isomorphic to mathematical structures already known, as a way of better understanding how these algebras work. Furthermore, we'll be proving results of these algebras based on informations obtained from the graph E. The main result that we are going to prove here show us how the graph E can make the Leavitt Path Algebra be simple or not.

Orientador : André Luís Vignatti / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 28/07/2016 / Inclui referências : f. 41-42 / Área de concentração: Ciência da computação / Resumo: As redes sociais são uma maneira de descrever as interações sociais em um grupo ou comunidade. Podem ser modeladas por meio de grafos, em que um vértice corresponde a uma pessoa, e uma aresta representa alguma forma de associação entre duas pessoas [Hasan e Zaki, 2011]. As redes sociais são objetos altamente dinâmicos, elas crescem e mudam rapidamente ao longo do tempo devido à adição e exclusão de vértices e arestas. Compreender os mecanismos pelos quais estas estruturas sociais evoluem é uma questão fundamental, ainda não bem compreendida, e que constitui a motivação para este projeto. Mais especificamente, a pesquisa se dedica ao problema da predição de laços sociais: dado um snapshot de uma rede social em tempo t0, busca-se prever com precisão as arestas que serão adicionados à rede em um determinado momento t futuro, tal que t > t0 [Liben-Nowell, 2005]. As soluções estudadas se dividem em dois grupos principais: predição de laço supervisionada e a predição de laço não supervisionada. A predição de laço supervisionada envolve técnicas de aprendizado de máquina como a extração de características e algoritmos de classificação [Zhang e Yu, 2011]. A predição não supervisionada busca de calcular métricas baseadas nas características topológicas do grafo [Hasan e Zaki, 2011]. Com base no segundo paradigma, e a partir do estudo de modelos de geração de grafos, é proposta como contribuição uma métrica para calcular a probabilidade de formação de arestas entre dois vértices específica para grafos com distribuição de grau Lei de Potência. Palavras-chave: redes sociais, predição de laço, modelo de geração de grafo. / Abstract: Social networks are a popular way to model the interactions among people in a group or community. They can be visualized as graphs, where a vertex corresponds to a person in some group and an edge represents some form of association between the corresponding persons [Hasan e Zaki, 2011]. Social networks are very dynamic, since new edges and vertices are added to the graph over time. Understanding the dynamics that drive the evolution of social networks is a complex problem, yet to be fully understood, and which comprises the motivation of this project. A basic computational problem underlying social-network evolution is the linkprediction problem: given a snapshot of a social network at time t, we seek to accurately predict the edges that will be added to the network during the interval from time t to a given future time t0, considering t > t0 [Liben-Nowell, 2005]. Most works in this field branch into two main groups: supervised and unsupervised link prediction. Supervised link prediction models have two important components: feature extraction and classification [Zhang e Yu, 2011]. Unsupervised link prediction calculates metrics based on features which are extracted from the graph topology, some works develop a graph evolution model [Hasan e Zaki, 2011]. Based on unsupervised link prediction concepts, mainly on graph generation models, we propose a link prediction metric, which is specific to power-law graphs. Keywords: social networks, link prediction, graph generation model.

Orientador : Prof. Dr. Renato José da Silva Carmo / Coorientador : Prof. Dr. André Luís Vignatti / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 20/05/2016 / Inclui referências : f. 63-65 / Resumo: O problema de maximização de influência em redes sociais, procura pelos vértices que permitam espalhar uma informação para o maior número possível de membros da rede.Um algoritmo guloso proposto por Kempe et al. [19], que escolhe iterativamente os vértices de maior influência, encontra um conjunto resposta cujo alcance da influência é pelo menos1 ? 1/e do ótimo. Mas esta abordagem possui alguns agravantes que comprometem o tempo de execução do algoritmo. Nesta dissertação propomos uma melhoria para o algoritmo guloso de Kempe et al. [19] com foco no tempo de execução deste sobre grafos de lei de potência. A melhoria consiste em fazer uma seleção prévia dos vértices mais promissores. Verificamos por meio de análise experimental que esta pré-seleção reduz expressivamente o tempo de execução, além de manter a qualidade da solução compatível com a do algoritmo guloso de Kempe et al. [19]. A otimização por pré-seleção utiliza propriedades presentes em grafos de lei de potência, explorando a relação de influência social com a distribuição de graus. Esta abordagem reduz em até 58%o tempo de execução do algoritmo Celf [22], que é uma das otimizações mais conhecidas do procedimento deKempe et al. [19]. / Abstract: The influence maximization problem in social networks, asks for the nodes that allow tospread a information for the highest number of members. A greedy algorithm proposed byKempe et al. [19], that choose iteratively the members of greatest influence, find a solutionset whose the reach of influence is at least 1?1/e of the optimum. But some aggravatinghave affecting the runtime of this approach. In this work we propose improvements forthe algorithm of Kempe et al. [19], with focus on the runtime in power law graphs. Theimprovement consists in make a previous selection of most promising nodes. We haveverified by experimental analysis that this pre selection reduces significantly the runtime,in addition maintaining a quality compatible with the greedy algorithm of Kempe etal. [19]. The optimization by pre selection uses properties present in power law graphs,by exploring the relationship between social influence and the degree distribution. Besides,this approach reduces the runtime of Celf [22] algorithm by up to 58%, which is one ofthe most known optimizations of the algorithm of Kempe et al. [19].

Resumo

Orientador : Prof. Dr. Renato José da Silva Carmo / Coorientador : Prof. Dr. André Luís Vignatti / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 26/02/2016 / Inclui referências : f. 55-57 / Resumo: A teoria dos grafos é um ramo da matemática utilizada para modelar e representar um conjunto de elementos e suas relações, além de ser muito utilizada na resolução de problemas computacionais. Um grafo pode representar diversos sistemas naturais e digitais como ligações proteicas, redes sociais, conexões digitais, entre outras. Essas redes contêm diversas características, uma dessas é a distribuição de grau dos vértices. Muitos grafos do mundo real apresentam em sua estrutura uma distribuição de grau que segue uma lei de potência (Power Law), o que informalmente significa que existem poucos vértices de grau elevado, enquanto muitos vértices apresentam grau baixo. Dentro dos problemas clássicos algorítmicos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos e que pertencem à classe NP-Difícil, especificamente o problema da cobertura por vértices mínima em grafos que apresentam uma distribuição de grau lei de potência. Assim, é apresentado neste trabalho um método inspirado em regras de redução ao núcleo do problema. Os resultados obtidos sugerem ser uma boa heurística de aproximação da solução _ótima, além de reduzir significativamente o tempo computacional na resolução do problema da cobertura por vértices. Palavras-chave: Grafos, Cobertura por Vértices, Regras de redução, Lei de Potência. / Abstract: Graph theory is a branch of mathematics used to model and represent a set of elements and their relationships, which is also often used to solve computational problems. A graph can represent various natural and digital systems, such as: protein binding, social networks, digital connections, among others. Those networks contain diverse characteristics, which one of these is the degree of the distribution of the vertices. Many graphs of the real world have in their structure a degree of distribution following a power-law, where informally means that there are few high degree vertices, while many other vertices have a low degree. Within the algorithmic classic problems, we are interested in computationally difficult problems to be solved and which belong to the NP-Hard class, specifically the problem of minimum vertex cover in graphs, that have a power-law degree distribution. Thus, this work presents a method based on reduction rules to the core of the problem. The achieved results indicate that it is a good approximation heuristic from the optimal solution, in addition to be a technique that a significantly reduces on the computational time to solve the problem of minimum vertex cover. Keywords: Graph, Vertex Cover, reduction rules, Power Law.

Orientador : Prof. Dr. Renato Carmo / Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 28/09/2017 / Inclui referências : f. 107-113 / Resumo: O problema da Clique Máxima (CM) é um problema fundamental e há uma grande motivação pela busca de algoritmos tão eficientes quanto possível para resolvê-lo de forma exata. Como esperado para um problema NP-difícil, os melhores algoritmos com desempenho de pior caso conhecido tem custo de tempo exponencial. Por outro lado, resultados experimentais encontrados na literatura indicam que instâncias de tamanho considerável podem ser resolvidas usando algoritmos baseados na técnica de branch-and-bound. Com isso, observa-se uma distância entre os melhores resultados analíticos e os melhores resultados experimentais. Uma possível explicação para discrepância aparente entre teoria e prática foi encontrada pela análise de instâncias aleatórias. Diversos algoritmos de branch- and-bound para a solução exata do CM foram estudados, analisados e implementados. Com base nos resultados analíticos é proposta uma metodologia para comparação experimental de algoritmos, que tem como principal ponto positivo o fato de que algoritmos podem ser comparados independente de detalhes de implementação e execução. Vários algoritmos foram testados como prova de conceito. Também foram estudadas instâncias de pior caso para algoritmos de branch-and-bound que só utilizam coloração como limitante superior, resultando em um custo exponencial de tempo para estes algoritmos. Uma nova família de algoritmos foi desenvolvida, capaz de resolver tais instâncias em tempo polinomial. Recentemente, técnicas de resolvedores para problemas de satisfatibilidade têm sido aplicadas em algoritmos para CM. Tais técnicas dependem de uma redução entre os dois problemas, mas o significado em termos do grafo fica obscurecido nas descrições originais. Algumas técnicas foram estudadas e convertidas para uma descrição que não usa termos referentes aos problemas de satisfatibilidade. A implementação de vários algoritmos estudados foi disponibilizada em um repositório de acesso público. Palavras-chave: Solução exata. Branch-and-bound. Análise de algoritmos. Comparação experimental. / Abstract: e Maximum Clique problem (CM) is a fundamental problem and there is a great motivation for the development of efficient exact algorithms to solve it. As expected for a NP-hard problem, the best algorithms where worst case analyses have been conducted present exponential running times. On the other hand, experimental results available in the literature show that instances of considerable size can be solved by branch and bound algorithms. Therefore, there is an apparent gap between the best theoretical results and the best experimental results. One possible explanation for this discrepancy between theory and practice was found through the analyses of random instances. Several exact branch and bound algorithm for CM were studied, analyzed and implemented. Based on these analytical results, a new methodology for the comparison of algorithms is proposed, where algorithms can be tested and compared regardless of implementation and execution details. Several algorithms were tested as a proof of concept. Worst case instances for some branch and bound algorithms were studied, namely algorithms that adopt only coloring-based bounding techniques to reduce the search space. These algorithms present exponential time cost for the studied instances. A new family of algorithms was developed, which is able to solve the mentioned instances in polinomial time. Recently, techniques from satisfiability solvers have been used in algorithms for CM. Such techniques depend on a reduction between the problems, and the original descriptions in terms of propositional calculus obscures their graph theoretic meaning. Some of these techniques were studied and converted to a description that uses only graph theory terminology. The implementation of several algorithms was made available in a public access repository. Keywords: Exact solution. Branch-and-bound. Analysis of algorithms. Experimental comparison.

Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-11-04T14:09:27Z No. of bitstreams: 2 arquivototal.pdf: 817270 bytes, checksum: ba2aa7837f218549769442c49a92611c (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Maria Suzana Diniz (msuzanad@hotmail.com) on 2015-11-05T11:26:40Z (GMT) No. of bitstreams: 2 arquivototal.pdf: 817270 bytes, checksum: ba2aa7837f218549769442c49a92611c (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-11-05T11:26:40Z (GMT). No. of bitstreams: 2 arquivototal.pdf: 817270 bytes, checksum: ba2aa7837f218549769442c49a92611c (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-08-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This paper presents an introductory study of graph theory, considering its relevance to the teaching of mathematics. Initially presents a brief history on Graph Theory. Then the rst chapter consists of some de nitions on graphs and examples, the second chapter deals with the paths, walks and cycles in a graph, highlighting the Eulerian tours and Hamiltonian cycles, also boarded a special type of graphs, trees . In Chapter 3 we address the planarity in graphs, thus presenting Euler's Formula. Finally in Chapter 4 we present some problems involving graphs. / Este trabalho apresenta um estudo introdutório sobre Teoria dos Grafos, considerando sua relevância para o ensino da Matemática. Inicialmente é apresentado um breve histórico sobre a Teoria dos Grafos. Em seguida, o capítulo 1 é constituído por algumas defi nições sobre grafos e exemplos, o capítulo 2 trata dos caminhos, passeios e ciclos num grafo, destacando-se os passeios Eulerianos e os ciclos Hamiltonianos, abordamos também um tipo especial de grafos, as árvores. No capitulo 3 abordamos a planaridade nos grafos, apresentando assim a Fórmula de Euler. Finalmente no capítulo 4 apresentamos alguns problemas envolvendo grafos.

O objetivo principal deste trabalho é tratar as implicações geométricas e topológicas da planaridade, destacando a influência desse conceito em problemas geométricos fundamentais. Tais problemas são derivados da fórmula de Euler e suas diversas aplicações. Também problemas topológicos, como o problema de coloração de mapas, são estudados na dissertação. A teoria de grafos tem extensiva utilização em matemática aplicada, pois demonstra ser uma poderosa ferramenta para a modelagem de diversas situações reais em física, química, biologia, engenharia elétrica e pesquisa operacional. Tanto em problemas práticos como em problemas teóricos tem-se o fato que a maioria das aplicações admitem métodos de resolução mais eficientes se o grafo associado for planar. A determinação da planaridade de um grafo é importante em diversas aplicações na indústria, engenharia e outras. Um aspecto neste estudo é que a planaridade é uma propriedade preservada mediante o isomorfismo de grafos. Também apresenta-se duas caracterizações da planaridade, uma devido a Kuratowski e outra devido a Wagner. São dois resultados clássicos da teoria de grafos, que identificam condições necessárias e suficientes para um dado grafo ser planar, e cujas técnicas de demonstração são ainda importantes em combinatória. / The main goal of this work is to treat the geometrical and topological implications of planarity, highlighting the infl.uence of t his concept over fundamental problems. Such problems are derived from the Euler's formula and its applications. Topological problems, such as map colouring, are also dealt with in this thesis. Graph theory has extensive use in applied mathematics, because it shows to be a powerful tool for modelling real situations in physics, chemistry, biology, electrical engineering and operational research. In theory, as well as in practical problems, it is the fact most applications admit more efficient solution methods if the associated graph is planar. The determination of the planarity of a graph is important in various applications in industry, engineering and others. An aspect of this survey is that planarity is an invariant property preserved throu~h graph isomorphisms. It is also presented two characterizations of planarity. One is due to Kuratowski and the other is due to Wagner. These are two classical results of graph theory, that identify necessary and sufficient conditions for a graph to be planar, whose t echniques are still important in combinatorics.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2008. / Submitted by Raquel Viana (tempestade_b@hotmail.com) on 2009-11-09T20:11:56Z No. of bitstreams: 1 2008_BuenoBorgesSouza.pdf: 5583476 bytes, checksum: a97d2b35caf210b712bd8d34c76a4a9d (MD5) / Approved for entry into archive by Marília Freitas(marilia@bce.unb.br) on 2009-12-08T11:54:06Z (GMT) No. of bitstreams: 1 2008_BuenoBorgesSouza.pdf: 5583476 bytes, checksum: a97d2b35caf210b712bd8d34c76a4a9d (MD5) / Made available in DSpace on 2009-12-08T11:54:06Z (GMT). No. of bitstreams: 1 2008_BuenoBorgesSouza.pdf: 5583476 bytes, checksum: a97d2b35caf210b712bd8d34c76a4a9d (MD5) Previous issue date: 2008-06-13 / Esta pesquisa descreve um sistema de auxílio a decisão com aplicação de metodologias de Teoria dos Grafos e Inteligência Artificial para dar suporte ao Gerenciamento de Fluxo de Tráfego Aéreo Brasileiro. Implementa-se um modelo de gerenciamento de fluxo baseado em grafos, com adaptações heurísticas, para a regulação dinâmica do fluxo. O modelo apresenta a arquitetura do Módulo de Balanceamento de Fluxo - MBF, que integra o Sistema Distribuído de Apoio a Decisão aplicado ao Gerenciamento Tático do Fluxo de Tráfego (SISCONFLUX), atualmente em desenvolvimento, e tem o objetivo de propiciar informações que ajudem na melhoria do gerenciamento do espaço aéreo nacional. O Módulo de Balanceamento de Fluxo (MBF) foi idealizado como um módulo do SISCONFLUX que tem a função de dar suporte ao sistema em operação no Primeiro Centro Integrado de Defesa Aérea e Controle de Tráfego Aéreo (CINDACTA I) e fornecer novas informações que auxiliem o gerenciamento do processo aplicado pelos controladores neste centro. Por meio de técnicas de maximização de fluxo adaptadas da Teoria dos Grafos, o MBF aplica um modelo de análise que determina o tempo de separação entre decolagens a partir das terminais contidas na Região de Informação de Vôo de Brasília (FIR-BS) e distribui a folga do fluxo ao longo do espaço aéreo controlado. O objetivo é prevenir ou reduzir o congestionamento nos diversos setores da FIR-BS. Com a ajuda dos outros módulos do SISCONFLUX, o MBF dá suporte a regulação do fluxo de tráfego com o objetivo de auxiliar os controladores na tomada de decisão. Com o desenvolvimento dessa ferramenta os controladores podem adquirir o conhecimento que os auxilie a tomar decisões. A pesquisa também apresenta os resultados de uma simulação com duas políticas: distribuição do fluxo igualitária e priorizada. Como exemplo mostra-se que a separação dos tempos de decolagens podem ser reduzidas de 30% a 60%, dependendo da política aplicada. _______________________________________________________________________________________ ABSTRACT / This research describes a decision system that uses the methodology of Graph Theory and Artificial Intelligence to support Air Trafic Flow Management in Brazilian air space. It implements a model for flow management based on graph with adapted heuristics for the regulation of the dynamic flow. The model presents the architecture of the Flow Balancing Module (FBM) and integrates with the Distributed Decision Support System Applied to Tactical Air Trafic Flow Management (SISCONFLUX), currently under development, with the objective to improve the national air space management. The FBM is proposed to support the operation system at First Integrated Center of Air Defense and Air Trafic Control - CINDACTA I and to help and improve the management process of controllers in this center. Using the maximization flow technique of adapted Graph Theory, FBM is developed as an analysis model that determines the take-off separation time from terminals within Flight Information Region of Brasilia (FIR-BS) and distributes the slack of flow along the controlled air space. The objective is to prevent or reduce congestions in diverse sectors of FIR-BS. With the help of other modules, FBM supports the regulation of trafic flow with the objective of give extra informations to controllers and other units within the SISCONFLUX. By means of the system developed, air trafic controllers and supervisors can effectively acquire knowledge and get assistance to make better decisions. The research also presents the results of the simulation with two policies: egalitarian and prioritization distribution of the flight flow. As an example, it shows that the take-off separation time should be reduced about 30% to 60%, depending on the policy applied.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2013. / Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2013-10-30T09:26:40Z No. of bitstreams: 1 2013_EliasdaCosta_Parcial.pdf: 94443 bytes, checksum: 4d38e1280c4bf24fd8c8215d3de01b0d (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-10-30T10:21:14Z (GMT) No. of bitstreams: 1 2013_EliasdaCosta_Parcial.pdf: 94443 bytes, checksum: 4d38e1280c4bf24fd8c8215d3de01b0d (MD5) / Made available in DSpace on 2013-10-30T10:21:14Z (GMT). No. of bitstreams: 1 2013_EliasdaCosta_Parcial.pdf: 94443 bytes, checksum: 4d38e1280c4bf24fd8c8215d3de01b0d (MD5) / Na primeira parte deste trabalho, apresentamos a teoria geral das medidas de Gibbs. A abordagem é baseada nas equações DLR e no formalismo termodinâmico. Em seguida, estudamos o modelo de Ising ferromagnético bidimensional. Mostramos que este modelo possui a propriedade forte de Markov e também algumas desigualdades de correlação, por exemplo a desigualdade de FKG. Por último provamos o Teorema de Aizenman-Higuchi o principal resultado desta dissertação. Este teorema sobre decomposição extremal foi provado independentemente, no inícios dos anos oitenta, por Michael Aizenman e Atsushi Higuchi, ambos baseados nos trabalhos de Lucio Russo. A prova dada aqui, devido a Aizenman, se baseia na investigação das simetrias dos espaços de configurações duplas e na aplicação sistemática da desigualdade de FKG e das equações DLR. _______________________________________________________________________________________ ABSTRACT / In the first part of this work, we present the general Gibbs measure theory. The approach is based on the DLR equations and the Thermodynamical Formalism. Next we study the ferromagnetic Ising model on the square lattice. We prove that this model satisfy the strong Markov property and also prove some correlation inequalities, as for example FKG. In the end we prove the Aizenman-Higuchi's theorem which is the main result of this master thesis. This theorem is about extremal decomposition and it was proved independently by Michael Aizenman and Atsushi Higuchi, both based on the work of Lucio Russo. The proof given here is due to Aizenman and is made by the investigation of the double configuration space symetries and systematic application of the FKG inequality and the DLR equations.