Ranking graph edges by the weight of their spanning arborescences or trees

AUTOR(ES)

Boaventura-Netto, Paulo Oswaldo

FONTE

Pesquisa Operacional

DATA DE PUBLICAÇÃO

2008-04

RESUMO

Um resultado baseado em um teorema clássico da teoria dos grafos é aqui generalizado para grafos valorados, permitindo a determinação do valor total das arborescências parciais com raiz dada que contenham um arco dado, em um grafo orientado valorado. Um resultado correspondente para grafos não orientados valorados é também apresentado. Em ambos os casos, a técnica descrita permite uma hierarquização por importância das ligações do grafo, sob este critério. Esta hierarquização é proposta como uma ferramenta para determinar a importância relativa das ligações de um grafo em estudos sobre vulnerabilidade de redes. Alguns exemplos aplicados são apresentados.

ASSUNTO(S)

grafos teorema "matrix-tree" vulnerabilidade

Documentos Relacionados

• An algorithm to generate all spanning trees of a graph in order of increasing cost
• Iterative class discovery and feature selection using Minimal Spanning Trees
• MIST: Maximum Information Spanning Trees for dimension reduction of biological data sets
• Ranking vocal fold model parameters by their influence on modal frequencies
• A NOTE ON THE ENUMERATION AND LISTING OF ALL POSSIBLE TREES IN A CONNECTED LINEAR GRAPH