Matrices of Forests and the Analysis of Digraphs
Chebotarev, Pavel · Agaev, Rafig
Original · EN
The matrices of spanning rooted forests are studied as a tool for analysing the structure of digraphs and measuring their characteristics. The problems of revealing the basis bicomponents, measuring vertex proximity, and ranking from preference relations / sports competitions are considered. It is shown that the vertex accessibility measure based on spanning forests has a number of desirable properties. An interpretation for the normalized matrix of out-forests in terms of information dissemination is given. Keywords: Laplacian matrix, spanning forest, matrix-forest theorem, proximity measure, bicomponent, ranking, incomplete tournament, paired comparisons
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.