Neste trabalho tratamos de um problema clássico bem conhecido em Teoria dos Grafos: o problema da existência de um ciclo hamiltoniano. Um grafo é dito hamiltoniano se possui um ciclo hamiltoniano, ou seja, apresenta um ciclo que percorre todos os vértices do grafo. Estudamos problemas clássicos associados a este problema em termos do número de arestas, do grau mínimo e da sequência de graus dos vértices de um grafo. Além disso, estudamos resultados espectrais para o problema de hamiltonicidade referentes às matrizes de adjacências e laplaciana. A principal contribuição deste trabalho é a apresentação detalhada de condições suficientes e condições necessárias que garantem um ciclo hamiltoniano em um grafo já existentes na bibliografia. / In this work we study a well-known problem in Graph Theory: the existence of a Hamilton cycle, namely a cycle that goes through every vertex in the graph. We consider classical su cient conditions related with this problem in terms of the number of edges, the minimum degree and the vertex degree sequence of a graph. Furthermore, we study spectral results for the hamiltonian problem in terms of the adjacency and laplacian matrix. The main contribution of this work is our detailed presentation of necessary and su cient conditions for the existence of a Hamilton cycle in a graph.

Neste trabalho tratamos de um problema clássico bem conhecido em Teoria dos Grafos: o problema da existência de um ciclo hamiltoniano. Um grafo é dito hamiltoniano se possui um ciclo hamiltoniano, ou seja, apresenta um ciclo que percorre todos os vértices do grafo. Estudamos problemas clássicos associados a este problema em termos do número de arestas, do grau mínimo e da sequência de graus dos vértices de um grafo. Além disso, estudamos resultados espectrais para o problema de hamiltonicidade referentes às matrizes de adjacências e laplaciana. A principal contribuição deste trabalho é a apresentação detalhada de condições suficientes e condições necessárias que garantem um ciclo hamiltoniano em um grafo já existentes na bibliografia. / In this work we study a well-known problem in Graph Theory: the existence of a Hamilton cycle, namely a cycle that goes through every vertex in the graph. We consider classical su cient conditions related with this problem in terms of the number of edges, the minimum degree and the vertex degree sequence of a graph. Furthermore, we study spectral results for the hamiltonian problem in terms of the adjacency and laplacian matrix. The main contribution of this work is our detailed presentation of necessary and su cient conditions for the existence of a Hamilton cycle in a graph.

Neste trabalho tratamos de um problema clássico bem conhecido em Teoria dos Grafos: o problema da existência de um ciclo hamiltoniano. Um grafo é dito hamiltoniano se possui um ciclo hamiltoniano, ou seja, apresenta um ciclo que percorre todos os vértices do grafo. Estudamos problemas clássicos associados a este problema em termos do número de arestas, do grau mínimo e da sequência de graus dos vértices de um grafo. Além disso, estudamos resultados espectrais para o problema de hamiltonicidade referentes às matrizes de adjacências e laplaciana. A principal contribuição deste trabalho é a apresentação detalhada de condições suficientes e condições necessárias que garantem um ciclo hamiltoniano em um grafo já existentes na bibliografia. / In this work we study a well-known problem in Graph Theory: the existence of a Hamilton cycle, namely a cycle that goes through every vertex in the graph. We consider classical su cient conditions related with this problem in terms of the number of edges, the minimum degree and the vertex degree sequence of a graph. Furthermore, we study spectral results for the hamiltonian problem in terms of the adjacency and laplacian matrix. The main contribution of this work is our detailed presentation of necessary and su cient conditions for the existence of a Hamilton cycle in a graph.

Made available in DSpace on 2014-06-12T18:31:25Z (GMT). No. of bitstreams: 2 arquivo7664_1.pdf: 826523 bytes, checksum: 137f501d35ab75799fa17d1aae25d76b (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 1990 / Esta dissertação se propõe a explorar o artigo intitulado Matroids induced by packing wheited subgraphs de M. Lemos. Apresentamos, baseado no artigo de M. Loebl e S. Poljak, On Matroids induced by packing subgraphs, uma família F, de subgrafos de G que preservam a propriedade de o conjunto dos vértices cobertos por algum F-empacotamento gerarem uma matróide. Introduzimos os conceitos de família hipoemparelhável, H, e família fechada de propulsores enraizados , e mostramos que se F = H[, os conjuntos dos vértices dos F,-empacotamentos de peso máximo de uma matróide, com pequenas restrições à função peso, formam uma matróide

Submitted by Pedro Barros (pedro.silvabarros@ufpe.br) on 2018-10-02T22:18:32Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TESE Antonio José Ferreira Gomes Junior.pdf: 795094 bytes, checksum: 529f11681a4d9bb3ee2869e50d35e58f (MD5) / Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-11-22T22:30:27Z (GMT) No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TESE Antonio José Ferreira Gomes Junior.pdf: 795094 bytes, checksum: 529f11681a4d9bb3ee2869e50d35e58f (MD5) / Made available in DSpace on 2018-11-22T22:30:27Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TESE Antonio José Ferreira Gomes Junior.pdf: 795094 bytes, checksum: 529f11681a4d9bb3ee2869e50d35e58f (MD5) Previous issue date: 2013-08-13 / CAPES / Manoel Lemos em seu artigo “Elements belonging to triads in 3-connected matroids” (2004) estabeleceu uma cota inferior para o número de elementos cobertos por triângulos em uma matróide cominimalmente 3-conexa com uma quantidade suficientemente grande de elementos, em função de sua quantidade de elementos. No seu artigo “On the number of triangles in 3-connected matrids” (2007) mostrou uma cota semelhante para o número de triângulos desse tipo de matróide. Ele ainda, em ambos os casos, encontrou uma família infinita de matróides que atingiam tais cotas. Assim, motivados por esses artigos, adicionamos ao problema a hipótese da matróide ser binária e construímos algumas matróides com uma pequena quantidade de elementos, satisfazendo essas condições, que foram utilizadas em decomposições necessárias para as demonstrações de resultados similares aos dos artigos de Lemos. Além disso, também encontramos, em ambos os casos, uma família infinita de matróides compostas pelas criadas para a decomposição que atingem o limite dessas cotas, mostrando que os resultados obtidos são os melhores possíveis. / Manoel Lemos in his article “Elements belonging do triads in 3-connected matroids” (2004) established a lower bound for the number of elements covered by triangles in a cominimally 3-connected matroid with a sufficiently large number of elements, depending on their amount of elements. In his article “On the number of triangles in 3-connected matrids” (2007) he showed a similar quota for the number of triangles of this type of matroid. He still, in both cases, found an endless family of matroids who reached such heights. Thus, motivated by these articles, we add to the problem the hypothesis of the matroid being binary and we construct some matroids with a small amount of elements, satisfying these conditions, that were used in necessary decompositions for the demonstrations of results similar to the articles of Lemos. In addition, we also find in both cases an infinite family of matroids composed by the maids for decomposition that reach the limit of these dimensions, showing that the obtained results are the best possible.

Neste trabalho, examinamos detalhadamente um procedimento de análise, introduzido em [21] e desenvolvido em [11] e [18], para a investigação dos erros em malhas arbitrárias, decorrentes de métodos discretos (diferenças finitas e elementos finitos) de segunda ordem para problemas de Sturm-Liouville regulares, com condições de contorno tipo Dirichlet, Neumann ou Robin (ou combinações destas). Esta análise nos permite obter estimativas finas sobre erros de solução e derivadas de primeira e segunda ordens. Aplicamos o procedimento em detalhe para o exame do método mimético discutido em [21] e do método de elementos finitos considerado em [18] e [11] (método de Galerkin com elementos seccionalmente lineares). Em particular, fenômenos de supraconvergência em ambos os métodos são observados e explicados facilmente a partir das estimativas desenvolvidas. / In the present work, we give a detailed discussion of the errar analysis intraduced in [21], and further developed in [11] and [18], of 2nd-order discrete methods (both finite-difference and finite element methods are considered here) for one-dimensional Sturm- Liouville problems with separated boundary conditions of Dirichlet, Neumann, or Robin type (or combinations of these). Such an analysis yields very precise estimates for both solution and derivative errors in the approximations. Application is given to the analysis of the mimetic method discussed in [21], and the standard 2nd-order Galerkin method [18], [11] with piecewise linear elements. In particular, supraconvergence effects are clearly explained based on the estimates obtained by the theory.

Neste trabalho, examinamos detalhadamente um procedimento de análise, introduzido em [21] e desenvolvido em [11] e [18], para a investigação dos erros em malhas arbitrárias, decorrentes de métodos discretos (diferenças finitas e elementos finitos) de segunda ordem para problemas de Sturm-Liouville regulares, com condições de contorno tipo Dirichlet, Neumann ou Robin (ou combinações destas). Esta análise nos permite obter estimativas finas sobre erros de solução e derivadas de primeira e segunda ordens. Aplicamos o procedimento em detalhe para o exame do método mimético discutido em [21] e do método de elementos finitos considerado em [18] e [11] (método de Galerkin com elementos seccionalmente lineares). Em particular, fenômenos de supraconvergência em ambos os métodos são observados e explicados facilmente a partir das estimativas desenvolvidas. / In the present work, we give a detailed discussion of the errar analysis intraduced in [21], and further developed in [11] and [18], of 2nd-order discrete methods (both finite-difference and finite element methods are considered here) for one-dimensional Sturm- Liouville problems with separated boundary conditions of Dirichlet, Neumann, or Robin type (or combinations of these). Such an analysis yields very precise estimates for both solution and derivative errors in the approximations. Application is given to the analysis of the mimetic method discussed in [21], and the standard 2nd-order Galerkin method [18], [11] with piecewise linear elements. In particular, supraconvergence effects are clearly explained based on the estimates obtained by the theory.

Neste trabalho, examinamos detalhadamente um procedimento de análise, introduzido em [21] e desenvolvido em [11] e [18], para a investigação dos erros em malhas arbitrárias, decorrentes de métodos discretos (diferenças finitas e elementos finitos) de segunda ordem para problemas de Sturm-Liouville regulares, com condições de contorno tipo Dirichlet, Neumann ou Robin (ou combinações destas). Esta análise nos permite obter estimativas finas sobre erros de solução e derivadas de primeira e segunda ordens. Aplicamos o procedimento em detalhe para o exame do método mimético discutido em [21] e do método de elementos finitos considerado em [18] e [11] (método de Galerkin com elementos seccionalmente lineares). Em particular, fenômenos de supraconvergência em ambos os métodos são observados e explicados facilmente a partir das estimativas desenvolvidas. / In the present work, we give a detailed discussion of the errar analysis intraduced in [21], and further developed in [11] and [18], of 2nd-order discrete methods (both finite-difference and finite element methods are considered here) for one-dimensional Sturm- Liouville problems with separated boundary conditions of Dirichlet, Neumann, or Robin type (or combinations of these). Such an analysis yields very precise estimates for both solution and derivative errors in the approximations. Application is given to the analysis of the mimetic method discussed in [21], and the standard 2nd-order Galerkin method [18], [11] with piecewise linear elements. In particular, supraconvergence effects are clearly explained based on the estimates obtained by the theory.

Made available in DSpace on 2014-06-12T18:33:40Z (GMT). No. of bitstreams: 2 arquivo934_1.pdf: 678753 bytes, checksum: af8d8f157b72162d2a4446bf7978c0c6 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Universidade Federal de Pernambuco / O Polinômio de Tutte generaliza alguns polinômios usados para contar estruturas em grafos, tais como colorações e fluxos. Não obstante, é mais naturalmente definido para matróides. Em termos mais formais, é essencialmente o único invariante polinomial com comportamento multiplicativo para soma direta de matróides ou uniões disjuntas de grafos conexos. Adicionando alguma complexidade em sua formulação, é possível capturar nele as simetrias de um grafo por um argumento de contagem de órbitas de grupos. Com outro viés, é possível codificar algebricamente uma matróide atribuindo pesos para os seus elementos ao construirmos uma variação do Polinômio de Tutte, o que resulta praticamente na função de partição do modelo de Potts

ARARUMA Arthur Rodrigues. Caminho mínimo com restrição probabilística de atraso máximo. 2013. 89 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T19:26:26Z No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T13:35:18Z (GMT) No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Made available in DSpace on 2016-07-13T13:35:18Z (GMT). No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) Previous issue date: 2013 / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem. / No problema do Caminho Mínimo com Restrição Probabilística de Atraso Máximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viárias a custo mínimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observá-lo tendo em mente estratégias de qualidade de serviço, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da área de otimização em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual não tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeração de partições do espaço de soluções do problema, que utiliza uma decomposição em L para selecionar partições de forma inteligente, e que é auxiliado por soluções de relaxações do problema de forma a obter cotas para o custo ótimo. Além disso, desenvolvemos algumas estratégias de ramificação e de poda para um esquema de Branch-and-Bound, com uma fase de pré-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparação em instâncias de menor porte para o problema. Para as demais instâncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessário para a resolução.