Coincidências: Problema dos aniversários e polinômios cromáticos (2019)
- Authors:
- Autor USP: AMATO NETO, LUIS - EACH
- Unidade: EACH
- Subjects: REDES COMPLEXAS; SISTEMAS DISCRETOS; POLINÔMIOS
- Keywords: Birthday problem; Chromatic polynomials; Coincidences; Coincidências; Polinômios cromáticos; Problema dos aniversários
- Language: Português
- Abstract: Como discutido em Diaconis e Mosteller (1989), o problema dos aniversários é um ponto importante de partida no estudo de coincidências. Uma definição de coincidência é adotada, seguida de uma breve apresentação dos seus principais aspectos: entre eles a subjetividade e a surpresa. Na literatura são encontradas as principais variações do problema dos aniversários, que analisadas, fornecem as bases para um estudo do aspecto probabilístico das coincidências. Neste trabalho os eventos são associados a variáveis aleatórias independentes e igualmente distribuídas, ou seja, os problema são estudados por técnicas de contagem. Desta forma o problema clássico dos aniversários pode ser associado à coloração dos vértices de um grafo completo, assim como o problema do aniversariante pode ser associado à coloração dos vértices de um grafo estrela. A partir destas observações, é proposta a formulação de problema dos aniversários sujeito a restrições de uma rede de relacionamentos, que equivale a um problema da coloração própria dos vértices de um grafo simples, cuja topologia modela as restrições do problema original. O objetivo do trabalho é aplicar o conhecimento desenvolvido sobre polinômios cromáticos no estudo das coincidências associadas a problemas dos aniversários sujeito a restrições... (Continua)(Continuação) Um resumo sobre teoria dos grafos e os principais resultados referentes a polinômios cromáticos são apresentados com o objetivo de dar clareza e consistência entre definições adotadas, teoremas utilizados e sua aplicação nos casos de árvores de Cayley, grafos Bollobas-Chung e redes sociais simples. A análise das coincidências se concentra na determinação do polinômio cromático e suas representações em diferentes bases, entre elas as formas: de potência, fatorial e de árvore. A decisão se um grafo pode ou não ser colorido de maneira própria com k > 2 cores é um problema de decisão NP-completo, portanto um objetivo secundário é analisar as limitações dos algoritmos existentes e dos sistemas disponíveis para de calculo de polinômios cromáticos, que possuem coeficientes inteiros e podem alcançar centenas de dígitos. Os cálculos e as simulações foram realizadas no Sage Mathematics Software (Linux Version 8.8). A conclusão demonstra que o conhecimento e as técnicas de polinômios cromáticos contribuem com a solução da generalização proposta do problema dos aniversários, sendo analisadas as limitações atuais quanto à eficácia dos algoritmos disponíveis e a capacidade computacional demandada pela topologia do grafo associado ao problema original
- Imprenta:
- Data da defesa: 10.12.2019
-
ABNT
AMATO NETO, Luis. Coincidências: Problema dos aniversários e polinômios cromáticos. 2019. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2019. Disponível em: https://www.teses.usp.br/teses/disponiveis/100/100132/tde-07022020-121851/. Acesso em: 25 set. 2024. -
APA
Amato Neto, L. (2019). Coincidências: Problema dos aniversários e polinômios cromáticos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/100/100132/tde-07022020-121851/ -
NLM
Amato Neto L. Coincidências: Problema dos aniversários e polinômios cromáticos [Internet]. 2019 ;[citado 2024 set. 25 ] Available from: https://www.teses.usp.br/teses/disponiveis/100/100132/tde-07022020-121851/ -
Vancouver
Amato Neto L. Coincidências: Problema dos aniversários e polinômios cromáticos [Internet]. 2019 ;[citado 2024 set. 25 ] Available from: https://www.teses.usp.br/teses/disponiveis/100/100132/tde-07022020-121851/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
