RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Южно-Уральского государственного университета. Серия «Математика. Механика. Физика» // Архив

Вестн. Южно-Ур. ун-та. Сер. Матем. Мех. Физ., 2021, том 13, выпуск 4, страницы 77–89 (Mi vyurm503)

Краткие сообщения

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

П. В. Разумовский, М. Б. Абросимов

Саратовский государственный университет, г. Саратов, Российская Федерация

Аннотация: Предлагаются к рассмотрению результаты поиска минимальных вершинных расширений для неориентированных цветных полных графов. Данная тематика непосредственно связана с моделированием полных отказоустойчивых технических систем с элементами различного типа в терминологии графов. Если описывать техническую систему как $\Sigma$, то ей сопоставляется некоторый граф $G(\Sigma)$, в котором вершины соответствуют элементам системы $\Sigma$, а ребра — связям между ними. Тип каждого элемента выражается в сопоставлении каждой вершине графа $G(\Sigma)$ некоторого цвета из множества цветов $F = \{1, 2\dots, i\}$. Вершинным расширением данной системы тогда является некоторый граф $G(\Sigma)$, в котором введены избыточные вершины и при котором система, ему соответствующая, способна продолжать работу в присутствии $k$ отказов любых её элементов. Полным граф называется тогда, когда любые две его вершины соединены ребром. Полные графы не имеют реберных расширений по определению — не существует способа добавить ребро в граф с максимальным количеством ребер. Другими словами, система, представленная полным графом, не способна противостоять отказам связей между своими элементами. Поэтому данная работа целиком посвящена исследованию минимальных вершинных расширений. Описываются условия существования минимальных вершинных расширений для цветных полных графов, приводятся схемы построения и формулы, по которым можно вычислить необходимое количество дополнительных ребер для построения минимального вершинного расширения цветного полного графа.

Ключевые слова: вершинные расширения графов, полные графы, минимальные расширения графов, расширения цветных графов, цветные графы.

УДК: 519.17

Поступила в редакцию: 28.10.2021

DOI: 10.14529/mmph210409



© МИАН, 2024