Построение минимальных вершинных расширений графа путём объединения его изоморфных копий
Herald of Tver State University. Series: Applied Mathematics · 29.05.2026 · (1(80)) · 79-88
DOI: 10.26456/vtpmk759 ↗Kurz gefasst
Fachartikel in der Zeitschrift Herald of Tver State University. Series: Applied Mathematics, erschienen am 29.05.2026. Verfasst von Александр Андреевич Лобов. Die Arbeit nennt 14 Literaturangaben.
Abstract (Originalsprache)
Гиперкуб является одной из классических топологий для построения сетей передачи информации. Изучению гиперкубов и их свойств посвящено много работ. Известны и некоторые результаты, связанные с задачей построения отказоустойчивых реализаций. В 1993 году Харари и Хейз предложили схему построения оптимальных устойчивых к отказам рёбер реализаций произвольного гиперкуба. Позднее была доказана единственность предложенной ими схемы. На данный момент аналогичная схема для построения оптимальной устойчивой к отказу вершин реализации гиперкуба не найдена. Оптимальные устойчивые к отказам $k$ узлов реализации графов называются минимальными вершинными $k$-расширениями. Для поиска минимальных вершинных $k$-расширений применяются различные численные методы. Известны результаты для 8-вершинного гиперкуба, но для 16-вершинного гиперкуба результат не был найден, даже с использованием вычислений на кластере. В данной работе предлагается новый подход к построению вершинных расширений графов. Обосновывается его корректность, а также описывается алгоритм, опирающийся на данный подход. Предлагаются и обосновываются оптимизации данного алгоритма на основе групп автоморфизмов. Предложенный алгоритм позволяет построить все минимальные вершинные 1-расширения 16-вершинного гиперкуба без применения кластера и суперкомпьютера. Hypercube is one of the classic topologies for constructing information communication networks. Much work has been devoted to the study of hypercubes and their properties. Some results related to the problem of constructing fault-tolerant implementations are also known. In 1993 Harary and Hayes proposed a scheme for constructing optimal edge-tolerant implementations of an arbitrary hypercube. The uniqueness of their scheme was later proven. To date, a similar scheme for constructing an optimal vertex-tolerant implementation of a hypercube has not been found. Optimal $k$-node-tolerant graph implementations are called minimal vertex-tolerant $k$-extensions. Various numerical methods are used to find minimal vertex $k$-extensions. Results are known for an 8-vertex hypercube, but no result has been found for a 16-vertex hypercube, even using cluster computations. This paper proposes a new approach to constructing vertex-tolerant graph extensions. Its correctness is substantiated, and an algorithm based on this approach is described. Optimizations of this algorithm based on automorphism groups are proposed and justified. The proposed algorithm allows one to construct all minimal vertex 1-extensions of a 16-vertex hypercube without the use of a cluster or supercomputer.
Zitieren
APA
Лобов, А. А. (2026). Построение минимальных вершинных расширений графа путём объединения его изоморфных копий. Herald of Tver State University. Series: Applied Mathematics, 79-88. https://doi.org/10.26456/vtpmk759
Vancouver
Лобов АА. Построение минимальных вершинных расширений графа путём объединения его изоморфных копий. Herald of Tver State University. Series: Applied Mathematics. 2026:79-88. doi:10.26456/vtpmk759
BibTeX
@article{2026,
author = {Лобов, Александр Андреевич},
title = {Построение минимальных вершинных расширений графа путём объединения его изоморфных копий},
journal = {Herald of Tver State University. Series: Applied Mathematics},
year = {2026},
number = {1(80)},
pages = {79--88},
doi = {10.26456/vtpmk759}
}
EUVIMED