The Matrix of Maximum Out Forests of a Digraph and Its Applications

Details The Matrix of Maximum Out Forests of a Digraph and Its Applications The Matrix of Maximum Out Forests of a Digraph and Its Applications

2006-02-03

arxiv.org/abs/math/0602059v2

Automation and Remote Control 61 (2000) 1424--1450

Mathematics

Combinatorics

27 pages, 3 figures

Scientific paper

We study the maximum out forests of a (weighted) digraph and the matrix of maximum out forests. A maximum out forest of a digraph G is a spanning subgraph of G that consists of disjoint diverging trees and has the maximum possible number of arcs. If a digraph contains any out arborescences, then maximum out forests coincide with them. We provide a new proof to the Markov chain tree theorem saying that the matrix of Ces`aro limiting probabilities of an arbitrary stationary finite Markov chain coincides with the normalized matrix of maximum out forests of the weighted digraph that corresponds to the Markov chain. We discuss the applications of the matrix of maximum out forests and its transposition, the matrix of limiting accessibilities of a digraph, to the problems of preference aggregation, measuring the vertex proximity, and uncovering the structure of a digraph.

Affiliated with

Also associated with

No associations

Rating

The Matrix of Maximum Out Forests of a Digraph and Its Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Matrix of Maximum Out Forests of a Digraph and Its Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Matrix of Maximum Out Forests of a Digraph and Its Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-485127