Образец для цитирования:
Курносова С. Г. T-неприводимые расширения объединений полных графов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2005. Т. 5, вып. 1. С. 107-?.
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
