期刊文献+

On an Invariant of Tournament Digraphs

On an Invariant of Tournament Digraphs
下载PDF
导出
摘要 To date, it is unknown whether it is possible to construct a complete graph invariant in polynomial time, so fast algorithms for checking non-isomorphism are important, including heuristic algorithms, and for successful implementations of such heuristics, both the tasks of some modification of previously described graph invariants and the description of new invariants remain relevant. Many of the described invariants make it possible to distinguish a larger number of graphs in the real time of a computer program. In this paper, we propose an invariant for a special kind of directed graphs, namely, for tournaments. The last ones, from our point of view, are interesting because when fixing the order of vertices, the number of different tournaments is exactly equal to the number of undirected graphs, also with fixing the order of vertices. In the invariant we are considering, all possible tournaments consisting of a subset of vertices of a given digraph with the same set of arcs are iterated over. For such subset tournaments, the places are calculated in the usual way, which are summed up to obtain the final values of the points of the vertices;these points form the proposed invariant. As we expected, calculations of the new invariant showed that it does not coincide with the most natural invariant for tournaments, in which the number of points is calculated for each participant. So far, we have conducted a small number of computational experiments, and the minimum value of the pair correlation between the sequences representing these two invariants that we found is for dimension 15. To date, it is unknown whether it is possible to construct a complete graph invariant in polynomial time, so fast algorithms for checking non-isomorphism are important, including heuristic algorithms, and for successful implementations of such heuristics, both the tasks of some modification of previously described graph invariants and the description of new invariants remain relevant. Many of the described invariants make it possible to distinguish a larger number of graphs in the real time of a computer program. In this paper, we propose an invariant for a special kind of directed graphs, namely, for tournaments. The last ones, from our point of view, are interesting because when fixing the order of vertices, the number of different tournaments is exactly equal to the number of undirected graphs, also with fixing the order of vertices. In the invariant we are considering, all possible tournaments consisting of a subset of vertices of a given digraph with the same set of arcs are iterated over. For such subset tournaments, the places are calculated in the usual way, which are summed up to obtain the final values of the points of the vertices;these points form the proposed invariant. As we expected, calculations of the new invariant showed that it does not coincide with the most natural invariant for tournaments, in which the number of points is calculated for each participant. So far, we have conducted a small number of computational experiments, and the minimum value of the pair correlation between the sequences representing these two invariants that we found is for dimension 15.
作者 Boris F. Melnikov Bowen Liu Boris F. Melnikov;Bowen Liu(Faculty of Computational Mathematics and Cybernetics, Shenzhen MSU-BIT University, Shenzhen, China)
出处 《Journal of Applied Mathematics and Physics》 2024年第7期2711-2722,共12页 应用数学与应用物理(英文)
关键词 GRAPH Directed Graph TOURNAMENT ?nvariant Graph Directed Graph Tournament ?nvariant
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部