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-31T15:32:01Z (GMT). No. of bitstreams: 1
Santos_ValdomiroPlacidodos_M.pdf: 1319625 bytes, checksum: 58e1f52c8359a65ece38b62fd5fa18a2 (MD5)
Previous issue date: 2001 / Resumo: O problema da reconstrução de torneios permanece sem uma conclusão definitiva por aproximadamente quatro décadas. Este trabalho apresenta a evolução das pesquisas sobre este problema e traz também um estudo sobre os torneios de Moon, que constituem uma classe de torneios reconstrutíveis. Em 1966, Frank Harary propôs a seguinte conjectura: todo torneio de ordem n é reconstrutível a partir de suas cartas se n é suficientemente grande. A falsidade desta conjectura (conhecida como conjectura da reconstrução para torneios) foi demonstrada por Stockmeyer, em 1977. Mas, muitas classes de torneios reconstrutíveis foram caracterizadas até o momento. Nosso objetivo neste trabalho é estudar algumas destas classes. Verificamos, na secção 2, que a classe dos torneios não-hamiltonianos constitui uma classe de torneios reconstrutíveis, o que foi provado por Harary e Palmer, em 1967. Centramos nossos estudos, no entanto, na classe dos torneios de Moon, ou seja, os torneios cujos subtorneios ou são hamiltonianos ou são transitivos. Na secção 5, caracterizamos os torneios de Moon por subtorneios transitivos maximais. A partir desta caracterização é possível representar os torneios de Moon pelo seu name . Finalmente, na secção 6, usando o name verificamos que os torneios de Moon são reconstrutíveis a partir de suas cartas / Abstract: The reconstruction problem for tournaments remains without a global solution since 1966. This paper shows the evolution of searches on this problem and presents a study about Moon toumaments, which constitute a class of reconstrutible toumaments. In 1966, Frank Harary posed the reconstrution problem for toumaments by asking: is it possible to reconstruct any toumament To ITom its cards provided n is sufficient1y large? The falsity of the reconstruction conjecture for toumaments was stated by Stockmeyer, in 1977. Several classes of reconstructible toumaments were characterized since the conjecture was posed. The porpose of this paper is to show some of this classes. We verify, in section 2, that the non-hamiltonian toumaments constitute a class of reconstructible toumaments. This result was proved by Harary and Palmer, in 1967. Our main purpose in this paper is to characterize the structure of Moon tournaments, i. e., the toumaments whose subtoumaments are either hamiltonian or transitive. In section 5, we characterize the Moon toumaments by using their maximal transitive subtoumaments. With this new characterization is possible to represent Moon toumaments by using its name. Finely, in section 6, using the name, we prove that Moon toumaments are reconstructible from its cards / Mestrado / Mestre em Matemática
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/306865 |
| Date | 12 November 2001 |
| Creators | Santos, Valdomiro Placido dos |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Rodrigues, Claudina Izepe, 1953-, Kiihl, José Carlos de Souza, Leite, Paulo Ferreira |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Computação Científica, Programa de Pós-Graduação em Matemática |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 50p. : il., application/pdf |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0802 seconds