Uma generalização de fatores em graficos
Iara Ciurria Stavropoulou
DISSERTAÇÃO
Português
T/UNICAMP St29g
Campinas, SP : [s.n.], 1982.
90 f. : il.
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...
Ver mais
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.
Ver menos
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... Ver mais 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. Ver menos
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... Ver mais 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. Ver menos
Uma generalização de fatores em graficos
Iara Ciurria Stavropoulou
Uma generalização de fatores em graficos
Iara Ciurria Stavropoulou
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra