O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.

Bounds for the signless laplacian energy

The energy of a graph G is the sum of the absolute values of the eigenvalues of the adjacency matrix of G. The Laplacian (respectively, the signless Laplacian) energy of G is the sum of the absolute values of the differences between the eigenvalues of the Laplacian (respectively, signless Laplacian) matrix and the arithmetic mean of the vertex degrees of the graph. In this paper, among some results which relate these energies, we point out some bounds to them using the energy of the line graph of G. Most of these bounds are valid for both energies, Laplacian and signless Laplacian. However, we present two new upper bounds on the signless Laplacian which are not upper bounds for the Laplacian energy. © 2010 Elsevier Inc. All rights reserved.

Resultados espectrais relacionados com a estrutura dos grafos

Nesta tese são estabelecidas novas propriedades espectrais de grafos com estruturas específicas, como sejam os grafos separados em cliques e independentes e grafos duplamente separados em independentes, ou ainda grafos com conjuntos (κ,τ)-regulares. Alguns invariantes dos grafos separados em cliques e independentes são estudados, tendo como objectivo limitar o maior valor próprio do espectro Laplaciano sem sinal. A técnica do valor próprio é aplicada para obter alguns majorantes e minorantes do índice do espectro Laplaciano sem sinal dos grafos separados em cliques e independentes bem como sobre o índice dos grafos duplamente separados em independentes. São fornecidos alguns resultados computacionais de modo a obter uma melhor percepção da qualidade desses mesmos extremos. Estudamos igualmente os grafos com um conjunto (κ,τ)-regular que induz uma estrela complementar para um valor próprio não-principal $. Além disso, é mostrado que $=κ-τ. Usando uma abordagem baseada nos grafos estrela complementares construímos, em alguns casos, os respectivos grafos maximais. Uma caracterização dos grafos separados em cliques e independentes que envolve o índice e as entradas do vector principal é apresentada tal como um majorante do número da estabilidade dum grafo conexo.