Orientador: Claudio Leonardo Luchesi

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

Resumo: É apresentada uma condição necessária e suficiente para que um grafo finito possua um subgrafo gerador em que cada vértice tenha seu grau num intervalo especificado. Este resultado generaliza outros obtidos por Hall e Tutte em que o intervalo de cada vértice é reduzido a um ponto. A...

Resumo: É apresentada uma condição necessária e suficiente para que um grafo finito possua um subgrafo gerador em que cada vértice tenha seu grau num intervalo especificado. Este resultado generaliza outros obtidos por Hall e Tutte em que o intervalo de cada vértice é reduzido a um ponto. A demonstração é construtiva, e obtém-se um algoritmo polinomial que determina um subgrafo que mais se aproxima num sentido bem definido, das especificações desejadas. Mostra-se ainda que ao se atribuir pesos às arestas, o problema se torna estão NP-completo.São apresentadas também algumas aplicações elementares do teorema, as quais incluem fluxos em redes e seqüências gráficas.

Abstract: A necessary and sufficient condition for a finite graph to have spanning subgraph in which the degree of each vertex lies
in a specified interval is presented. This result generalizes others that were obtained by Hall and Tutte, in which the interval of each vertex is reduced to a single...

Abstract: A necessary and sufficient condition for a finite graph to have spanning subgraph in which the degree of each vertex lies
in a specified interval is presented. This result generalizes others that were obtained by Hall and Tutte, in which the interval of each vertex is reduced to a single point. The proof is constructive and a polinomial algorithm is obtained. This algorithm determines a subgraph which in a well defined sense, is as close as possible to the desired specifications. It is shown that when we associate weights with the edges, the problem becomes NP-complete. Some direct applications of the theorem are also presented which include flows in networks and graphic sequences.