Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Курносова С. Г. T-неприводимые расширения объединений полных графов // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2005. Т. 5, вып. 1. С. 107-115. DOI: 10.18500/1816-9791-2005-5-1-107-115, EDN: RPBUAE

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
30.09.2005
Полный текст:
(downloads: 154)
Язык публикации: 
русский
Рубрика: 
УДК: 
519.17
EDN: 
RPBUAE

T-неприводимые расширения объединений полных графов

Авторы: 
Курносова Светлана Геннадьевна, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Т-неприводимое расширение является одним из видов оптимальных расширений для графов. Конструкции оптимальных расширений применяются в диагностике дискретных систем и криптографии. Расширением п-вершинного графа граф Нс п+1 вершинами такой, что граф G вкладывается в каждый максимальный подграф графа Н. У любого графа есть тривиальное расширение - соединение G+vrpaфа одной вершиной. Т-неприводимые расширения получаются из тривиального удалением максимального числа ребер, не нарушающим свойство расширения. Задача нахождения графа по его Т-неприводимому расширению имеет линейную сложность, а для задачи отыскания всех Т-неприводимых расширений произвольного графа в настоящее время эффективного алгоритма нет. В данной работе предлагается алгоритм построения всех Т-неприводимых расширений и оценка их количества для объединений полных графов, каждый из которых имеет не менее одной вершины.

Список источников: 
  1. Авиженис А., “Отказоустойчивость — свойство, обеспечивающее постоянную работоспособность цифровых систем”, Тр. Ин-та инженеров по электротехнике и радиоэлектронике, 66:1О (1978), 5–25
  2. Hayes P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., С-25:9 (1976), 875–884
  3. Салий В. Н., “Доказательства с нулевым разглашением в задачах о расширениях графов”, Вестн. Томск. ун-та, 2003, № 6, Прил., 63–65 
  4. Курносова С. Г., Т-неприводимые расширения 3-, 4-, 5- и 6-вершинных графов, Деп. в ВИНИТИ 21.06.2003, № 1203-B2003, Саратов, 2003, 18 с.
  5. Курносова С. Г., “Т-неприводимые расширения для некоторых классов графов”, Теоретические проблемы информатики и ее приложений, 6, Саратов, 2005
  6. Курносова С. Г., Каталог Т-неприводимых расширений для деревьев с числом вершин не более 1О, Деп. в ВИНИТИ 30.06.2004, № 1126-82004, Саратов, 2004, 16 с.
  7. Курносова С. Г., “Т-неприводимые расширения бесповторных объединений полных графов”, Молодежь. Образование. Экономика, Т. 4, Сб. науч. ст., Ярославль, 2004, 289–292
Поступила в редакцию: 
16.03.2005
Принята к публикации: 
17.08.2005
Опубликована: 
30.09.2005