Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306865
Type: TESE
Title: Reconstrução dos torneios de Moon
Author: Santos, Valdomiro Placido dos
Advisor: Rodrigues, Claudina Izepe, 1953-
Abstract: 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
Subject: Torneios
Teoria dos grafos hamiltonianos
Language: Português
Editor: [s.n.]
Date Issue: 2001
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Santos_ValdomiroPlacidodos_M.pdf1.29 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.