Для цитирования:
Лобов А. А., Абросимов М. Б. Вершинные расширения 4-слойных графов и гиперкубов // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2022. Т. 22, вып. 4. С. 536-548. DOI: 10.18500/1816-9791-2022-22-4-536-548, EDN: BHQKFP
Вершинные расширения 4-слойных графов и гиперкубов
Дж. П. Хейз предложил математическую модель отказоустойчивых реализаций технических систем на основе графов, которой в более абстрактном виде соответствуют вершинные и рёберные расширения графов. Граф $G^*$ называется вершинным $k$"-расширением графа $G$, если граф $G$ вкладывается в каждый граф, полученный из $G^*$ удалением любых $k$ вершин. Если никакая собственная часть графа $G^*$ не является вершинным $k$-расширением графа $G$, то расширение $G^*$ называется неприводимым. Если вершинное $k$-расширение имеет минимально возможное число вершин и рёбер, то оно называется минимальным. Задача поиска минимальных расширений для произвольного графа является вычислительно сложной. Только для некоторых классов графов удалось найти частичное или полное описание их минимальных вершинных расширений. В данной работе предложена общая схема построения вершинных 1- и 2-расширений для почти всех двудольных графов, в том числе и для гиперкубов. Гиперкуб является интересным графом с точки зрения его свойств и возможности использования в качестве топологии вычислительной системы. Минимальные вершинные расширения для гиперкубов неизвестны. На практике используются тривиальные 1-расширения, которые получаются добавлением одной вершины и соединением её со всеми остальными. Неприводимое 1-расширение для 16-вершинного гиперкуба, которое предлагается в данной работе, содержит на одно ребро меньше, чем тривиальное 1-расширение. Также в статье определяется количество неизоморфных расширений для каждого гиперкуба, которые можно построить с использованием предложенных схем, и доказывается неприводимость вершинных 1-расширений гиперкуба.
- Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. Москва : Физматлит, 1997. 368 с. EDN: XYCVTZ
- Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Саратовского ун-та, 2012. 192 с. EDN: QMXQLB
- Hayes J. P. A graph model for fault-tolerant computing system // IEEE Transactions on Computers. 1976. Vol. C-25, № 9. P. 875–884. https://doi.org/10.1109/TC.1976.1674712
- Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol. 23, iss. 2. P. 135–142. https://doi.org/10.1002/net.3230230207
- Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. 1996. Vol. 27, iss. 1. P. 19–23. https://doi.org/10.1002/(SICI)1097-0037(199601)27:1<19::AID-NET2>3.0.CO;2-H
- Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Математические заметки. 2010. Т. 88, вып. 5. С. 643–650. https://doi.org/10.4213/mzm8403, EDN: RLRFEF
- Абросимов М. Б., Камил Ихаб А. К., Лобов А. А. Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2019. Т. 19, вып. 4. С. 479–486. https://doi.org/10.18500/1816-9791-2019-19-4-479-486, EDN: YXOMDX
- Абросимов М. Б., Судани Х. Х. К., Лобов А. А. Построение минимальных рёберных расширений графа без проверки на изоморфизм // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2020. Т. 20, вып. 1. С. 105–115. https://doi.org/10.18500/1816-9791-2020-20-1-105-115, EDN: PXDRGJ
- Harary F., Hayes J. P., Wu H.-J. A survey of the theory of hypercube graphs // Computers & Mathematics with Applications. 1988. Vol. 15, iss. 4. P. 277–289. https://doi.org/10.1016/0898-1221(88)90213-1
- Biggs N. L. Distance-transitive graphs // Algebraic Graph Theory. Cambridge : Cambridge University Press, 1974. P. 155–163. https://doi.org/10.1017/CBO9780511608704.021
- 1175 просмотров