Computational complexity of graph extensions.pdf В 1976 году Хейз в работе [1] предложил основанную на графах модель для исследованияотказоустойчивости. Технической системе Е сопоставляется помеченныйграф G, вершины которого соответствуют элементам системы Е, ребра (или дуги) -связям между элементами, а метки указывают тип элементов. Под отказом элементасистемы Е понимается удаление соответствующей вершины из графа системы Gи всех связанных с ней ребер. Говорят, что система Е* является k-отказоустойчивойреализацией системы Е, если отказ любых k элементов системы Е* приводит к графу,в который можно вложить граф системы Е с учетом меток вершин. Построениеk-отказоустойчивой реализации системы можно представить себе как введение в нееопределенного числа новых элементов и связей. При этом предполагается, что в нормальномрежиме работы избыточные элементы и связи маскируются, а в случае отказапроисходит реконфигурация системы до исходной структуры.Пусть в системе Е встречается t различных типов элементов. Очевидно, что любаяее k-отказоустойчивая реализация должна содержать не менее k дополнительныхэлементов каждого типа. Легко видеть, что такого числа дополнительных элементовдостаточно для построения k-отказоустойчивой реализации системы Е. В самом деле,добавим k элементов каждого типа и соединим их все между собой и с элементамисистемы Е. Тогда любой отказавший элемент можно будет заменить одним из добавленныхэлементов соответствующего типа.k-отказоустойчивая реализация Е* системы Е, состоящей из элементов t различныхтипов, называется оптимальной, если система Е* отличается от системы Е на kэлементов каждого из t типов системы Е, и среди всех k-отказоустойчивых реализацийс тем же числом элементов система Е* имеет наименьшее число связей.Хейз предложил процедуры построения оптимальной k-отказоустойчивой реализациидля цепи, цикла и помеченного дерева. Позднее Хейз и Харари в работе [2]обобщили модель на случай отказов связей между элементами, предложив понятиереберной отказоустойчивости. Модель отказоустойчивости, в которой рассматриваютсяотказы элементов, в работе [3] было предложено называть вершинной отказоустойчивостью.Если исключить понятие отказа, то рассмотренные ранее понятия могут быть естественнымобразом сформулированы с использованием обычных терминов теории графов.Впервые это было предложено автором в работе [4], и далее мы дадим формальныеопределения именно в таком виде.Граф G* = (V*, а*) называется вершинным (реберным) k-расширением (k - натуральное)графа G = (V, а), если граф G вкладывается в каждый подграф графа G*,получающийся удалением любых его k вершин (ребер).Сформулируем задачу о вершинном k-расширении как задачу распознаваниясвойств, то есть задачу, ответом на которую может быть «да» или «нет»:ВЕРШИННОЕ k-РАСШИРЕНИЕУСЛОВИЕ. Даны графы G = (V, а) и H = (U, в ).ВОПРОС. Верно ли, что граф G является вершинным k-расширением графа H?Теорема 1. Задача ВЕРШИННОЕ k-РАСШИРЕНИЕ является NP-полной.Аналогично формулируется задача о реберном k-расширении:РЕБЕРНОЕ k-РАСШИРЕНИЕУСЛОВИЕ. Даны графы G = (V, а) и H = (U, в ).ВОПРОС. Верно ли, что граф G является реберным k-расширением графа H?Теорема 2. Задача РЕБЕРНОЕ k-РАСШИРЕНИЕ является NP-полной.

Скачать электронную версию публикации