Counting Forests for the Analysis of Structures

The matrices of spanning rooted forests are studied as a tool for analysing the structure of digraphs. The problems of finding the basis bicomponents and the reachability relation, measuring vertex accessibility, and ranking from preference relations / sports competitions are considered. It is shown that the vertex accessibility measure based on spanning forests satisfies a number of characteristic conditions. An interpretation of forest matrices in terms of information dissemination is proposed