|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Non-surjective linear transformations of tropical matrices preserving the cyclicity indexстатья
- Авторы: Guterman Alexander, Kreines Elena, Vlasov Alexander
- Журнал: Kybernetika
- Том: 58
- Номер: 5
- Год издания: 2023
- Издательство: Akademie Ved Ceske Republiky
- Местоположение издательства: Czech Republic
- Первая страница: 691
- Последняя страница: 707
- DOI: 10.14736/kyb-2022-5-0691
- Аннотация: The cyclicity index of a matrix is the cyclicity index of its critical subgraph, namely, the subgraph of the adjacency graph which consists of all cycles of the maximal average weight. The cyclicity index of a graph is the least common multiple of the cyclicity indices of all its maximal strongly connected subgraphs, and the cyclicity index of a strongly connected graph is the least common divisor of the lengths of its (directed) cycles. In this paper we obtain the characterization of linear, possibly non-surjective, transformations of tropical matrices preserving the cyclicity index. It appears that non-bijective maps with these properties exist and all maps are exhausted by transposition, renumbering of vertices, Hadamard multiplication with a matrix of a certain special structure, and certain diagonal transformation. Moreover, only diagonal transformation can be non-bijective.
- Добавил в систему: Власов Александр Владиславович