Sobre quadrados mágicos, grafos graciosos e colorações especiais: teoremas, algoritmos e aplicações
Resumo
Neste trabalho foram investigados problemas de rotulação em grafos, que consistem em atribuir rótulos, geralmente números inteiros, a vértices ou arestas, ou ambos, de modo a respeitar alguma restrição. Grafos rotulados incluem os grafos mágicos, grafos graciosos e colorações com restrições de distâncias. Quadrados mágicos podem ser modelados como grafos bipartidos completos, que por sua vez podem ter uma rotulação graciosa. Tal rotulação pode ser vista como um caso particular de coloração de vértices que respeita certa restrição de distância. Estas correlações foram exploradas nesta pesquisa, sendo reescritas em detalhes as provas dos principais teoremas, bem como implementados algoritmos de reconhecimento e determinação de soluções factíveis - exato e heurísticas gulosas, com uso do benchmark DIMACS. A prova da NP-completude para coloração com distâncias iguais é apresentada.
Referências
Arsie, K. C. (2010). Jogos sudoku e quadrado mágico. Master’s thesis, Universidade Federal do Paraná.
Beavers, B. (2001). Golomb rulers and graceful labeling. Loisiana State University.
Dias, B. R. C., de Freitas Rodrigues, R., and Filho, N. M. (2012). Alocação de canais em redes celulares sem fio: algoritmos e modelos teóricos em grafos e escalonamento. In SBPO - Simpósio Brasileiro de Pesquisas Operacionais.
dos Santos, C. P., Neto, J. P., and Silva, J. N. (2007). Os quadrados latinos + Puzzle Hexágono Mágico. Edimpresa.
Drury, N. (1992). Dictionary of Mysticism and the Esoteric Traditions. Bridport, Dorset: Prism Press.
Fang, W. (2010). A computational approach to the graceful tree conjecture.
Feofiloff, P., Kohayakawa, Y., and Wakabayashi, Y. (2011). Uma Introdução Sucinta à Teoria dos Grafos. Universidade de São Paulo.
Gallian, J. A. (2015). A dynamic survey of graph labeling. The Electronic Journal of Combinatorics.
Garey, M. and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
Ghersi, I. I. (1921). Matematica Dilettevole e Curiosa. Ulrico Hoepli, Milan, Italy.
Golomb, S. W. (1974). The largest graceful subgraph of the complete graph. The American Mathematical Monthly, 81(5):499–501.
Kosowski, A. and Manuszewski, K. (2004). Classical coloring of graphs. Contemporary Mathematics.
Nishad, T. M. (2012). Application of strong graphs in wireless networks. International Journal of Scientific and Engineering Research.
Roberts, G. E. (2015). Composing with numbers: Sir peter maxwell davies and magic squares. Math, Music and Identity.
Rosa, A. (1967). On certain valuations of the vertices of a graph. Theory of Graphs (Internat. Symposium, Rome, July 1966).
Trick, M. (2004). Graph coloring and its generalizations. http://mat.gsia.cmu.edu/COLOR03/. Acesso em: 04/2016.
Watson, R. L. (1972). A survey on the graceful labeling of graphs. Master’s thesis, Roanoke College.
