Матрица максимальных исходящих лесов орграфа и ее применения

Исследованы свойства максимальных исходящих лесов орграфа (в общем случае – взвешенного), а также свойства соответствующей им матрицы. Рассмотрены цепи Маркова, связанные с взвешенным орграфом и доказано, что матрица предельных средних вероятностей такой цепи совпадает с нормированной матрицей максимальных исходящих лесов. Тем самым получена интерпретация матрицы предельных средних вероятностей произвольной конечной стационарной цепи Маркова в терминах веса максимальных исходящих лесов. Описаны применения исследуемой матрицы и транспонированной к ней матрицы предельных достижимостей орграфа в задачах агрегирования предпочтений, измерения близости вершин взвешенного орграфа и выявления его структуры.