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

Simple item page
dc.creatorAgaev, Rafig
dc.creatorChebotarev, Pavel
dc.date2006-02-03
dc.date2006-02-04
dc.date.accessioned2026-07-07T07:03:05Z
dc.date.available2026-07-07T07:03:05Z
dc.descriptionWe 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.
dc.description27 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/math/0602059
dc.identifierhttp://arxiv.org/abs/math/0602059
dc.identifierAutomation and Remote Control 61 (2000) 1424--1450
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/108840
dc.subjectCombinatorics
dc.subjectData Structures and Algorithms
dc.subjectAlgebraic Geometry
dc.subject05C50; 05C05; 15A51
dc.titleThe Matrix of Maximum Out Forests of a Digraph and Its Applications
dc.typetext

Files

Collections

arXiv