O problema da reconstrução dos torneios com quociente simples normal

• Autor(es): Colombo, Jones
• Data: 2000
• Identificador Persistente: https://hdl.handle.net/20.500.12733/1588721
• Origem: Oasisbr
• Assunto(s): Torneios; Teoria dos grafos hamiltonianos
• Tipo de Documento: Dissertação de mestrado
• Idioma: Português

Descrição

Orientador: Claudina Izepe Rodrigues

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica

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