CÓDIGOS DE IDENTIFICAÇÃO E DENSIDADE MÍNIMA EM GRAFOS TIPO GRADE HEXAGONAIS

Resumen

No trabalho em questão foram estudados códigos de identificação para grafos do tipo grade com número limitado de linhas, mas com infinitas colunas. Entre as grades estudadas, destacam-se as grades triangulares, as grades King e as grades hexagonais. Diversos artigos sobre o tema e os métodos a serem aplicados ao lidar com problemas dessa área foram consultados e lidos. Destaca-se, principalmente, o uso do método da descarga para achar códigos com densidade mínima para grades triangulares e grades King. Como todo grafo G, uma grade é formada por um conjunto de vértices V(G) e um conjunto de arestas E(G). Dado um subconjunto C ⊆ V (G) e um vértice v do grafo G, seja C[v] o conjunto dos vizinhos de v que estão em C. Um código de identificação de G é um conjunto C ⊆ V (G) tal que: todo vértice v de V(G) tem C[v] não vazio e, para cada dois vértices distintos u e v, C[u] é diferente de C[v]. Se C é um código de identificação, dizemos que C[v] é o código de v. Durante o decorrer do trabalho, foram estudadas as provas da densidade mínima 9/20 para código de identifcação da grade H(2) - grade hexagonal com duas linhas. Para outras grades, desenvolveu-se uma técnica para obter densidades mínimas com o auxílio do computador. Provou-se que para as grades hexagonais H(3) e H(3B) com 3 linhas a densidade mínima é 6/13 e 11/25 respectivamente. Tais valores foram obtidos a partir de um algorítmo criado para rodar códigos possíveis para grids de duas linhas, 3 linhas e até 4 linhas. Também se usou o algorítmo de Floyd para detectar ciclos negativos e, logo, garantir a minimalidade da densidade de tais códigos. Nota-se que o tema em voga tem sido discutido em muitos trabalhos a nível nacional e internacional, portanto, podemos dizer que o trabalho aqui apresentado se propõe a ilustrar novos resultados dentro da teoria de grafos. Espera-se que esse trabalho sirva de referência para achar valores mínimos para densidade de códigos de identificação em outros tipos de grades.