Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306867
Type: TESE
Title: Uma generalização de fatores em graficos
Author: Stavropoulou, Iara Ciurria, 1952-
Advisor: Lucchesi, Cláudio Leonardo, 1945-
Luchesi, Claudio Leonardo
Abstract: 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 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.
Subject: Teoria dos grafos
Language: Português
Editor: [s.n.]
Date Issue: 1982
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Stavropoulou_IaraCiurria_M.pdf1.46 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.