Neste trabalho, estudamos o problema de encontrar grafos extremais com rela c~ao a energia laplaciana sem sinal. Mais especi camente, procuramos grafos com a maior energia laplaciana sem sinal em determinadas classes. Nesse sentido, conjecturamos que o grafo unic clico conexo com a maior energia laplaciana sem sinal e o grafo formado por um tri^angulo com v ertices pendentes distribu dos balanceadamente e provamos parcialmente essa conjectura. Tal resultado foi provado tamb em para a energia laplaciana. Al em disso, conjecturamos que o grafo com a maior energia laplaciana sem sinal dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos. / In this work, we study the problem of nding extremal graphs with relation to the signless Laplacian energy. More speci cally, we look for graphs with the largest signless Laplacian energy inside certains classes. In this sense, we conjecture that the connected unicyclic graph with the largest signless Laplacian energy is the graph consisting of a triangle with balanced distributed pendent vertices and we partially prove this conjecture. This result was also proved for the Laplacian energy. Moreover we conjecture that the graph with the largest signless Laplacian energy among all graphs with n vertices is the complete split graph with a clique of [n+1/ 3] vertices and we prove this conjecture for some classes of graphs, in particular, for trees, for unicyclic and bicyclic graphs.

Neste trabalho, apresentamos um algoritmo que determina o número de autovalores de uma matriz simétrica qualquer que representa uma árvore, num dado intervalo real. Várias aplicações são obtidas em relação à distribuição dos autovalores da matriz laplaciana perturbada, uma matriz de representação de grafos que inclui, como casos particulares, a matriz de adjacências, a matriz laplaciana combinatória, a matriz laplaciana sem sinal e a matriz laplaciana normalizada, amplamente estudadas em Teoria Espectral de Grafos. Além disso, desenvolvemos também um algoritmo de localização de autovalores da matriz de adjacências de um grafo unicíclico. Este procedimento permite obter propriedades espectrais de grafos unicíclicos denominados centopeias unicíclicas. / In this work, we present an algorithm that computes the number of eigenvalues of any symmetric matrix that represents a tree, in a given real interval. Several applications are obtained about the distribution of the eigenvalues of the perturbed Laplacian matrix, which is a matrix representation of graphs that includes, as special cases, the adjacency matrix, the combinatorial Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix, widely studied in Spectral Graph Theory. In addition, we also develop an algorithm that locates the eigenvalues of the adjacency matrix of a unicyclic graph. This procedure allows us to obtain spectral properties of unicyclic caterpillars.

Neste trabalho, estudamos o problema de encontrar grafos extremais com rela c~ao a energia laplaciana sem sinal. Mais especi camente, procuramos grafos com a maior energia laplaciana sem sinal em determinadas classes. Nesse sentido, conjecturamos que o grafo unic clico conexo com a maior energia laplaciana sem sinal e o grafo formado por um tri^angulo com v ertices pendentes distribu dos balanceadamente e provamos parcialmente essa conjectura. Tal resultado foi provado tamb em para a energia laplaciana. Al em disso, conjecturamos que o grafo com a maior energia laplaciana sem sinal dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos. / In this work, we study the problem of nding extremal graphs with relation to the signless Laplacian energy. More speci cally, we look for graphs with the largest signless Laplacian energy inside certains classes. In this sense, we conjecture that the connected unicyclic graph with the largest signless Laplacian energy is the graph consisting of a triangle with balanced distributed pendent vertices and we partially prove this conjecture. This result was also proved for the Laplacian energy. Moreover we conjecture that the graph with the largest signless Laplacian energy among all graphs with n vertices is the complete split graph with a clique of [n+1/ 3] vertices and we prove this conjecture for some classes of graphs, in particular, for trees, for unicyclic and bicyclic graphs.

Neste trabalho, estudamos o problema de encontrar grafos extremais com rela c~ao a energia laplaciana sem sinal. Mais especi camente, procuramos grafos com a maior energia laplaciana sem sinal em determinadas classes. Nesse sentido, conjecturamos que o grafo unic clico conexo com a maior energia laplaciana sem sinal e o grafo formado por um tri^angulo com v ertices pendentes distribu dos balanceadamente e provamos parcialmente essa conjectura. Tal resultado foi provado tamb em para a energia laplaciana. Al em disso, conjecturamos que o grafo com a maior energia laplaciana sem sinal dentre todos os grafos com n v ertices e o grafo split completo com uma clique de [n+1/ 3] v ertices e provamos tal conjectura para algumas classes de grafos, em particular, para arvores, grafos unic clicos e bic clicos. / In this work, we study the problem of nding extremal graphs with relation to the signless Laplacian energy. More speci cally, we look for graphs with the largest signless Laplacian energy inside certains classes. In this sense, we conjecture that the connected unicyclic graph with the largest signless Laplacian energy is the graph consisting of a triangle with balanced distributed pendent vertices and we partially prove this conjecture. This result was also proved for the Laplacian energy. Moreover we conjecture that the graph with the largest signless Laplacian energy among all graphs with n vertices is the complete split graph with a clique of [n+1/ 3] vertices and we prove this conjecture for some classes of graphs, in particular, for trees, for unicyclic and bicyclic graphs.

Neste trabalho, apresentamos um algoritmo que determina o número de autovalores de uma matriz simétrica qualquer que representa uma árvore, num dado intervalo real. Várias aplicações são obtidas em relação à distribuição dos autovalores da matriz laplaciana perturbada, uma matriz de representação de grafos que inclui, como casos particulares, a matriz de adjacências, a matriz laplaciana combinatória, a matriz laplaciana sem sinal e a matriz laplaciana normalizada, amplamente estudadas em Teoria Espectral de Grafos. Além disso, desenvolvemos também um algoritmo de localização de autovalores da matriz de adjacências de um grafo unicíclico. Este procedimento permite obter propriedades espectrais de grafos unicíclicos denominados centopeias unicíclicas. / In this work, we present an algorithm that computes the number of eigenvalues of any symmetric matrix that represents a tree, in a given real interval. Several applications are obtained about the distribution of the eigenvalues of the perturbed Laplacian matrix, which is a matrix representation of graphs that includes, as special cases, the adjacency matrix, the combinatorial Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix, widely studied in Spectral Graph Theory. In addition, we also develop an algorithm that locates the eigenvalues of the adjacency matrix of a unicyclic graph. This procedure allows us to obtain spectral properties of unicyclic caterpillars.

Neste trabalho, apresentamos um algoritmo que determina o número de autovalores de uma matriz simétrica qualquer que representa uma árvore, num dado intervalo real. Várias aplicações são obtidas em relação à distribuição dos autovalores da matriz laplaciana perturbada, uma matriz de representação de grafos que inclui, como casos particulares, a matriz de adjacências, a matriz laplaciana combinatória, a matriz laplaciana sem sinal e a matriz laplaciana normalizada, amplamente estudadas em Teoria Espectral de Grafos. Além disso, desenvolvemos também um algoritmo de localização de autovalores da matriz de adjacências de um grafo unicíclico. Este procedimento permite obter propriedades espectrais de grafos unicíclicos denominados centopeias unicíclicas. / In this work, we present an algorithm that computes the number of eigenvalues of any symmetric matrix that represents a tree, in a given real interval. Several applications are obtained about the distribution of the eigenvalues of the perturbed Laplacian matrix, which is a matrix representation of graphs that includes, as special cases, the adjacency matrix, the combinatorial Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix, widely studied in Spectral Graph Theory. In addition, we also develop an algorithm that locates the eigenvalues of the adjacency matrix of a unicyclic graph. This procedure allows us to obtain spectral properties of unicyclic caterpillars.

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus $p$ sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. / In this thesis, we use the polyhedral approach to solve combinatorial problems in telecommunications context. First, we introduce the problem of network design with unicyclic connected components. We recall that without other constraints, our problem is easy to solve, and we propose a study with new technical constraints. We start our study by adding constraints on the size of cycles. We aim to obtain unicyclic components such that the size of each cycle is not lower than a certain p. This problem is NP-Hard. We describe some valid inequalities for the design of unicyclic graphs with girth constraints. The faces induced by these valid inequalities are also studied. Some of them can be separated in polynomial time. A cutting plane algorithm based on these inequalities is implemented to solve the problem. Furthermore, we focus on a Steiner type problem, which consists in partitioning the graph to unicyclic components, such that some given vertices belong to a cycle. We prove then that our problem is easy to solve, and we propose an exact extended formulation and a partial description of the convex hull of the incidence vectors of our Steiner network problem. Polynomial time separation algorithms are described. One of them is a generalization of the Padberg&Rao algorithm to separate blossom inequalities. Other technical constraints are proposed such as degree constraints, a bound of the number of unicyclic components, constraints related to whether some given pairs of vertices belong to the same component or to different components. Finally, we study the spectra of two specified classes of unicyclic graphs.