O espectro de grafos threshold e aplicações

Detalhes bibliográficos
Ano de defesa: 2013
Autor(a) principal: Tura, Fernando Colman
Orientador(a): Trevisan, Vilmar
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/10183/77731
Resumo: Nesta tese de doutorado estudamos uma classe de grafos denominada threshold. Iniciamos apresentando algumas caracterizações dos grafos threshold e definindo-os de uma forma apropriada para o nosso propósito. Mais especificamente, estudamos o espectro dos grafos threshold. Para isso apresentamos alguns resultados previamente conhecidos, como por exemplo, em relação à matriz de adjacência, uma redução para o cálculo do polinômio característico e a multiplicidade dos autovalores não principais. Desenvolvemos um algoritmo que constrói uma matriz diagonal D congruente a A + xI , onde A é a matriz de adjacência de um grafo threshold, x é um número real e I é a matriz identidade. Como aplicação, determinamos quantos autovalores de um grafo threshold G pertencem a um intervalo real (a, b]. A implementação do nosso algoritmo depende apenas da sequência binária de um grafo threshold e sua complexidade é de ordem O(n). Tal algoritmo é facilmente adaptado para a matriz distância Θ de um grafo threshold G. Nesta tese apresentamos aplicações desse algoritmo, como a simplicidade dos autovalores principais, a minimalidade do menor autovalor de um threshold, exibindo uma fórmula para esse menor autovalor, uma ordenação dos grafos threshold via índice, e uma classe infinita de grafos threshold com espectro integral. Além disso, apresentamos um novo algoritmo para o cálculo do polinômio característico de um grafo threshold G.