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

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.

MELO, Henrique Alves de. Fórmula de Euler no plano e para poliedros. 2013. 54 f. Dissertação (Mestrado em Matemática em Rede Nacional) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Rocilda Sales (rocilda@ufc.br) on 2014-03-26T16:16:01Z No. of bitstreams: 1 2013_dis_hamelo.pdf: 14135976 bytes, checksum: e309e7f484cd1319bc4d472ff39b05ae (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2014-03-26T16:18:25Z (GMT) No. of bitstreams: 1 2013_dis_hamelo.pdf: 14135976 bytes, checksum: e309e7f484cd1319bc4d472ff39b05ae (MD5) / Made available in DSpace on 2014-03-26T16:18:25Z (GMT). No. of bitstreams: 1 2013_dis_hamelo.pdf: 14135976 bytes, checksum: e309e7f484cd1319bc4d472ff39b05ae (MD5) Previous issue date: 2013 / Polyhedra are geometric solids formed by a finite number of polygons they can be convex or non-convex, regular or not regular. This work we make three demonstrations of Euler’s theorem for polyhedra in one plane being used graphs. We will adopt preliminary definitions of polygons, polyhedra and graphs and make a brief study of the theorem before the demonstrations analysis when the theorem is valid and what conditions exist polyhedra, since the theorem is accepted. The work brings some applications in the form of questions in the theory presented. / Os poliedros são sólidos geométricos formados por uma quantidade finita de polígonos. Eles podem ser convexos ou não convexos, regulares ou não regulares . Neste trabalho fazemos três demonstrações do teorema de Euler para poliedros no plano, sendo uma utilizado grafos. Adotaremos definições preliminares de polígonos, poliedros e grafos e faremos um breve estudo do teorema antes das demonstrações analisado quando o teorema é valido em quais condições existem os poliedros, uma vez que o teorema é aceito. O trabalho traz algumas aplicações em forma de questões da teoria apresentada.

ARAÚJO, R. T. Convexidades de caminhos e convexidades geométricas. 2014. 52 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T18:18:58Z No. of bitstreams: 1 2014_dis_rtaraújo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-09-23T16:28:22Z (GMT) No. of bitstreams: 1 2014_dis_rtaraújo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) / Made available in DSpace on 2015-09-23T16:28:22Z (GMT). No. of bitstreams: 1 2014_dis_rtaraújo.pdf: 997190 bytes, checksum: 1adad553da251fa0f87bb80fbe452db4 (MD5) Previous issue date: 2014 / In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P∗ 3 . We show a relation between the geodetic convexity and the P∗ 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P∗ 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P∗ 3 in graphs with few P4’s.

Tese (doutorado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, Programa de Pós-Graduação em Matemática, 2014. / Submitted by Ana Cristina Barbosa da Silva (annabds@hotmail.com) on 2015-01-30T14:49:50Z No. of bitstreams: 1 2014_AndreiaBorgesAvelar.pdf: 1538432 bytes, checksum: a4c007b570815d67eeac5de0133a52bb (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2015-05-04T10:30:29Z (GMT) No. of bitstreams: 1 2014_AndreiaBorgesAvelar.pdf: 1538432 bytes, checksum: a4c007b570815d67eeac5de0133a52bb (MD5) / Made available in DSpace on 2015-05-04T10:30:29Z (GMT). No. of bitstreams: 1 2014_AndreiaBorgesAvelar.pdf: 1538432 bytes, checksum: a4c007b570815d67eeac5de0133a52bb (MD5) / Uma nova estrutura baseada em digrafos e denominada Grafos com Matrizes de Medida (MWGs) é apresentada. Esta estrutura se baseia na estrutura conhecida como Grafos de Contextos de Chamado (CCGs) e é aplicada na verificação de terminaçãao de programas funcionais de primeira-ordem especificados no estilo da linguagem de especifica¸cao do as- sistente de prova PVS. Similarmente a CCGs, os vértices em um MWG correspondem aos chamados recursivos da função modelada. Caminhos em um MWG, assim como em um CCG, representam o fluxo de execução dos chamados recursivos do programa em questão. De acordo com o princípio de mudança de tamanho, MWGs são aplicados na verificação de terminação através da especificação de critérios para garantir que todos os circuitos no MWG, que corresponderiam a possíveis execuções infinitas de chamados recursivos, nao podem ser repetidos infinitamente. Em CCGs, isto é realizado através da construção de combinação de medidas, sobre o domínio de uma relação bem-fundada, definidas nos parâmetros da função recursiva que está sendo modelada. Assim, a fim de verificar terminação da função, deve-se verificar que a combinação de medidas decresce estritamente em todos os possíveis circuitos. Ao invés de procurar uma combinação de medidas para cada circuito, em MWGs as arestas são rotuladas com matrizes quadradas cujas entradas expressam relaçoes entre diferentes medidas aplicadas aos parâmetros formais e atuais. Desta forma, o comportamento das medidas após executar uma sequência de chamados recursivos associada a um caminho no MWG é expresso através da multiplicação especializada das matrizes que rotulam as arestas do caminho. O critério de terminação em MWG corresponde a uma simples noção de positividade da matrix associada a um determinado circuito. As matrizes de medida modelam o resultado das combinações de medidas da tecnologia CCG de uma forma muito elegante possibilitando a formulação de critérios simples de terminação em MWGs. Tais critérios baseiam-se na positividade dos ciclos (circuitos simples) do MWG, levando a positividade de qualquer circuito. Dois critérios de terminação para MWGs são formalizados. A correspondência entre terminação em CCGs e MWGs é formalizada. A especificação de uma simples linguagem funcional de primeira-ordem com sua respectiva semântica para terminação é apresentada, e são discutidos os elementos necessários para a formalizaçao da correspondência entre a semântica de terminação para esta linguagem e terminação em MWGs. _____________________________________________________________________________ ABSTRACT / A new digraph structure called Matrix-Weigthed Graphs (MWGs) is presented. This structure is based on Calling Context Graphs (CCGs) and is applied to verify termination of first-order functional programs written in the style of the specification language of the PVS proof assistant restricted to its first-order fragment. Similarly to CCGs, a MWG has nodes that correspond to the recursive calls of the modeled program. Paths in a MWG, as well as in a GCC, model the execution ow of recursive calls in the associated program. According to the size-change termination principle, MWGs are used to verify termination of the specification through criteria that guarantee that all circuits in the MWG, would correspond to possible infinite executions of recursive calls, can not be repeated infinitely. In CCG, this is done by building well-founded measures for the parameters of the recursive functions that should be proved to strictly decreasing in all possible circuits. Instead searching a combination of measures for any circuit that guarantees the impossibility of infinite recursive calls as done in CCGs, MWGs edges are labelled with square matrices whose components express relations between different measures applied to the formal and actuals parameters. In this way, the behavior of measures after executing the recursive calls associated to a path in the MWG is expressed by an specialized multiplication of the matrices labeling the edges in the path. The termination criterion in the MWG corresponds to a simple notion of positivity of the matrix associated to a given circuit. The measure matrices model the results of combination of measures of the CCG's technology in a very elegant manner making possible the formulation of simple termination criteria in MWGs. Such criteria is based on the positivity of the cycles (simple circuits) of the MWG, leading to positivity of any circuit. Two termination criteria for MWG are formalized. The correspondence between the termination in CCGs and MWGs is formalized. The specification of a simple first-order language with its semantics for termination is presented and the necessary elements to formalize the correspondence between the semantics of termination of this language and termination in MWGs.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2010. / Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2010-11-11T15:06:08Z No. of bitstreams: 1 2010_ThaynaraAriellydeLima.pdf: 425950 bytes, checksum: b13ed7f0e0a2cae760f76c7a3f7dba18 (MD5) / Approved for entry into archive by Daniel Ribeiro(daniel@bce.unb.br) on 2010-12-03T22:42:49Z (GMT) No. of bitstreams: 1 2010_ThaynaraAriellydeLima.pdf: 425950 bytes, checksum: b13ed7f0e0a2cae760f76c7a3f7dba18 (MD5) / Made available in DSpace on 2010-12-03T22:42:49Z (GMT). No. of bitstreams: 1 2010_ThaynaraAriellydeLima.pdf: 425950 bytes, checksum: b13ed7f0e0a2cae760f76c7a3f7dba18 (MD5) / Na genômica comparativa soluções algoríıtmicas eficientes para o problema da dist ância de rearranjo de genomas são uma ferramenta importante para o desenvolvimento de software que permite estabelecer relacionamento evolutivo entre organismos, por exemplo para a constr~ção de árvores filogenéticas de organismos. Existem diversas operações sobre palavras que modelam mutações ocorridas nos genes dos seres vivos (e.g. reversões, transposições, troca de blocos, etc.). Restritos à operação de reversão o problema de rearranjo de genomas ´é NP-difícil. Sendo assim, é plausível considerar algoritmos de aproximação. O algoritmo conhecido que melhor aproxima a solução do problema de rearranjo via reversões tem raio de 1.375. No seu artigo seminal, Bafna e Pevzner apresentam soluções O(n2) de raios de aproximação 1.5 para permutações com sinal e 7 4 para permutações sem sinal. Neste trabalho propõ-se um uso cuidadoso e discriminado entre as representações combinatória (palavras e grafos de pontos de quebra) e algébrica (ciclos de permuta ções) das permutações, que contribuirão para analisar com precisão e de maneira adequada diversas características do problema da distância de reversão e das soluções apresentadas por Bafna e Pevzner. _________________________________________________________________________________ ABSTRACT / Efficient algorithmic solutions to the problem of genome rearrangements in comparative genomics are an important tool for the development of software allowing one to estabilish the evolution link between organisms, for instance the construction of phylogenetic trees. There are several string operations modelling mutations occurring inside genes (e.g. reversals, transpositions and block interchange, etc.). When restricted to the reversal operation, the problem of genome rearrangement is NP-hard. Thus, polynomially bounded approximated algorithms are considered to be admissible solutions. The best known approximated algorithm to solve the rearrangement problem through reversals has approximation ratio of 1.375. In their seminal paper, Bafna and Pevzner presented O(n2) solutions of ratio 1.5 for signed permutations and 7 4 for unsigned permutations. This work proposes a careful discrimination between the combinatory (strings and breakpoint graphs) and the algebraic (cycles of permutations) representations of permutations to analyse precisely, and in an adequate way, many of the problem characteristics and solutions presented by Bafna and Pevzner.

Orientador: Claudina Izepe Rodrigues / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-26T16:45:39Z (GMT). No. of bitstreams: 1 Colombo_Jones_M.pdf: 6336447 bytes, checksum: 620030ff0cb706f37ef7c0f7947b0631 (MD5) Previous issue date: 2000 / Resumo: Neste trabalho, o objetivo foi o de estudar o problema da reconstrução para torneios com o quociente simples normal. Com este intuito, introduzimos e desenvolvemos no capítulo 1 diversos conceitos, tais como, o quociente de um torneio e mostramos que torneios hipomorfos tais que ambos sejam não simples possuem o mesmo quociente simples. No capítulo 2 introduzimos os conceitos de ciclo minimais e característico. Ao final mostramos que a existência de quociente simples normal é uma propriedade hipomorfa para torneios de ordem superior ou igual a 7. No capítulo 3 demonstramos que os torneios hamiltonianos de ordem maior ou igual a 4 que têm quociente simples normal são reconstrutíveis, se excluirmos um torneio de ordem 5 e dois de ordem 6. Além disso, no início deste capítulo verificamos que os torneios exibidos por Stockmeyer são realmente contra exemplos da conjectura da reconstrução , a qual diz que se dois torneios têm as mesmas cartas são isomorfos. E finalmente apresentamos uma análise das relações entre as classes dos torneios reconstrutíveis atualmente conhecidos(1999). / Abstract: In this work, the objective was to study the reconstruction problem for tournaments with simple normal quotient. With this intention, we introduced and developed in chapter one few concepts, so as, quotient of a tournaments which are not both simple have the same simple quotient. In chapter two we introduce the concepts of minimal and characteristic cycles, and ending this topic we show that the existence of a normal simple quotient is a hipomorphic property for tournaments of order seven or higher. In third chapter we show that hamiltonian tournaments of order four or higher which have normal simple quotient are reconstructible, if we exclude an order five and two of order six tournaments. Moreover, in the beginning of this chapter we check that tour- naments showed by Stockmeyer, be really counterexamples of reconstruction conjecture, which says that if two tournaments with the same cards are isomorphic. Finally we pre-sent and analyse the relation between the reconstruction classes atually known (1999). / Mestrado / Mestre em Matemática

Orientador : Ricardo Dahab / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-28T09:27:15Z (GMT). No. of bitstreams: 1 Silva_CandidaNunesda_M.pdf: 9020782 bytes, checksum: 72d783f2186f3848f226c74b427014de (MD5) Previous issue date: 2001 / Mestrado

Orientador: Claudina Izepe Rodrigues / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-25T18:11:42Z (GMT). No. of bitstreams: 1 Souza_MarcelaLucianoVilelade_M.pdf: 3036170 bytes, checksum: f5c4fa24e4a49364c6bef25d9978950e (MD5) Previous issue date: 1999 / Resumo: Nesta dissertação, o objetivo foi estudar o problema da reconstrução de torneios normais. Para isso, introduzimos primeiro alg,umas noções preliminares sobre a teoria de grafos orientados e torneios. Depois, vimos alguns resultados envolvendo torneios hamiltonianos e bineutros, diferença delica e característica cíelica de um torneio para posteriormente serem aplicados no resultado principal. Finalmente, mostramos os resultados essenciais para o nosso objetivo que estudam a normalidade de torneios hipomorfos e a Composição Canônica do subtorneio Pn-k. / Abstract: Not informed. / Mestrado / Mestre em Matemática