Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

Made available in DSpace on 2017-07-21T19:25:54Z (GMT). No. of bitstreams: 1 Mauricio A Ribeiro.pdf: 11596045 bytes, checksum: a3c106c698d0e695c79bdb2053e8bd59 (MD5) Previous issue date: 2016-08-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this study, we discuss the presence of social structures in classical literature, in particular the ones by two writers: Homer ("Odyssey") and J.R.R. Tolkien ("The Silmarillion", "The Hobbit"and the trilogy "The Lord of the Rings"), that, somehow, influenced the society in different ways. In this context, based on the pieces of definition of social relations presented in this work, we analyze the literary social structures that are presented in these books, which have characteristics that are similar to the current online real social structures, like Facebook and Twitter, in which individuals interact in various ways. Therefore, we use graphs theory to study and compare the literary social structures present in that literature and the online real social structures, causing the appearance of connectivity distributions formed by the social relations among the characters (in the literary social structures) and among individuals (in online real social structures). Such distributions follow a power law with an exponential cutoff, which differs from connectivity distributions of structures found in the scientific literature. Other properties found in these analyzes are: the ubiquity attribute of the gods that are in the literary social structures (detected through varying the average path length of these structures); the friendship paradox; the transitivity; the assortativity; and the distribution of betweenness centrality. Due to these similarities between the two types of social structures that were studied, we chose to analyze the vulnerability, the efficiency and the homogeneity of social relations of literary social structures by some attack methodologies, like removing from these structures only a character, a group of characters or whole communities. / Nesta tese, abordaremos a presença de estruturas sociais em obras clássicas, em particular de dois escritores: Homero (“Odisseia”) e J.R.R. Tolkien (“O Silmarillion”, “O Hobbit” e a trilogia de “O Senhor dos Anéis”), que, de certa forma, influenciaram a sociedade em diversos níveis. Nesse contexto, com base nas definições de relações sociais apresentadas neste trabalho, analisamos as estruturas sociais literárias que surgem nessas obras e que possuem características semelhantes às das estruturas sociais reais online) da atualidade, como o Facebook e o Twitter, em que os indivíduos interagem das mais diversas maneiras. Portanto, utilizamos a teoria dos grafos para estudar e comparar as estruturas sociais literárias presentes em tais obras e as estruturas sociais reais (online), possibilitando o surgimento de distribuições de conectividade formadas pelas relações sociais entre as personagens (nas estruturas sociais literárias) e entre indivíduos (nas estruturas sociais reais online). Tais distribuições seguem uma lei de potência com truncamento exponencial, o que difere das distribuições de conectividade das estruturas encontradas na literatura científica. Outras propriedades encontradas nessas análises são: o atributo de onipresença das divindades que estão inseridas nas estruturas sociais literárias (detectado através da variação da distância de caminho médio dessas estruturas); o paradoxo da amizade; a transitividade; a assortatividade; e a distribuição de centralidade de intermediação. Devido a tais similaridades entre os dois tipos de estruturas sociais estudadas, optamos por analisar a vulnerabilidade, a eficiência e a homogeneidade das relações sociais das estruturas sociais literárias mediante algumas metodologias de ataques, como remover dessas estruturas somente um personagem, um grupo de personagens ou comunidades inteiras.

Este trabalho apresenta uma nova estrutura matemática para a álgebra de caminhos, que permite analisar a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop e, sob o ponto de vista da engenharia de tráfego e da Qualidade de Serviço (QoS) na arquitetura Generalized Multiprotocol Label Switching (GMPLS), garantir de maneira confiável a incorporação de novas métricas de roteamento aos algoritmos de roteamento baseados em múltiplas restrições. Baseando-se nessa nova álgebra de caminhos, são analisadas as propriedades de monotonicidade, isotonicidade e liberdade, conhecidas por garantir a convergência dos algoritmos de roteamento e, ao contrário do indicado na literatura até o momento, verifica-se que a propriedade de monotonicidade não e condição necessária e nem suficiente para garantir a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop. Sendo assim, este trabalho propõe uma nova propriedade, denominada coerência, para a garantia da convergência do roteamento hop-by-hop e um novo algoritmo de roteamento hop-by-hop com convergência garantida. Para avaliar os resultados teóricos obtidos, s~ao analisados dois estudos de casos de aplicação do roteamento multi-restritivos hop-by-hop com o uso de uma ferramenta de simulação desenvolvida em MATLAB e baseada no algoritmo Eliminação de Loop pelo Nó de Destino (ELND) também proposto. Como resultado das simulações desses estudos de casos, verifica-se que as diferentes estratégias de otimização, necessárias as redes (GMPLS), impõem a necessidade de trabalhar com algoritmos de roteamento que permitam a definição de mais de duas métricas de roteamento com diferentes critérios de otimização para cada uma delas, comprovando, portanto, a necessidade do desenvolvimento e da continuação deste trabalho. / This work presents a new mathematical structure for paths algebra that allows the convergence analysis of hop-by-hop multi-constrained routing algorithms and, under the traffic engineering and quality of service perspectives in the Generalized Multiprotocol Label Switching (GMPLS) architecture, trustily ensures the aggregation of new routing metrics in a constrained-based routing. Based on this new paths algebra, we analyze the monotonicity, isotonicity and freeness properties, known as ensuring routing algorithms convergence, and despite of what has been indicated in the literature, we verified that the monotonicity property is not sufficient to ensure the hop-by-hop routing convergence. Therefore, this work proposes a new property, called coherence, as a necessary and sufficient condition to ensure it, as well as, a new multi-constrained hop-by-hop routing algorithm with ensured convergence. In order to evaluate the theoretical results obtained, two study cases of the hop-by-hop multi-constrained routing applications are analyzed in the present thesis by using the Eliminação de Loop pelo Nó de Destino (ELND) simulation tool, developed in MATLAB and also presented as a product of this work. As result of these study cases simulations, we verified that different optimization strategies, requested by the (GMPLS) networks, compel the use of routing algorithms that allow the specification of more than two routing metrics with different optimization criteria for each one of them, thus proving the necessity of this work and its continuation.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-08-25T20:24:28Z No. of bitstreams: 1 JandersonFreitas.pdf: 2087995 bytes, checksum: e49b1008df3093f81aeb841870a06df9 (MD5) / Made available in DSpace on 2017-08-25T20:24:28Z (GMT). No. of bitstreams: 1 JandersonFreitas.pdf: 2087995 bytes, checksum: e49b1008df3093f81aeb841870a06df9 (MD5) Previous issue date: 2017-05-08 / The paper presents problem solving using Graph Theory and Euler’s Theorem. The research performs specific activities in high school involving graphs in various applications of the Euler relation as a problem solving method with Graph Theory. The relationship of Euler is presented in a Geometric view and by the graphs planning. The research proposes a link between the students ’daily problems with the modeling of problem situations by the Graph Theory, specifically the planar graphs solved with the implementation of Euler’ s Theorem focused on the teaching of basic mathematics. Applications of Graph Theory are shown in solving problems with the bridges of the city of Barra do Corda and the students’ school life. / O trabalho apresenta a resolução de problemas utilizando a Teoria dos Grafos e o Teorema de Euler. Uma pesquisa que executa atividades específicas no ensino médio envolvendo grafos em várias aplicações da relação de Euler como método de resolução de problemas com Teoria dos Grafos. A relação de Euler é apresentada em uma visão Geométrica e pela planificação dos grafos. Propondo um elo entre os problemas do cotidiano dos alunos com a modelagem de situações problema pela Teoria dos Grafos, especificamente os grafos planares resolvidos com a implementação do Teorema de Euler voltado ao ensino de matemática básica. São mostradas aplicações da Teoria dos Grafos na resolução de problemas com as pontes da cidade de Barra do Corda e da vida escolar dos alunos.

Submitted by FLAVIA FERNANDA FAVARO null (flaviafavaro@hotmail.com) on 2018-01-10T03:14:21Z No. of bitstreams: 1 A Teoria dos Grafos e sua abordagem na sala de aula com recursos educacionais digitais.pdf: 2731904 bytes, checksum: 49a548fa505952226f589c5471f9b496 (MD5) / Approved for entry into archive by Adriana Aparecida Puerta null (dripuerta@rc.unesp.br) on 2018-01-10T18:21:25Z (GMT) No. of bitstreams: 1 favaro_ff_me_rcla.pdf: 2692020 bytes, checksum: c889310c873cab619e98b36f809e81c0 (MD5) / Made available in DSpace on 2018-01-10T18:21:25Z (GMT). No. of bitstreams: 1 favaro_ff_me_rcla.pdf: 2692020 bytes, checksum: c889310c873cab619e98b36f809e81c0 (MD5) Previous issue date: 2017-12-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho estudamos a Teoria dos Grafos compreendendo suas definições, resultados e algumas aplicações como O Problema das Pontes de Köningsberg, O Problema Chinês do Carteiro, O Problema do Caixeiro Viajante e O Teorema das Quatro e das Cinco Cores. Com o uso da Coleção M3 - Matemática Multimídia, que contém recursos educacionais em formatos digitais, aplicamos as atividades sugeridas aos alunos do segundo ano do Ensino Médio de uma escola particular localizado na cidade de São Pedro - SP. As atividades mostraram que, apesar da Teoria dos Grafos não constar no currículo regular do Ensino Médio, sua aplicação para este grupo de alunos foi positiva, uma vez que os alunos sentiram-se motivados com o conteúdo abordado na forma digital e com sua aplicação ao estudo de Matrizes. Concluímos assim que, nos dias atuais a ligação do processo de ensino aprendizagem com os softwares educacionais podem proporcionar, tanto para os professores quanto para os alunos, uma forma mais prazerosa e eficaz de obter conhecimento em Matemática. / In this work, we study Graph Theory, meaning its definitions, results e some applications such as the Köningsberg bridge problem, the chinese postman problem, the travelling salesman problem and the four color theorem as well as the five color theorem. By using the M3 - Matemática Multimídia Series, which contains educational resources in digital form, we applied the suggested activities to second year high school students form a private school located at the city of São Pedro – São Paulo State. The activities showed that, although Graph Theory is not part of the high school regular curriculum, its application to this group of students was positive, since the students felt themselves motivated by the digital approach to its contents and its applications to the study of Matrices. We conclude that, nowadays, the connection between the teaching processes and educational softwares can provide, to the teachers as well as to the students, a more pleasurable and efficient way to obtain knowledge in Mathematics.

Orientador: Fabricio Aparecido Breve / Banca: Denis Henrique Pinheiro Salvadeo / Banca: Diego Raphael Amancio / Resumo: O Aprendizado de Máquina é uma área que vem crescendo nos últimos anos e é um dos destaques dentro do campo de Inteligência Artificial. Atualmente, uma das subáreas mais estudadas é o Aprendizado Semi-Supervisionado, principalmente pela sua característica de ter um menor custo na rotulação de dados de exemplo. A categoria de modelos baseados em grafos é a mais ativa nesta subárea, fazendo uso de estruturas de redes complexas. O algoritmo de competição e cooperação entre partículas é uma das técnicas deste domínio. O algoritmo provê acurácia de classificação compatível com a de algoritmos do estado da arte, e oferece um custo computacional inferior à maioria dos métodos da mesma categoria. Neste trabalho é apresentado um estudo sobre Aprendizado Semi-Supervisionado, com ênfase em modelos baseados em grafos e, em particular, no Algoritmo de Competição e Cooperação entre Partículas (PCC). O objetivo deste trabalho é propor um novo algoritmo de competição e cooperação entre partículas baseado neste modelo, com mudanças na caminhada pelo grafo, com informações de dominância sendo mantidas nas arestas ao invés dos nós; as quais possam melhorar a acurácia de classificação ou ainda o tempo de execução em alguns cenários. É proposta também uma metodologia de avaliação da rede obtida com o modelo de competição e cooperação entre partículas, para se identificar a melhor métrica de distância a ser aplicada em cada caso. Nos experimentos apresentados neste trabalho, pode ser visto que... / Abstract: Machine Learning is an increasing area over the last few years and it is one of the highlights in Artificial Intelligence area. Nowadays, one of the most studied areas is Semi-supervised learning, mainly due to its characteristic of lower cost in labeling sample data. The most active category in this subarea is that of graph-based models, using complex networks concepts. The Particle Competition and Cooperation in Networks algorithm (PCC) is one of the techniques in this field. The algorithm provides accuracy compatible with state of the art algorithms, and it presents a lower computational cost when compared to most techniques in the same category. In this project, it is presented a research about semi-supervised learning, with focus on graphbased models and, in special, the Particle Competition and Cooperation in Networks algorithm. The objective of this study is to base proposals of new particle competition and cooperation algorithms based on this model, with new dynamics on the graph walking, keeping dominance information on the edges instead of the nodes; which may improve the accuracy classification or yet the runtime in some situations. It is also proposed a method of evaluation of the network built with the Particle Competition and Cooperation model, in order to infer the best distance metric to be used in each case. In the experiments presented in this work, it can be seen that the proposed algorithm presented better accuracy when compared to the PCC for some datasets, while the proposed distance metrics evaluation achieved a high precision level in most cases / Mestre

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Mecânica, Florianópolis, 2010 / Made available in DSpace on 2012-10-24T22:44:03Z (GMT). No. of bitstreams: 1 281094.pdf: 2556693 bytes, checksum: 3357c5d3f7a1cfe0bddeec63b21572c0 (MD5) / A fase de projeto conceitual demecanismos emanipuladores paralelos, i.e. estruturas cinematicas, destina-se ao desenvolvimento da concepçao da cadeia cinematica. As etapas fundamentais para o desenvolvimento da concepao da cadeia cinematica sao sintese e analise. A sintese corresponde à enumeraçao de concepcoes e a analise corresponde `a seleçao das concepçoes mais promissoras considerando os requisitos de projeto. O objetivo deste trabalho é aplicar ferramentas da teoria de grupos e teoria de grafos para a enumeraçao e para a analise de estruturas cinematicas. A enumeraçao sera desenvolvida de forma sistematica em tres niveis: enumeraçao de cadeias cinematicas, enumeraçao de mecanismos e enumeraçao de manipuladores paralelos. A aplicaçao de ferramentas da teoria de grafos e grupos permite desenvolver novos metodos para enumeraçao e, consequentemente, obter novos resultados. A analise sera simplificada considerando um novo metodo que avalia as simetrias das cadeias cinematicas. Uma cadeia cinematica é representada de forma univoca atraves de um grafo. A representaçao atraves do grafo permite a manipulaçao computacional do problema de enumeraçao de cadeias cinematicas. A aplicaçao de ferramentas integradas da teoria de grafos e teoria de grupos permite identificar as simetrias das cadeias cinematicas atraves do grupo de automorfismos do grafo e, assim, é possivel identificar quais são as possiveis escolhas de base para novos mecanismos e avaliar quais sao as possiveis escolhas de base e efetuador final para manipuladores paralelos. O primeiro nivel da sintese corresponde à enumeraçao de cadeias cinematicas com determinada mobilidade, numero de elos, numero de juntas que operam num determinado sistema de helicoides. O segundo nivel da sintese corresponde a enumeraçao de mecanismos. Um mecanismo é uma cadeia cinematica com um elo escolhido para ser a base. Assim, a enumeraçao de mecanismos consiste em determinar todas as possiveis escolhas de bases para uma determinada cadeia cinematica. O principal conceito empregado neste nivel é o de simetria de grafos não coloridos e orbitas do grupo de automorfismos. O terceiro nivel da sintese corresponde `a enumeraçao de manipuladores paralelos. Um manipulador paralelo é uma cadeia cinematica com um elo escolhido para ser a base e outro para ser o efetuador final. Em outras palavras, um manipulador paralelo é um mecanismo com um elo escolhido para ser o efetuador final. Assim, a enumeraçao de manipuladores paralelos consiste em determinar todas as possiveis escolhas de efetuador final para um determinado mecanismo. O principal conceito empregado neste nivel é a simetria de grafos coloridos e orbitas do grupo de automorfismos de grafos coloridos. Na etapa de analise das concepcoes enumeradas serao abordadas propriedades bem estabelecidas na literatura: mobilidade, variedade, conectividade, grau de controle, redundancia e simetria. Mobilidade e variedade sao propriedades globais das estruturas cinematicas. Conectividade, grau de controle e redundancia sao propriedades locais, i.e. entre dois elos da estrutura cinematica e sao dadas por matrizes n×n, onde n é o número de elos da cadeia. A simetria pode ser considerada uma propriedade global e/ou local da estrutura cinem´atica. A aplicaçao de ferramentas integradas da teoria de grafos e teoria de grupos permite demonstrar que as propriedades locais sao invariantes pela acao do grupo de automorfismos do grafo, i.e. elas sao propriedades simetricas. Desta forma, a representaçao matricial é reduzida de n×n para o×n, onde o é o numero de orbitas do grupo de automorfismos do grafo aassociado à estrutura cinematica. Essa abordagem permite simplificar a analise de estruturas cinematicas apenas considerando as simetrias das cadeia associadas.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-graduação em Engenharia Mecânica / Made available in DSpace on 2012-10-23T23:10:37Z (GMT). No. of bitstreams: 1 248436.pdf: 960786 bytes, checksum: ea91ab2ec7da01bf13ed0f739309d988 (MD5) / O objetivo principal deste trabalho é apresentar novas abordagens para a síntese estrutural de cadeias cinemáticas, que é uma fase fundamental para o projeto de mecanismos, utilizando ferramentas da teoria de grafos e da teoria de grupos. A síntese estrutural de cadeias cinemáticas consiste na geração de uma lista completa de cadeias cinemáticas sem cadeia isomórficas e degeneradas que satisfazem a equação da mobilidade. Nesta fase do projeto de mecanismos as dimensões dos elos não são consideradas e uma cadeia cinemática pode ser representada de forma unívoca por um grafo cujos vértices correspondem aos elos da cadeia e as arestas correspondem às juntas. Com isso, a síntese estrutural de cadeias cinemáticas consiste na geração de uma lista completa de grafos que satisfazem a equação da mobilidade. Uma revisão dos principais métodos de síntese estrutural de cadeias cinemáticas é apresentada e os principais problemas desses métodos são identificados. Existem duas espécies de problemas: geração de cadeias isomórficas e degeneradas as quais devem sempre ser evitadas por um método ideal de síntese estrutural; e a geração de cadeias com fracionamento as quais devem ser consideradas opcionais. Em vista disto, dois métodos de geração de cadeias sem fracionamento e um de cadeias com fracionamento são aprimorados e um novo método de geração exclusiva de cadeias com fracionamento é proposto. Novos resultados são obtidos para cadeias que operam em vários sistemas de helicóides. Os resultados serão apresentados em tabelas, e para o caso plano, as diferenças nos resultados encontrados na literatura serão analisados. A síntese estrutural de mecanismos consiste na enumeração das possíveis inversões cinemáticas que uma cadeia cinemática pode originar. Para esta fase foi utilizada uma nova abordagem com ferramentas da teoria de grupos. Pela primeira vez na literatura de mecanismos foi introduzido o conceito de órbitas do grupo de automorfismos do grafo, o qual representa a cadeia cinemática, para representar as inversões cinemáticas. Novos resultados são obtidos para mecanismos que operam em vários sistemas de helicóides e apresentados em tabelas.

Submitted by Nathália Faria da Silva (nathaliafsilva.ufv@gmail.com) on 2017-10-04T12:42:42Z No. of bitstreams: 1 texto completo.pdf: 13995495 bytes, checksum: 71c34a30f49b54385642ee42cdb41d72 (MD5) / Made available in DSpace on 2017-10-04T12:42:42Z (GMT). No. of bitstreams: 1 texto completo.pdf: 13995495 bytes, checksum: 71c34a30f49b54385642ee42cdb41d72 (MD5) Previous issue date: 2017-02-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A Teoria dos Grafos está associada a situações que podem ser descritas por meio de diagramas representados por um conjunto de pontos (vértices) e linhas que ligam alguns pares destes pontos (arestas). Seu inı́cio remonta a visita de Leonhard Euler à cidade de Königsberg, em 1736, quando foi apresentado a ele um desafio que intrigava os moradores da cidade. Eles se perguntavam se era possı́vel sair de casa, passar em cada ponte, apenas uma vez, e retornar ao ponto inicial. O diagrama montado por Euler para representar o mapa das sete pontes da cidade é um esquema de grafo. O desenvolvimento e a consolidação da Teoria dos Grafos proporcionou significativas contribuições para a Fı́sica, Quı́mica, Biologia e Ciência da Computação. Os algoritmos associados a problemas de caminho mı́nimo, coloração e busca de árvore geradora mı́nima são amplamente utilizados na prática de linguagem de programação. Nessa pesquisa, o problema de caminho mı́nimo e a busca da árvore geradora mı́nima são usados para o trabalho de algoritmos envolvendo grafos com alunos do Ensino Médio em uma escola de Belo Horizonte. Uma sequência didática com três aulas foi aplicada, sendo a primeira aula sobre a introdução à teoria dos grafos, a segunda aula sobre algoritmos e grafos e a terceira aula com a implementação desses algoritmos usando a linguagem de programação C. Os algoritmos utilizados foram Dijkstra, Prim, Kruskal e Floyd. Resultados apontam para a possibilidade de inclusão da Teoria dos Grafos no Ensino Médio tendo em vista as interações com Análise Combinatória, Probabilidade e Poliedros. O estudo de grafos por meio de algoritmos e sua aplicação em linguagem de programação é uma nova abordagem a ser considerada para o Ensino Médio. / The Theory of Graphs is associated with situations that can be described by means of diagrams represented by a set of points (vertices) and lines that connect some pairs of these points (edges). Its beginning dates back to Leonhard Euler’s visit to the town of Königsberg in 1736, when he was presented with a challenge that intrigued the city’s residents. They wondered if it was possible to get out of the house, pass on each bridge only once, and return to the starting point. The diagram assembled by Euler represent the map of the city’s seven bridges is a graph diagram. The development and consolidation of Graph Theory provided significant contributions to Physics, Chemistry, Biology and Computer Science. The algorithms associated with minimum path, coloring, and minimum generation tree search algorithms are widely used in programming language practice. In this research, the minimum path problem and the minimum generation tree search are used to work with algorithms involving graphs with high school students in a school in Belo Horizonte. A didactic sequence with three sections was applied, being the first class on the introduction to the graph theory, the second class on algorithms and graphs and the third class with the implementation of these algorithms using the C programming language. The algorithms used were Dijkstra, Prim, Kruskal and Floyd. Results point to the possibility of including the Theory of Graphs in High School in view of the interactions with Combinatorial Analysis, Probability and Polyhedra. The study of graphs through algorithms and their application in programming language is a new approach to be considered for High School.

IVO, Rafael Fernandes. Uma nova estratégia para renderizar descontinuidades e superfícies intersectantes em modelos baseados em splats. 2011. 87 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T15:39:16Z No. of bitstreams: 1 2011_dis_rfivo.pdf: 18188495 bytes, checksum: 8bba2f9c682856ab4b475566ec0afe9a (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-21T14:07:35Z (GMT) No. of bitstreams: 1 2011_dis_rfivo.pdf: 18188495 bytes, checksum: 8bba2f9c682856ab4b475566ec0afe9a (MD5) / Made available in DSpace on 2016-07-21T14:07:35Z (GMT). No. of bitstreams: 1 2011_dis_rfivo.pdf: 18188495 bytes, checksum: 8bba2f9c682856ab4b475566ec0afe9a (MD5) Previous issue date: 2011 / Splats based models have gained increasing attention due to its potential for rendering complex geometric models efficiently and with high quality. The absence connectivity information of these models allows complex modeling operations, as Boolean operations, and fractures in physics simulations. However, these operations often generate models with edges and corners that can not be represented correctly with a finite number of splats without a treatment to be done. In this work, a neighborhood graph uses an estimate which ensures the connection of all these splats on opposite sides a discontinuity and that need to be clipped against each other. After using a method for detecting discontinuities in the generated graph, the neighbors participating in the a splat clipping, clip partners are determined to cut out and sorted splat so as to adapt it to the curve of discontinuity. Another problem encountered in rendering models based on reconstruction of splats is intersecting surfaces. Close intersections of surfaces, the surfaces are mixed, resulting in artifacts. to treat these cases, a segmentation algorithm performs separation of the various surfaces present in the model, identifying the splats that form and hold them to be combined into areas near the intersections of surfaces in the surface reconstruction phase space image. / Modelos baseados em splats têm ganhado crescente atenção devido a seu potencial para renderizações de modelos geométricos complexos de forma eficiente e com alta qualidade. A ausência de informações de conectividade desses modelos permite operações de modelagem complexas, como operações booleanas, e fraturas em simulações físicas. Entretanto, essas operações geralmente geram modelos com arestas e cantos que não podem ser representados corretamente com um número finito de splats sem que um tratamento seja feito. Neste trabalho, um grafo de vizinhança utiliza uma estimativa que garante a conexão de todos os splats presentes em lados opostos de uma descontinuidade e que precisam ser recortados uns contra os outros. Após utilizar um método de detecção de descontinuidades no grafo gerado, os vizinhos que participam do recorte de um splat, os clip partners, são determinados e classificados para que recortem o splat de forma a adaptá-lo à curva da descontinuidade. Outro problema encontrado na renderização de modelos baseados em splats é reconstrução de superfícies intersectantes. Nas proximidades de interseções de superfícies, as superfícies são misturadas, resultando em artefatos. Para tratar esses casos, um algoritmo de segmentação realiza a separação das diversas superfícies presentes no modelo, identificando os splats que as formam e impedindo que eles sejam combinados em áreas próximas de interseções de superfícies na etapa de reconstrução da superfície em espaço de imagem.