Uma generalização de fatores em graficos
AUTOR(ES)
Iara Ciurria Stavropoulou
DATA DE PUBLICAÇÃO
1982
RESUMO
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.
ASSUNTO(S)
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000048522Documentos Relacionados
- Uma generalização do problema de seleção de vertices em digrafos
- Aquisição e generalização de mandos em uma criança com autismo
- AQUISIÇÃO E GENERALIZAÇÃO DE COMPORTAMENTOS EM UMA CRIANÇA COM DIAGNÓTICO DE AUTISMO
- Uma generalização do teorema de Ljusternik-Schnirelmann.
- Uma generalização do teorema de representação de Riesz
