Reconstrução dos torneios de Moon
AUTOR(ES)
Valdomiro Placido dos Santos
DATA DE PUBLICAÇÃO
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
ASSUNTO(S)
teoria dos grafos hamiltonianos torneios
