Algoritmos para encontrar anéis cromáticos em redes de parentesco

Abstract

O trabalho tem como objetivo possibilitar a verificação de hipóteses sobre povos através da disponibilização de anéis cromáticos derivados de redes reais. Para isto, foi definido a utilização de grafos para representação das redes de parentesco reais. Um modo de colorir vértices deste grafo foi proposto com base em uma hipótese antropológica. Também foram propostos algoritmos que calculam propriedades derivadas das cores. Utilizando as propriedades obtidas, o trabalho desenvolveu formas de enumerar anéis cromáticos, implementando cada uma delas para execuções sequenciais e paralelas. Uma análise sobre o tempo de execução das buscas implementadas foi realizada sobre a rede real Arara. Uma análise numérica dos resultados também foi realizada sobre os 520 anéis com uma afinidade e 110590 anéis com duas afinidades encontrados para a rede.

The goal of this work is to enable the verification of hypotheses about people by providing chromatic rings obtained from real networks. To achieve this goal, the use of graphs to represent real kinship networks was defined. A way of coloring vertices of this graph was proposed based on an anthropological hypothesis. Algorithms that calculate properties derived from colors have also been proposed. Using this properties, the work developed ways of enumerate all the chromatic rings, implementing each one to execute sequentially and parallelaly. An analysis of the execution time of the implemented searches was carried out on the Arara network, a real network. An analysis of numeric results was also performed on the 520 rings with one affinity and 110590 rings with two affinities found on the network.