Códigos de identificação de densidade mínima na grade hexagonal com número finito de linhas (2024)
- Authors:
- Autor USP: SOBRAL, GABRIEL AUGUSTO GONÇALVES - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/T.45.2024.tde-18092024-200458
- Subjects: TEORIA DA INFORMAÇÃO; TEORIA DA COMUNICAÇÃO; TEORIA DOS GRAFOS; OTIMIZAÇÃO COMBINATÓRIA
- Keywords: Código de identificação; Densidade mínima; Grade hexagonal com número finito de linhas; Hexagonal grid with finite number of rows; Identifying code; Minimum density
- Agências de fomento:
- Language: Português
- Abstract: Num grafo G, um conjunto de vértices C ⊆ V (G) é um código de identificação se, para cada vértice de G, a vizinhança fechada N[v] de v intersecta C, e para quaisquer vértices distintos u e v em G, temos que N[u]∩C ≠ N[v] ∩ C. Nesta tese, investigamos códigos de identificação da grade hexagonal (infinita) com k linhas, denotada por Hk. Estamos interessados em encontrar para cada k um código de identificação de Hk com a menor densidade possível, denotada por d*(Hk). Em muitas grades infinitas, é usado o método da descarga para provar limites inferiores para a densidade mínima de códigos de identificação. Não encontramos na literatura uma formalização satisfatória a respeito da aplicação desse método em grafos infinitos. Apresentamos aqui essa formalização, e mostramos que se um grafo não satisfaz certas propriedades, a aplicação do método da descarga pode levar a resultados errôneos. Usamos este método para provar que d*(Hk) ≥ 2/5 para todo k, e que d*(H2) = 9/20. Também provamos que existe um único código de identificação periódico na grade H2 com densidade 9/20. É fácil provar que d*(H1) = 1/2. Para as grades hexagonais de 3 a 5 linhas, usamos o conceito de grafo de configurações e implementamos um programa baseado neste conceito para mostrar que d*(H3) = 6/13 ≈ 0, 461538, d*(H4) = 7/16 = 0, 4375 e d*(H5) = 11/25 = 0, 44. Para as grades hexagonais com mais do que 5 linhas, mostramos que d*(H6) ≤ 47/108 ≈ 0, 43518, d*(H7p)≤ 3/7 ≈ 0, 428571, onde p é um natural positivo, e d*(H7p+r ) ≤ 3/7 + (r/(7p + r))(d*(Hr ) - 3/7) para r ∈ [6]. Também provamos que a grade Hk é r-identificável, tem um (r, ≤ 2)-código de identificação e não tem um (r, ≤ ℓ)-código de identificação, para k ≥ 1, r ≥ 1 e ℓ ≥ 3. Estudos sobre a densidade mínima de códigos de identificação na grade hexagonal sem restrição quanto ao número de linhas (e colunas) vêm sendo realizados há mais de 20 anos, já os resultados que provamos para a grade hexagonal Hk não foram tratados antes na literatura
- Imprenta:
- Data da defesa: 17.07.2024
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
SOBRAL, Gabriel Augusto Gonçalves. Códigos de identificação de densidade mínima na grade hexagonal com número finito de linhas. 2024. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2024. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-18092024-200458/. Acesso em: 21 fev. 2026. -
APA
Sobral, G. A. G. (2024). Códigos de identificação de densidade mínima na grade hexagonal com número finito de linhas (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-18092024-200458/ -
NLM
Sobral GAG. Códigos de identificação de densidade mínima na grade hexagonal com número finito de linhas [Internet]. 2024 ;[citado 2026 fev. 21 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-18092024-200458/ -
Vancouver
Sobral GAG. Códigos de identificação de densidade mínima na grade hexagonal com número finito de linhas [Internet]. 2024 ;[citado 2026 fev. 21 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-18092024-200458/
Informações sobre o DOI: 10.11606/T.45.2024.tde-18092024-200458 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
