Комбинаторные методы математической теории надежности тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Черняк, Аркадий Александрович
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Минск
МЕСТО ЗАЩИТЫ
|
||||
|
2000
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
Институт математики Национальпом: академии наук Беларуси
РГ5 Ой
УДК 519.7Н510.1 СЕН 2000
ЧЕРНЯК Аркадий Александрович
КОМБИНАТОРНЫЕ МЕТОДЫ МАТЕМАТИЧЕСКОЙ ТЕОРИИ НАДЕЖНОСТИ
01.01.09 — математическая кибернетика
Автореферат диссертации на соискание ученой степени доктора физико-математических наук
Минск — 2000
Работа выполнена в Белорусском государственном университете
Научный консультант — доктор физико-математических наук, профессор Тышкевич Регина Иосифовна
Официальные оппоненты:
доктор физико-математических наук, академик HAH Беларуси Танаев Зячеслав Сергеевич
доктор физико-математических наук, профессор Зуев Юрий Анатольевич
доктор физико-математических наук, профессор Харин Юрий Семенович
Оппонирующая организация — Нижегородский государственна университет им. Н. И. Лобачевского
Защита состоится 22 сентября 2000 г. в 1500 на заседании совета г защите диссертаций Д 01.02.02 в Институте математики HAH Беларуси г адресу. 220072, Минск, ул. Сурганова 11
С диссертацией можно ознакомиться в библиотеке Института математик HAH Беларуси
Автореферат разослан " V " С 2000 г.
Ученый секретарь совета по защите диссертаций, доктор физико-математических наук, профессор
П.П. Матус
JfS'ßS.Cb-Oli /„ Uti . О
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы диссертации. Укрупнение масштабов производства I прогресс компьютерных технологий в последние два десятилетия пособствовали развитию математической теории надежности больших •истем. Потребность в развитом математическом аппарате привела к формированию двух основных направлений исследований:
а) вероятностные методы, основанные на предельных теоремах теории |ероятностей, статистическом моделировании, теории массового >бслуживания и теории случайных процессов;
б) методы дискретной математики, основанные на булевой алгебре, ;омбинаторном анализе, теории графов и гиперграфов, теории алгоритмов и :ложности вычислений, теории коммуникационных сетей.
В рамках первого направления в странах бывшего СССР, включая Беларусь, сложились научные школы мирового уровня. Второе направление, > пределах которого возможно создание эффективных сомпыотерноориентированных методов анализа высоконадежных :ложных систем, особенно интенсивно развивается в США, Кауадй и Индии, что отражено в многочисленных монографиях, учебниках, справочной и обзорной литературе. Исследования, проведенные в диссертации, относятся именно к этому направлению и их актуальность Раскрывается ниже.
Проблемы вычисления комбинаторной надежности и надежностного покрытия гиперграфов в эквивалентных формулировках — в терминах монотонных бинарных систем, клатгеров, симплициальных комплексов, эулевых функций — известны в литературе уже более 40 лет. Ключевыми здесь являются алгоритмические задачи точного и приближенного вычисления полиномов надежности гиперграфов, а также задачи синтеза максимально надежных графов с предписанными значениями параметров, характеризующих пропускные способности вершин и ребер. Большинство разработанных в этой области подходов и методов было предназначено для сетевых моделей мультитермннальной надежности, и потому ограничено 2-униформными гиперграфами, т. е. графами и мультиграфами. В связи с этим оставались открытыми задачи опенки полиномов надежностного и связного надежностного покрытия гиперграфов, а также задачи алгоритмической классификации двойственных проблем надежности и синтеза максимально надежных элементов в классах гиперграфов с предписанными степенными параметрами.
В начале 80-х годов была разработана теория доминирования, сыгравшая важную роль в эволюции комбинаторных методов анализа надежности сетевых структур. На ее основе были усовершенствованы многочисленные
методы расчета надежности графов, использующие принципы включен»: исключения и факторизации/ и выявлены среди них оптимальнь алгоритмические стратегии. Впоследствии границы этой теории был значительно раздвинуты благодаря установлению взаимосвязи функци доминирования клаттеров с матроидными инвариантами симплициальны комплексов и Полиномами надежности гиперграфов. Однако диапазон это теории охватывал только традиционные модели сетевой надежности, г позволяющие учитывать произвольную монотонную логик функционирования в вершинах графов. ,
Особенности двойственных проблем надежности для графоидны гиперграфов определяются свойствами индуцирующих их графов, чт требует разработки специальных методов решения этих проблел Центральными здесь являются проблемы вычисления оллполюсной резидуалыюй надежности различных классов графов. Интенсивное изучени первой было обусловлено тем, ч|о связанные с нею графоидные гиперграф] обладают матроидальными и шеллинговыми свойствами. Это послужил причиной появления эффективных методов для ее приближенного решенш Вторая проблема оставалась малоизученной ввиду немонотонности систем! путей индуцированного ею1 графоидного гиперграфа и как следствш неприменимости сложившихся подходов, используемых для расчета и оценк оллполюсной надежности. Незавершенными оставались также исследовани по алгоритмической классификации двойственных проблем надежности узких подклассах графоидных гиперграфов.
Связь работы с крупными научными программами, темам!' Исследования проводились в рамках следующих госбюджетных научны тем:
— Республиканская программа важнейших научно-исследовательских рабо в области естественных, технических и общественных наук п Белорусской ССР на 1986—1990 гг.,'утвержденная постановление? № 39 Президиума АН БССР от 03.04.86, тема Машиностроение 0 "Развитие теории прогнозирования надежности структурно-сложны систем машин и их элементов, разработка методик, программных ; аппаратурных средств оценки надежности",. 1986—1990, № roc регистрации 01860016567; i
— Исследование дискретных объектов с предписанным*} свойствами, 1996— 1997 гг. (план НИР Белгосуниверситета, приказы БГУ № 216-Д от 19.03.9 и № 438-Д от 14.05.97), № гос. регистрации 19962634;
— Характеризационные и алгоритмические аспекты теории графов и булевы функций, 1997—1999 гг. (распоряжение Министерства образован» Республики Беларусь № 05-9/5 от 13.01.97), № гос. регистрации 19974238;
— Разработка универсальных математических методов анализа надежности сложных систем, 1996—1997 гг., утверждена Министерством образов; кия и науки Республики Беларусь, приказ №. 60 от 16.02.96, № гос. регистрации 1996403.
Цель и задачи исследований. Целью исследования является разработка универсальных комбинаторных моделей и методов анализа надежности "иперграфов с предписанными структурными свойствами. Задачами исследования являются: алгоритмическая классификация двойственных троблем надежности и синтез максимально надежных элементов в классах -иперграфов с предписанными структурными свойствами; получение )ффективно вычислимых оценок основных полиномов надежности ^иперграфов; создание универсальной модели мультитерминальной надежноетн графов с произвольной монотонной логикой в вершинах и распространение на эту модель теории доминирования.
Объект и предмет исследования. Объектом исследования являются :труктурно-с ложные системы и устройства, для которых возникает необходимость разработки комбинаторных методов анализа надежности. Предметом исследования являются математические модели таких систем, алгоритмическая сложность соответствующих задач, точные и приближенные методы их решения.
Методология и истоды проведенного исследования. Использовались методы теории сложности вычислений, теории графов, булевой и пороговой ■гогики, комбинаторной теории бинарных матриц, теории надежности коммуникационных сетей.
Ряд новых методов разработан автором диссертации, в том числе общий иетод получения нижних оценок коэффициентов полиномов надежности гиперграфов; единый декомпозиционный подход для решения проблем резидуальной надежности в наследственных (относительно композиции) классах графов.
Разработана новая техника доказательства полиномиальной :водимости перечислительных задач на базе модифицированного метода локальных замен, использующего рекуррентные соотношения для анализа числовых свойств структурных характеристик добавляемых модулей.
Разработана конструктивная методология получения факторизационных георем и алгоритмов синтеза гиперграфов с предписанными значениями переключательно совершенных параметров.
Научная новизна и значимость полученных результатов. Получена алгоритмическая классификация проблем вычисления комбинаторной надежности и надежностного покрытия в классах гиперграфов с ограниченными степенными параметрами. Тем самым решена открытая
задача алгоритмической сложности двойственных проблем надежности ду униформных гиперграфов с разреженной реберной структурой.
Разработан метод регуляризации для получения эффективно вычислимь нижних оценок коэффициентов основных полиномов надежное! гиперграфов. С этой целью определен аналог регулярных гиперграфов классе всех гиперграфов — реберно-регулярные гиперграфы, и введен операции ,-сдвигов на .гиперграфах. Доказано, что эти операции I увеличивают коэффициентов полиномов надежности и за полиномиальнс время с их помощью гиперграфы и униформные простые гиперграфы мож! преобразовать соответственно в реберно-регулярные и регулярнь гиперграфы. Показано, что структурные свойства реберно-регулярнь гиперграфов позволяют генерировать подклассы канонических гиперграфо полиномы надежностного и связного надежностного покрытия которь эффективно вычислимы; в то же время получена структурная характеризащ путей и сечений регулярных гиперграфов, давшая эффективные алгоритм вычисления их полиномов комбинаторной надежности. На основе эт! результатов решены две открытые задачи, изученные ранее в частнь случаях: а) эффективная оценка полиномов надежностного и связно! надежностного покрытия униформных гиперграфов; б) структурнг характеризация гиперграфов, имеющих наименьшие коэффициент полиномов надежности в классах униформных гиперграфов фиксированными числами вершин и ребер. В серии прямых следств> получены усиления известных результатов о полиномиальной дуализаш регулярных гиперграфов и свойствах регулярных гиперграфо индуцирующих матроидные комплексы.
Разработана единая теоретическая основа для решения задач синте: максимально надежных элементов в классах гиперграфов с предписанньш значениями переключательно совершенных параметров. Это достигается помощью конструктивного аппарата, унифицирующего теоремы переключениях и обобщающего их на гиперграфы. На базе этого аппарата качестве прямых следствий решены: задача выявления множес: гипергр чфов, в которых основные виды степенных последовательности становятся переключательно совершенными, и задача эффективно] построения элементов в множествах связных гиперграфов с предписании степенными последовательностями.
Построена новая модель мультитерминальной надежности монотонный граф, представляющий собой графовую суперпозицию прость гиперграфов, что дает возможность моделировать с их помощью сложнь системы с сетевой структурой и произвольной монотонной логике функционирования в вершинах. Монотонные графы обобщают в традиционные модели мультитерминальной надежности — ¿/-тривиальн*
графы, которые являются их специальными случаями. На монотонные графы распространена теория доминирования, что позволило достичь максимально возможной конденсации символьных выражений надежности и определить граничные подклассы монотонных графов, для которых существуют :оответственно псевдополиномиальные и квазиполнномиальные алгоритмы решения проблемы комбинаторной надежности. Параллельно' выявлена клаттерная природа всех ранее известных результатов о доминировании d-тривиальных графов. Получена структурная характеризация основных подклассов монотонных графов, обладающих пороговой живучестью, завершающая, в частности, эффективное описание ¿-тривиальных графов с гаким же свойством.
Завершена алгоритмическая классификация (начатая другими авторами) проблем вычисления полиномов надежности в подклассах графоидных гиперграфов: а) определены границы, разделяющие #Р-полные и полиномиально разрешимые подзадачи проблемы вычисления полинома надежностного покрытия графоидных гиперграфов, индуцированных деревьями ограниченной степени и диаметра; б) доказана гипотеза о UP-полноте проблемы вычисления полинома оллполюсной надежное™ з классе гамильтоновых графов; в качестве следствий аналогичные результаты установлены в классах графов, близких к полным и полным двудольным; в) закрыт вопрос об алгоритмической сложности проблемы вычисления полинома резидуальной надежности для основных расширений пороговых графов; при этом все результаты о полиномиально разрешимых случаях получены на основе единого декомпозиционного подхода, применимого гакже к любому свойству графов, которое наследственно относительно эперации композиции или подвергалось бы легко обозримым изменениям, делающим это свойство наследственным.
Все результаты являются новыми. Некоторые из них включены (с :оответствующими ссылками) в несколько монографий по дискретной математике и теории надежности, в том числе в монографию Mahadev N., Peled U. "Tlireshold graphs and related topics", Amsterdam — New York, 1995.
Практическая значимость полученных результатов. Ряд моделей и теоретических обобщений, разработанных в диссертант;, возникли из конкретных практических задач в рамках хоздоговорных НИР, выполненных автором в составе группы ответственных исполнителей в Институте проблем надежности машин АН БССР по заказу предприятия п/я 5537 Министерства авиационной промышленности СССР.
Ра^рпботанные автором методы и алгоритмы вошли составной частые з заботу "Алгоритмические методы оценки и оптимизапии надежности технических систем с сетевой структурой", удостоенной премии Академии наук БССР за лучшую НИР (1990 г.).
Методы и алгоритмы, разработанные в диссертации, могут был использованы в задачах анализа и синтеза сложных систем, при оптимальнол проектировании высоконадежных систем со структурными ограничениями для решения задач живучести систем.
Основные положения диссертации, выносимые на защиту. На защиту выносятся:
— классификация в соответствии с алгоритмической сложностьк двойственных проблем надежности в классах гиперграфов < ограниченными степенными параметрами;
— общий метод получения эффективно вычислимых нижних оцено[ основных полиномов надежности гиперграфов на базе комбинаторны) свойств регулярных и реберно-регулярных гиперграфов;
— единая теоретическая методология для решения задач синтезг максимально надежных гиперграфов в классах гиперграфов с предписанными значениями переключательно совершенных параметров;
— универсальная графовая модель мультитерминальной надежности — монотонный граф; теория доминирования для монотонных графов I определение на ее основе граничных классов монотонных графов, дл? которых существуют псевдополиномиальные и квазиполиномиальньи алгоритмы решения проблемы комбинаторной надежности; эффективны« характеризации основных подклассов монотонных графов, обладающи> пороговой живучестью;
— вклад в алгоритмическую классификацию проблем вычисления полиномое надежности графоидных гиперграфов: полиномиальные алгоритмы решения, доказательства йР-полиоты и #Р-трудности этих проблем в различных классах графоидных гиперграфов.
Личный вклад соискателя. Все основные результаты диссертации получены автором самостоятельно. Из всех совместных работ, не считав авторских свидетельств на изобретения, в диссертацию включены толькс результаты, полученные лично автором. Что касается авторских свидстельстг [33, 34], то идеи изобретений в них принадлежат лично автору, а формуль изобретений принадлежат автору и соавторам в равной степени и включены I приложение к диссертации.
Апробация результатов диссертации. Результаты исследований включенных в диссертацию, докладывались на следующих научных форумах 4-я Всесоюзная научно-техническая конференция по повышению качестве функционирования и надежности информационных сетей и их элементов, г Новосибирск, 1981 г.; Республиканская научно-техническая конференция "Пуп повышения технического уровня и надежности машин", Минск, 1986 г.; 30-? и 33-й Международные коллоквиумы по технической кибернетике математике и вычислительной технике "Графы и сети — теория г
риложення", г. Ильменау, Германия, 1985 г., 1988 г.; Республиканская аучно-техническая конференция "Проблемы качества и надежности изделий лектронной техники, радиоэлектронной аппаратуры и средств управления", 4инск, 1988 г.; Международный симпозиум по надежности в электронике RELECTRONIC'91" г. Будапешт, Венгрия, 1991 г.; Всесоюзная научно-ехническая конференция по повышению надежности машин и приборов, г. Куйбышев, 1991 г.; Европейская конференция по индустриальной [атематике, г. Прага, Чехия, 1994 г.; 4-й Международный конгресс по ндустриальной и прикладной математике "ICIAM 99", г. Эдинбург, Иотландия, 1999 г.; семинар Белорусского математического общества, г. 4инск, 1999 г.; семинары по теории графов и гиперграфов механико-[атематического факультета Белгосуниверситета, 1997—1999 гг.
Опублнкованность результатов. Основные результаты диссертации публикованы в работах [1—41], из которых 30 публикаций в журналах [1— 0], 2 публикации в сборниках работ [31, 32], 2 авторских свидетельства на :зобретения [33, 34], 5 тезисов докладов и выступлений [35—39], 2 .епонированные рукописи [40, 41]. Общее количество страниц публикованных материалов — 288 'журнальных страниц.
Структура и объем диссертации. Диссертация соспмгг из обшей характеристики работы, 4 глав, заключения, списка использованных [сточников и одного приложения. Объем диссертации 230 страниц. Список юпользованных источников содержит 204 наименований.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
В главе 1 описаны основные направления исследований, составляющие [редмет диссертации. Дан краткий обзор результатов диссертации и шределено их место в исследованиях по комбинаторным аспектам (атематической теории надежности.
В разделе 2.1 главы 2 получена алгоритмическая классификация шойственных проблем надежности в классах гиперграфов с ограниченными :тепенными параметрами.
Пусть G - (Т, Р) — простой гиперграф с множеством вершин Т и мно-кеством ребер р (в простых гиперграфах ребра не вложимы друг в друга), R+ — множество неотрицательных действительных чисел, pr:T-+ R4 — функция, для которой 0 < pr(s) < 1 при каждом s е Т. Предположим, что саждая вершина s, независимо от других, с вероятностью 1 — pr(s) может включаться из G (отказывать). Обозначим через Iir(G, рг(Т)) вероятность юбытия, заключающегося в том, что множество неисключенных вершин в G содержит хотя бы одно ребро (т. е. является зависимым множеством).
Величина hR(G, рг(Т)) известна как комбинаторная надежность простог гиперграфа С; проблему ее вычисления будем называть /lEL-проблемой.
Пусть теперь G — гиперграф (в гиперграфах допускается вложимост ребер друг в друга), не содержащий изолированных вершин. Каждой вершин j гиперграфа G сопоставим множество N(s) всех инцидентных ей ребер Величина |/V(j)| называется степенью вершины j. Пусть G* = (7*, Р*) -простой гиперграф, двойственный к G, в котором Т* = Р, Р * = Min({iV(s) : е 7}), где Min(Q) обозначает множество всех минимальных (по включению подмножеств системы множеств Q. Предположим, что задана функция рг : Т ~> R+, и каждая вершина е, независимо от других, с вероятностью 1 — рг{е может исключаться из G* (отказывать). Обозначим через hçiG, рг(Р] вероятность события, заключающегося в том, что множество ненсключенны вершин в G* является трансверсальным для Р* (т. е. имеет непусто пересечение с каждым ребром из Р*). Величина hdG, рг{Р)) известна ка величина надежностного покрытия гиперграфа G; проблему ее вычислени будем называть СО VD ОТ-проблемой. Несмотря на двойственност формулировок, REL-пробпша. и COFDL/P-проблема по существу не являютс двойственными. Отметим также, что эти проблемы в эквивалентны: формулировках — в терминах монотонных бинарных систем, клаттероЕ симплициальных комплексов, булевых функций — известны в литератур уже более 30 лет. Ввиду тождественности понятий простого гиперграфа i клаттера системы множеств, зависимые и трансверсальные множеств простого гиперграфа будем называть его путями и сечениями.
Если все значения функции рг равны р (в этих случаях будем писать л вместо pr(J) илирг(Р)), то
Г 0>
№ Я,р'{1-р)*-1, тЦР\,
1=0
где И, — число путей в G мощности /', — число реберных покрытий в ( мощности /. Символьные выражения в правых частях равенств (1 называются соответственно полиномом комбинаторной надежности (сокрг щенно, полиномом КН) простого гиперграфа G и полиномом надежностног покрытия (сокращенно, полиномом НП) гиперграфа G.
Как видно из определений, проблемы вычисления полиномов надежност являются перечислительными задачами комбинаторного анализа, исток изучения которых восходят ко второй половине 19-го века. Так, если гиперграфе G степени всех ребер равны 2, а число вершин четно, то задача сложности вычисления среднего коэффициента полинома НП гиперграфа (
вляется знаменитой проблемой о сложности вычисления перманента атрицы. Эта проблема, а также проблемы вычисления полиномов адежности оказались #Р-полньшн (L. G. Valiant, М. О. Ball, J. S. Provan), , е. алгоритмически трудноразрешимыми. Это было доказано в рамках гории сложности вычислений, построенной для перечислительных задач бщего вида: по аналогии с классо:; Р (полиномиально разрешимых зада ч) и пассом NP (недетерминированно разрешимых за полиномиальное время 1дач распознавания) были определены класс UP перечислительных задач, гшаемых за полиномиальное время на недетерминированных машинах ьюринга со cneuT'.vibHbiMH счетными устройствами, а также классы олных и UP-трудны v задач, к которым полиномиально сводимы все задачи з #Р.
Следующим шагом в изучении двойственных проблем надежности вилось рассмотрение их в классах гиперграфов с ограниченными степенями :ршин и ребер. Этот первый уровень сужения проблем надежности осматривался многими авторами. Полученные здесь ранее результаты ожно разбить на две группы: а) доказательства эффективной разрешимости роблем вычисления полиномов надежности в классах гиперграфов с потной реберной структурой, т. е. в гиперграфах, в которых степени вершин пи ребер растут вместе с размерностью задачи; б) доказательства 1Горитмической трудноразрешимое™ этих проблем для гиперграфов с роизвольными степенями вершин (ребер). Алгоритмическая сложность войственных проблем надежности для гиперграфов с ограниченными гепенями вершин и ребер оставалась невыясненной. В разделе 2.1 этот эпрос полностью закрыт. Пусть (к, Г) обозначает множество простых шерграфов, в которых степени всех ребер равны к (¿-униформность) и аксимальная вершинная степень (частота появлений вершин в ребрах) равна пусть [А*, /] обозначает также множество всех гиперграфов, получаемых из шерграфов множества (к, I) добавлением кратных ребер.
Теорема 1. Пусть к и / — фиксированные натуральные числа, к > 2, I > 2. огда /^¿-проблема и COVDUP-проблема полиномиально разрешимы ^ответственно в классах (к, Г) и /] при к = I = 2; для всех остальных «чений к и / проблемы вычисления полиномов КН и НП являются #Р-эудными в классах (к, /)• Более того, задача вычисления полинома КН только одной точке р = 1/2 является #Р-полной в классах (к, Г) для всех / > 3, к + / 6, а задача вычисления полинома НП только в одной точке р = 1/2 является Р-полной в классах (к, Г) для всех к> 3, к + / >6 и "Л-полной в классах [£, /] пя всех& + /> 5.
Продвинуться в решении этих вопросов удалось благодаря разработке ригинальнои методологии доказательства #Р-пи;шоты, которую условно ожно назвать методом рекуррентного расширения. Суть этого метода в
следующем: к основному модулю (гиперграфу, булевой функции и пр. присоединяются серии графов или булевых выражений (модул! присоединения) с рекуррентно определяемой структурой; затем мере: рекуррентные соотношения выясняются числовые свойства (делимость взаимная простота) нужных параметров или графовых характеристш расширенного модуля; на базе этих свойств доказывается полиномиальна) сводимость; при этом наращивание структурной сложности модул) присоединения позволяет осуществлять полиномиальную сводимость 1 достаточ но сильным сужениям перечислительных задач общего вида.
В связи с трудноразрешимостыо двойственных проблем надежности дш гиперграфов, актуальны два направления исследований: а) приближенны« методы вычисления полиномов надежности и оценка их коэффициентов (та] называемая равномерная оценка полиномов); б) поиск подклассо! гиперграфов с нетривиальными структурными свойствами, для которы; проблемы надежности полиномиально разрешимы. В рамках первогс направления были разработаны различные подходы для оценки полиномо! КН гиперграфов, опирающиеся на классические результаты экстремально} комбинаторики. Однако проблема оценки полиномов НП и полиномо; связного надежностного покрытия (сокращенно, полиномов СНП гиперграфов в общем случае оставалась открытой задачей. Исключение составляли полиномы СНП 2-униформных гиперграфов, т. е. графов 1 мультиграфов. Полиномом СНП гиперграфа С? называется символьно! выражение
т
¡=0
значение которого в каждой точке р совпадает с р), где рг(р) является величиной связного надежностного покрытия гиперграфа й, равно! вероятности связности частичного гиперграфа с множеством вершин Т I множеством неисключенных ребер из О (очевидно, ct равно числу реберны; покрытий в й мощности;, индуцирующих связные гиперграфы).
В рамках второго направления ключевым являлся результат о подкласса) шеллинговых гиперграфов. Если О с 2Г, то О1 (О*) будет обозначат! множество всех надмножеств (подмножеств) системы множеств О.] ~ р с Т: 7\Х е П}. Пара [Г, О] называется симплициальным комплексом, есл! О = £У. Если при этом О образует набор независимых множеств матроида < носителем Г, то [7, называется матроидным комплексом
Симплициальный комплекс, в котором все фасеты одинаковой мощности, ; сам комплекс можно разбить на интервалы множеств {5сГ: (/с 5с ^ называется шеллинговым. Понятие шеллингового гиперграфа шире, так как н требует равномощности ребер: простой гиперграф называется шеллинговым
:слн существует шеллинг его ребер, т. е. такой порядок всех его ребер Р¡,..., Р„, три которой для каждого i = 2, ..., т все минимальные множества семейства множеств {/V Pt, ...., />,-1 \ Pi} одноэлементные. Очевидно, простой гиперграф Т, Р) индуцирует два двойственных симплициальных комплекса: грансверсальный комплекс [Т, 2Г\РЛ] и копутевой комплекс [7", Тоэтому униформный простой пшерграф (Г, Р) шеллинговый, если и только если копутевой комплекс [Г, i P'J] шеллинговый. Алгоритмическая сложность задачи распознавания шеллинговых гиперграфов является до сих юр открытой проблемой. Однако на основе методов ортогонализации булевых моделей надежности (М. О. Ball, J. A. Abraham, L. Fratta, J. Provan) было юказано: ЯЫ,-проблема полиномиально разрешима в тех подклассах иеллинговых гиперграфов, шеллинговость которых распознается за юлиномиальное время. К настоящему времени известны только два таких юдержательных подкласса: гиперграфы, индуцирующие копутевые латроидные комплексы, и регулярные гиперграфы. Пусть задан некоторый юрядок j|, ..., s„ вершин из Г, А = {j,,..., s, },
B = {sj,..., Sjr), /, < i2 <■■■ < ir, j\ < Ji <... < jr.C кажем, что А является левым
даигом В, если /t < j\,..., ir < jr. Порядок вершин в простом гиперграфе шывается регулярным, если множество его путей (или сечений) замкнуто тшеительно левых сдвигов. Простой гиперграф с фиксированным >егулярным порядком своих вершин называется регулярным. Известно, что ¡адачи существования и построения регулярного порядка гиперграфа юлиномиально разрешимы. Поэтому шеллинговость регулярных •иперграфов, с очевидностью вытекающая из их определения, также останавливается за полиномиальное время.
В разделах 2.2, 2.3 главы 2 разработан единый метод — метод >егулярнзации — получения эффективно вычислимых нижних оценок соэффициентов всех трех полиномов надежности гиперграфов, :интезирующий в себе оба направления, о которых говорилось выше. С этой клью определен аналог регулярных гиперграфов в классе всех гиперграфов — реберно-регулярные гиперграфы: в них любой левый сдвиг произвольного эебра не уменьшает кратности этого ребра (понятия регулярного и реберно-эегулярного гиперграфов становятся эквивалентными на множестве униформных простых гиперграфов). Введены операции сдвига первого и ¡торого рода на гиперграфах. Доказано, что эти операции не увеличивают соэффициентов полиномов надежности и за полиномиальное время с их юмощью гиперграфы и униформные простые гиперграфы можно треобразовать соответственно в реберно-регулярные и регулярные "иперграфы. В то же время оказалось, что структурные свойства реберно->егулярных гиперграфов позволяют генерировать подклассы канонических
гиперграфов, полиномы НП и СНП которых эффективно вычислимы, г полученная в разделе 2.2 комбинаторная характерпзация путей и сеченш регулярных гиперграфов приводит к эффективным алгоритмам точного вычисления коэффициентов их полиномов КН.
Следствие 1. Среди гиперграфов с фиксированными числом вершин i числом ребер наименьшие коэффициенты полиномов НП и СНП имеют реберно-регулярные гиперграфы.
Следствие 2. Среди простых униформных гиперграфов с фиксированными числом вершин и числом ребер наименьшие коэффициенты полиномов КН имеют регулярные гиперграфы.
Другой серией следствий метода регулязации явилось усиление классических результатов (P. Hammer, U. Peled, Lenstra J., A. Kan, B. Simeone. L. Wolsey) о полиномиальной дуализации регулярных гиперграфов (т. е. с двойственном представлении их за полиномиальное время системой минимальных сечений) и свойствах регулярных гиперграфов, индуцирующих матроидные комплексы. В частности, временная сложность всех алгоритмических результатом, содержащихся в этих следствиях, либс линейная, либо равна 0(| 7> | + | Т | ■ | Q* |) (здесь П* — множество первых производных характеристических векторов ребер гиперграфа (7, Р), \Р* \ < IРI; вектор х* называется первой производной бинарного вектора * = (дгь ..., *„) если X* получается из х преобразованием единичной координаты вектора х с наибольшим индексом в нулевую координату).
Пусть А — некоторый степенной параметр гиперграфов из множества Ж. характеризующий уровни резервирования или пропускные способности вершин и ребер. Тогда возникает известная проблема синтеза максимально надежного элемента в классе ЩА0) = {G е Ж : A(G) = Д0} всех гиперграфов из множества Ж с предписанным значением Д0 параметра А. Проблема синтеза может быть решена на основе следующих двух этапов:
(*) решения задачи существования и построения некоторого элемента из Щ&о) (будем называть ее задачей существования);
(**) эффективной генерации всех элементов множества /%(Д0). Ранее было доказано (С. J. Colbourn, I. Soi, К. Aggarval), что этап (**] автоматически реализуется для параметров А, обладающих свойством переключательного совершенства. Это свойство означает, что существует система блочных переключений — преобразований специального вида, которые: а) не изменяют значений параметра А; б) в случае непустоты множества Ж{А0) обеспечивают достижимость из произвольного элемента е Щ&о) любого другого элемента в ЩА0); в) позволяют эффективно вычислять полиномы надежности преобразованного гиперграфа через полиномы надежносги преобразуемого гиперграфа. Таким образом, этап (**]
трансформируется в задачу выявления множеств Ж, в которых параметр Л становится переключательно совершенным (назовем ее задачей о переключениях). Следует отметить, что для переключательно совершенного параметра А в классе %(Л0) осуществима также эвристическая процедура локального решения проблемы синтеза. Она основана на поиске в окрестности //(С) элемента с наибольшим значением показателя надежности (комбинаторной надежности, величины надо- постного или связного надежностного покрытия); N(0) — это множество псех гиперграфов, которые могут быть получены из С? с помощью только одного блочного переключения.
Задача существования и задача о переключениях имеют самостоятельный интерес для теории графов и гиперграфов и довольно интенсивно изучались разными авторами. Однако полученные здесь результаты либо оставались незавершенными, либо ограничивались только графами и мультиграфами. В разделах 2.4, 2.5 главы 2 разработана единая теоретическая основа для решения этих задач на гиперграфах. Это достигается с помощью инструктивного аппарата, унифицирующего теоремы о переключениях и эбобщающего их на гиперграфы. Эффективность методологии подтверждена также следующими сериями прямых следствий. Пусть ЬЛк) — множество к-/ниформных гиперграфов, кратность ребер которых не превосходит г, г, к е
00
и {°о}, — множество натуральных чисел, ¿г = ¿г(«>) = ^Ьг(к)
к=г
очевидно, ¿„ ¿ь Ьт и Ь£2.) являются соответственно г-гиперграфами, тростыми гиперграфами, гиперграфами и /--графами).
Первая группа следствий касается задачи о переключениях для основных шдов степенных последовательностей гиперграфов.
Следствие 3. Реберная степенная последовательность является 1ереключательно совершенной в классах Ьг и Ь^к) для любых г и к. Зершинная степенная последовательность является переключательно свершенной в ЬДК), если и только если г = оо или к = 2.
Следствие 4. Окружная степенная последовательность является тереюпочательно совершенной в классах /--графов для любого г. Частотная степенная последовательность является переключательно совершенной в слассах (ул, д)-дифферентных г-графов для любых г, ¡1 и ц.
Другая группа следствий завершает решение задачи существования связных гиперграфов с предписанными степенными последовательностям«: толучены конструктивные доказательства полиномиальной разрешимости >той задачи в классах связных г-гиперграфов (гиперграфов) с предписанной >еберной (вершинной) степенной последовательностью и связных г-графов (ц, <7)-дифферентных г-графов) с предписанной окружной (частотной)
степенной последовательностью. Получены также новые критерии факторизуемости степенных последовательностей гиперграфов, в частных случаях воспроизводящие известные теоремы о факторизуемости степенных последовательностей графов.
С факторизацией степенных последовательностей связано понятие тотальной совместимости значений степенного параметра Д. Пусть Д15 Д2 — некоторые значения параметра Д. Предположим, что множества вершин гиперграфов из и ЩА2) совпадают. Скажем, что значение Л2
совместимо со значением Дь если в 3£(Д|) и Ш(Аг) существуют гиперграфы
G = (7, {/>„,...,/>,„,}), Я=(Г, {Р2и Р2т})
такие, что Р\, с Ргf, i = 1, ..., т. При этом Я называется гиперграфом совместимости с А(. Очевидно, h^G, р) < Л^Я, р), /;A/(G, р) < hjjrl, р), и коэффициенты полиномов НП и СНП гиперграфа G не превосходят коэффициентов соответствующих полиномов гиперграфа Я. Значение Д2 называется потенциально совместимым с Дь если все три множества 7K{ts{), %(Д2), "Щ&2 — А|) не пустые (если Ai и Д2 — наборы последовательностей, то Д2 — Л] обозначает набор разностей соответствующих последовательностей из Д2 и Д|). Значение Д0 называется тотально совместимым, если с ним совместимо любое потенциально совместимое значение Дд параметра Д.
Тотальная совместимость значения Д0 означает, в частности, что минимальные величины надежностного и связного надежностного покрытия гиперграфов из "ЩА0) доставляют нижние оценки соответствующим величинам гиперграфов совместимости из множества Ж(А'0) для любого Ад, потенциально совместимого с Д0. Проблема получения достаточных условий тотальной совместимости значений параметра Д = (а, (3), где а и Р — последовательности степеней вершин и ребер фиксированной длины, обсуждалась в работах R. Brualdi, R. Anstee, Y. С. Chen, A. Shastri; ими были получены достаточные условия тотальной совместимости значений параметра (а, Р) в терминах запрещенных конфигураций. Однако эти условия оказались алгоритмически труднопроверяемыми. В разделе 2.4 даны эффективно проверяемые достаточные условия тотальной совместимости параметра (а, Р). В серии следствий усилены соответствующие достаточные условия Чена-Шастри-Ансти в терминах запрещенных конфигураций, опровергнута гипотеза Брюалди-Ансти о тотальной совместимости пары (а0, Ро), для которой Щ(а0, Ро)) * 0; доказано существование полиномиального алгоритма построения гиперграфа совместимости с тотально совместимой парой.
В разделе 3.1 главы 3 введена новая графовая модель мультитерминальной надежности — монотонный граф, который определяется следующим образом. Для О с 2Г обозначим через Bl(Q.) множество
(ХсГ:1л Г* 0 для каждого Г е Q}. Если #= (Г, Р) — гиперграф без кратных ребер, то пары [Г, Min^)] и [Г, Min (В!(Р))] называются соответственно клаггерами путей и сечений (гиперграфа Н) с носителем Т; при этом элементы из Mini?) называются минимальными путями, а элементы из Ыт(В1(Р)) — минимальными сечениями. Очевидно, простой гиперграф совпадает со своим клаттером путей. Клатгер [Т, Q] когерентный, если каждый элемент из Т принадлежит некоторому множеству из ii; клаттер [Т, Q] вырожденный, если |Q| = 1. Пусть теперь G — ориентированный граф с множеством дуг DG, с входным полюсом 5 и выходным полюсом t (т. е. G — (s, О-граф), в котором D+(s, G) = 0, D'(/, G) = 0, D\v, G) * 0, D'(y, G) * 0 дня v * s, t, где D\v, G) и D~(v, G) — соответственно множества дуг, направленных в вершину v и направленных из вершины v. При этом наибольшая го величин |D+(v, G)| называется степенью (s, /)-фафа G. Предположим, что с каждой вершиной v * s связан когерентный клаттер путей с носителем D+(v, G), называемый локальным клаттером путей вершины v. Монотонным подграфом графа G назовем его (j, /)-подграф Н, в котором все локальные клаттеры когерентны и каждый минимальный путь произвольного локального клаттера путей в Н является минимальным путем соответствующего локального клаттера в G. Тогда минимальный подграф в G — это его монотонный подграф, в котором все локальные клатгеры путей вырожденные. Если теперь 7KG) = {Рь ..., Р„} — множество всех минимальных полграфов в G, DP(G) = {DP..., DPn}, то гиперграф G = (DG, Dp(G)) (или v го клаттер путей [DG, Dp(G)]) называется монотонным графом. При это * минимальные подграфы должны быть ациклическими, в противном случае G называется нестандартным монотонным графом. Таким образом, монотонный граф представляет собой "графовую" суперпозицию локальных клаттеров (гиперграфов), что позволяет моделировать с их помощью сложные системы, которые на структурном уровне являются графами, а на локальном (вершинном) уровне являются гиперграфами.
Монотонные графы обобщают все классические модели мультитерминальной надежности сетевых структур: /f-полюсные неориентированные, 2-терминальные, исток-К-терминальные,
оллтерминальные графы, которые в дальнейшем, будут объединены под общим названием "(/-тривиальные графы". Фактически, в ¿/-тривиальных графах все локальные клаттеры сечений вырожденные, а минимальными
подграфами могут быть только простые цепи. Поэтому они являютс: специальными случаями такого граничного подкласса монотонных графов как fifc-тривиальные графы: в таких графах локальный клаттер путей ил! локальный клаттер сечений каждой вершины вырожденный.
Введение монотонных графов в немалой степени было инспирирован« теорией доминирования, давшей новый импульс развитию комбинаторны; методов анализа надежности сетевых структур. Так, 70-е годы бьш отмечены всплеском работ, в которых рассматривались различны! алгоритмические версии расчета надежности ¿-тривиальных графов основанные на двух комбинаторных принципах: включения-исключения i факторизации (аналоге метода ветвей и границ). При этом сопоставлешк эффективности алгоритмов проводилось эмпирически. Комбинаторно! осмысление этих методов и выявление среди них оптимальны: алгоритмических стратегий было дано позднее (A. Satyanarayana, М. Chang A. Huseby, J. Hagstrom и др.) на базе теории доминирования, использующс! свойства функции доминирования ¿-тривиальных графов в алгоритма: анализа их надежности. Целочисленная функция 5, заданная на булеане 2Г называется функцией доминирования простого гиперграфа G = (Т, Р) (imi его клаттера путей [Т, р]), если для любого множества А с j
ф(Л) = £8(Д), где ер — индикатор путей гиперграфа G. При этом величин.
В^А
8(7) называется доминированием гиперграфа G (или клаттера [Т, Р\).
В разделах 3.2, 3.3 главы 3 теория доминирования распространена н; монотонные графы, что позволило достичь максимально возможно! конденсации символьных выражений комбинаторной надежносп монотонных графов на базе выявленных свойств их функцш доминирования (см. пп. А)—В)).
А) Решена проблема вычисления доминирования монотонных графо1 через их локальные доминирования (теоремы 2, 3, следствия 5, 6).
Теорема 2. Доминирование произвольного ациклического монотонной графа равно произведению доминирований локальных клаттеров путей все: его вершин.
Теорема 3. Доминирование произвольного циклического монотонной графа равно нулю. Для любого фиксированного натурального г задач; определения доминирования является #Р-полной в классе нестандартны: монотонных графов, в которых число циклических минимальных подграфо] равно г.
Следствие 5. Задача вычисления доминирования в классе монотонны: графов полиномиально разрешима.
Следствие 6. Задача вычисления доминирования монотонного графа, в котором все локальные клаттеры путей являются регулярными гнперграфэми, полиномиально разрешима.
Параллельно выявлена клатгерная природа всех ранее полученных результатов о доминировании «/-тривиальных графов, непосредственно вытекающих из перечисленных выше.
Б) Конструктивно доказано существование псевдополиномиального алгоритма (временная сложность которого полиномиальна относительно числа монотонных подграфов) решения ^¿-проблемы в классе ациклических монотонных графов ограниченной степени. Для произвольного монотонного графа получена аддитивная формула надежности, длина которой равна числу ациклических монотонных подграфов, а сложность вычисления каждого слагаемого определяется только сложностью вычисления локального доминирования.
В) Доказано, что задача вычисления полинома КН является #Р-трудной в классах ациклических ¿/с-тривиальных графов степени 2, в которых число минимальных подграфов (или минимальных разрезов) пропорционально их размерности. Это означает, в частности, что в случае Р Ф ИР не существует квазнполиномиальных алгоритмов (временная сложность которых полиномиальна относительно числа минимальных подграфов или числа минимальных разрезов) решения АЕ£-проблемы в классе ациклических с/с-тривиальных графов степени 2.
Следует отметить, что ранее было доказано существование квазиполиномиапышх алгоритмов решения ЙЕ£-проблемы для основных подклассов (/-тривиальных графов. Поэтому результаты пп. Б), В) фактически проводят водораздел между подклассами монотонных графов, для которых соответственно существуют псевдополиномиальные и квазиполиномиальные алгоритмы решения /?££-проблемы.
В разделе 3.4 главы 3 получена структурная характеризация основных подклассов монотонных графов, обладающих пороговой живучестью, что позволило, в частности, завершить эффективное описание ¿/-тривиальных графов с пороговой живучестью. Полюсной граф Я обладает пороговой живучестью, если в Я каждая дуга имеет определенную "цену разрушения", а цостижимость между полюсамч теряется тогда и только тогда, когда сумма 'цены разрушения" отказавших дуг превосходит допустимый порог. Простой гиперграф называется пороговым, если существует гиперплоскость, этделяюшая множество характеристических векторов всех его путей от юпутей. Аналогично, копороговый гиперграф характеризуется существованием гиперплоскости, отделяющей множество
(арактеристическнх векторов всех его сечений от несечений. Двойственность »тих понятий делает их малоразличимыми при изучении общих свойств
гиперграфов. Однако, если в основе определения гиперграфа лежит графовая структура, то проявление комбинаторных свойств этих понятий существенно зависит от определения множества ребер гиперграфа. Так, симбиоз монотонного графа G проявляется здесь в том, что копороговость гиперграфа G становится эквивалентной пороговой живучести (s, /)-графа G. Ранее было получено эффективное описание 2-полюсных неориентированных графов с пороговой живучестью (P. Hammer, F. Maffrey, М. Queyranne). Для остальных классов ¿/-тривиальных графов эта задача оставалась открытой. Ее решение содержится в следующих следствиях, прямо вытекающих из полученных в разделе 3.4 структурных характеризаций ¿с-тривиалышх графов, обладающих пороговой живучестью.
Вершина v монотонного графа G называется ¿-вершиной, если )Z)+(v, (?)| > 1 и локальный клаттер сечений вершины v вырожденный.
Следствие 1. Оллтерминапьный граф обладает пороговой живучестью, если и только если он ациклический и имеет не более одной ¿-вершины.
Инъективная функция ср : VG -> N+ называется ранговой функцией графа Н, если для любой дуги icv € DH верно <р(ы) < cp(v). Пусть Н — (s, 0-граф с ранговой функцией ф. Н называется арфа-графом, если Я содержит остовную (у, /)-цепь и для любых двух дуг uv, ziv, не принадлежащих этой цепи, либо ср(и) < ф(г), ф(у) > ф(ш), либо ср(м) > ф(г), ф(у) < ф(и>).
Следствие 8. 2-терминальный (s, /)-граф обладает пороговой живучестью, если и только если он является арфа-графом.
Следствие 9. Задача распознавания /Г-полюсных неориентированных графов, обладающих пороговой живучестью, разрешима за линейное время.
Теор тма 4. Задача распознавания ¿с-тривиальных графов G, обладающих пороговой живучестью, разрешима за время (?(|DG|2); в классе произвольных монотонных графов G соответствующая задача может быть решена квазиполиномиальным алгоритмом.
В качестве следствий показано также, что алгоритмическая сложность ЛЁХ-проблемы в подклассах монотонных графов, обладающих пороговой живучестью, не превосходит алгоритмической сложности соответствующих задач распознавания таких графов.
Если каждой вершине st гиперграфа G поставить в соответствие булеву переменную х,, каждому ребру — элементарную конъюнкцию переменных, соответствующих вершинам этого ребра, и обозначить Фд дизъюнкцию эти> конъюнкций, то комбинаторная надежность гиперграфа G будет равнг вероятности события {Фс = 1}. При этом функция Ф0 называете? структурной функцией гиперграфа G. Если G — монотонный граф, тс элементарные конъюнкции в Фс биективно соответствуют минимальнь№ подграфам в G. Поэтому к анализу надежности монотонных графо1 применимы методы булевой алгебры. Первоначально булевы методь
»азрабатывались для решения &££-проблемы в подклассах ¿-тривиальных рафов. Впоследствии они были распространены на многозначные системы, лементы которых допускают несколько состояний отказов. Общей ;ыч целительной основой этих методов являлась ортогонализация труктурных функций состояний отказов. Однако общим недостатком ставалась проблема размерности, возникающая из-за экспоненциального юста объема требуемой памяти в процессе ортогонализации. Этот недостаток собенно быстро обнаруживает себя при решении &Е£-проблемы для шогозначных систем. В разделе 3.5 главы 3 на основе общей булевой юдели многозначных систем <5 получен алгоритм расчета вероятности вхождения системы 5 в некотором состоянии отказа, емкостная сложность оторого полиномиальна относительно размерности системы. Это остигается за счет аддитивного построения ортогональной д.н.ф., минуя ромежуточный этап построения структурных функций состояний отказа, [оказано применение этого метода к вычислению надежности произвольного онотонного графа С. При этом требуемые затраты памяти пропорциональны вадрату размерности С, а временная сложность алгоритма полиномиально 1висит от длины построенной ортогональной д.н.ф.
Всюду ниже все графы считаются неориентированными, без петель и ратных ребер; степень графа — это наибольшая из степеней его вершин; УН ЕН обозначают соответственно множества вершин и ребер графа Н.
Гиперграф О = (Г, Р) называется вершинно (реберно) графоидным шерграфом, индуцированным графом Н с системой маршрутов если = УН (Т = ЕН), а V состоит из вершинных (реберных) множеств некоторого :мейства ^ связных подграфов в Я, называемых маршрутами в Н. Семейство аршрутов, состоящее только из однореберных графов, называется урожденной системой маршрутов.
В разделе 4.1 главы 4 завершена алгоритмическая классификация гачатая другими авторами) СОУОиР-пробпемы в классах графоидных шерграфов, индуцированных деревьями.
Теорема 5. Пусть г, 5 — фиксированные натуральные числа, г 2 5. 1дача вычисления подинома НП только в одной точке р = 1/2 является Р-полной в следующих классах простых графоидных гиперграфов: а) вдуцированных деревьями степени г с системой маршрутов, состоящей из ;ревьев степени 5, при г>Ъ,з> 2; б) индуцированных деревьями диаметра г системой маршрутов, состоящей из деревьев диаметра 5, при г > 2, $ > 2. Во :ех остальных случаях СОКОС/Л-проблема полиномиально разрешима, а иенно: в) в классе простых графоидных гиперграфов, индуцированных :ревьями степени 2 с системой маршрутов, состоящей из деревьев степени
г) в классе графоидных гиперграфов, индуцированных произвольными ¡ревьями с вырожденной системой маршрутов.
Получены достаточные условия для системы маршрутов произвольного дерева Я, обеспечивающие полиномиальную разрешимость COVDUP-проблемы для графоидных гиперграфов, индуцированных Я, причем эти условия в определенном смысле являются пороговыми для эффективной разрешимости COVDUP-nроблемы.
Если в качестве маршрутов берутся все подграфы индуцирующего графа Я, обладающие некоторым теоретико-графовым свойством О, то в этом случае длина входного слова задачи, связанной с индуцированным графоидным гиперграфом G = (Т', Р), определяется только размерностью графа Я. В подобных ситуациях будем говорить, что G индуцирован графом Я и свойством С*. СОVD{//'-проблема для таких реберно графоидных гиперграфов G трансформируется в алгоритмически менее сложную оптимизационную задачу покрытия, называемую в дальнейшем DIM-проблемой. В общем виде £>/Л/-проблема заключается в определение наименьшей мощности сПт(Я, G) оптимального покрытия множества веришь Т ребрами из Р, которые Moiyr быть взяты в качестве реберных множсстг оптимальной системы маршрутов % ъ Н, обладающих свойством О Следующие три свойства G наиболее интенсивно изучались в связи с DIM-проблемой: "быть расщепляемым графом", "быть пороговым графом", "был полным графом". Обозначим эти свойства соответственно Sp, Th, CI Величины dim(//, Sp), сНт(Я, Th), dim(/7, СГ) называются расщепляемой пороговой и кликовой размерностями графа Я. Хорошо известно, чтс проблема вычисления кликовой размерности в общем случае ///'-трудная, не полиномиально разрешима в классах пороговых и расщепляемых графов i тривиальна для двудольных графов; проблема вычисления noporoBoi размерности /W-трудная в общем случае и полиномиально разрешима дл5 двудольных графов, а задача распознавания "dim(//, Th) < к" является NP-полной в классе расщепляемых графов при любом фиксированном к > 3 v полиномиально разрешимой в общем случае при к < 2 (V. Chvatal, Т. Ma, J Spinrad, М. Yatinakakis, Т. Ibaraki и др.). Поэтому следующие результаты и: раздела 4.2 главы 4 завершают алгоритмическую классификацию DIM проблемы для ряда Sp, Th, CI.
Теорема 6. Задача вычисления расщепляемой размерности является NP трудной в классе двудольных графов и разрешима за линейное время дл) деревьев. Задача распознавания '^¡ш(Я, Sp) < к" является W-полной npi любом фиксированном к > 3, но является полиномиально разрешимой при к: 2 и при любом фиксированном к для двудольных графов.
Что касается REL-проблемы для вершинно (реберно) графоидноп гиперграфа G, индуцированного графом Я и свойством О, то она изучалас! исключительно для свойства С* "быть связным (связным остовным подграфом, порожденным вершинным (реберным) множеством графа Я1
При этом величина pt\VHf) (h^H, рг(ЕЯ))), равная комбинаторной
надежности гиперграфа G, называется резидуальной (оллполюсной) надежностью графа Я, а полином КН гиперграфа G называется полиномом резидуальной (оллполюсной) надежности графа Я. Очевидно, резидуальная (оллполюсная) надежность графа Я равна вероятности связности Н. Кроме того, оллполюсная надежность графа Я равна зеличиЕ{е связного надежностного покрытия вершинно графоидного гиперграфа, индуцированного графом Я с вырожденной системой маршрутов.
Особенность проблемы вычисления оллполюсной надежности включается в том, что копугевой комплекс [Т, Рй], в котором М'ю(Р) ;остоит из всех реберных множеств остовов графа Я, является кографическим латроидом и, следовательно, шеллинговым комплексом. А это, в свою очередь, означает существование квазиполиномиального алгоритма, )ычисляющего оллполюсную надежность произвольного графа. Такая кобенность обусловила разработку многочисленных эффективных методов триближенного вычисления полиномов оллполюсной надежности и их равномерной оценки (что отражено в различных монографиях и обзорных ;татьях). Результатов же по алгоритмической сложности задачи вычисления юлинома оллполюсной надежности было накоплено немного: установлена ее галиномиальная разрешимость для полных и полных двудольных графов, а акже для очень узких подклассов планарных графов; доказана #Р-трудность той задачи в общем случае, а также в классе планарных графов (Е. Gilbert, ). Vertigan, Т. Politof, J. Provan и др.). Недоказанным оставалось налогичное утверждение для гамильтоновых графов, высказанное в виде ипотезы; невыясненной оставалась динамика этой задачи в классах рафов, близких к полным и полным двудольным. В разделе 4.1 главы 4 одтверждена гипотеза, и в качестве следствий доказано, что задача ычисления полинома оллполюсной надежности только в одной точке р = /2 является #Р-подной в классах расщепляемых графов и. двудольных рафов сколь угодно большого обхвата.
Особенность проблемы вычисления резидуальной надежности «слючается в том, что в вершинно графоидном гиперграфе G = (Г, Р), ндуцированном графом Я и свойством "быть порожденным связным одграфом", множество ребер Р может не совпадать со своим замыканием \ Такая особенность делает неприменимыми традиционные методы, гпользуемые, например, для расчета и оценки оллполюсной надежности. В азделе 4.3 главы 4 на базе новых подходов завершена классификация в тответствии с алгоритмической сложностью проблемы вычисления гзидуальной надежности основных расширений класса пороговых графов, зчатая в работах С. Stivaros, F. Boesch, Sutner К., С. Süffel.
Теорема 7. Задача вычисления полинома резидуальной надежности только в одной точке р = 1/2 является #Р-полной в классах бокспороговых и квазипороговых графов.
Теорема 8. Проблема вычисления резидуальной надежности полиномиально разрешима в классах доминантно-пороговых, квазидоминантно-пороговых, матрогенных и матроидальных графов.
При этЬм теорема 8 получена на основе единого декомпозиционного подхода, позволяющего резидуальную надежность графа полиномиально вычислять через резидуальную надежность его неразложимых (относительно операции композиции) компонент. Этот подход может применяться также для любого свойства графов, которое наследственно относительно композиции или подвергалось бы легко обозримым изменениям, делающим это свойство наследственным.
ЗАКЛЮЧЕНИЕ
В диссертации разработаны теоретические основы решения задач математической теории надежности, имеющих комбинаторную природу. Основные результаты состоят в следующем.
1. Получена классификация в соответствии с алгоритмической сложностью проблем комбинаторной надежности и надежностного покрытия в классах гиперграфов с ограниченными степенными параметрами. Тем самым решена открытая задача алгоритмической сложности двойственных проблем надежности для униформных гиперграфов с разреженной реберной структурой [17,21, 25].
2. Определен аналог регулярных гиперграфов в классе всех гиперграфов — реберно-регулярный гиперграф — и введены операции сдвигов на гиперграфах; доказано, что эти операции не увеличивают коэффициентов полиномов надежности и за полиномиальное время с их помощью гиперграфы и униформные простые гиперграфы можно преобразовать соответственно в реберно-регулярные и регулярные гиперграфы. Получены структурные характеризации путей и сечений регулярных и реберно-регу-лярных гиперграфов, позволяющие эффективно вычислять их полиномь надежности. На этих результатах базируется новый метод полученш полиномиально вычислимых нижних оценок основных полиномо1 надежности гиперграфов, синтезирующий в себе два отдельнс развивающихся направления исследований: приближешгую оценку полиномов надежности и определение нетривиальных классов гиперграфов,) которых проблемы надежности полиномиально разрешимы. Как следстви» решена ранее изученная в частных случаях задача структурно! характеризации гиперграфов, имеющих наименьшие коэффициента полиномов надежности в классах униформных гиперграфов I
фиксированными числами вершин и ребер, а также усилены известные юзультаты о полиномиальной дуализации регулярных гиперграфов и :войствах регулярных гиперграфов, индуцирующих матроидные комплексы 18, 19, 33,34,41].
3. На базе унификации теорем о переключениях и обобщении их на иперграфы разработана единая теоретическая основа для решения задач интеза максимально надежных элементов в классах гиперграфов с [редписанными значениями переключательно совершенных параметров. 1араллельно дано конструктивное решение задачи существования связных иперграфов с предписанными степенными последовательностями, получены ритерии их факторизуемости, определены максимальные множества иперграфов, в которых основные виды степенных последовательностей тановятся переключательно совершенными (полученные ранее в этой >бласти результаты были ограничены, в основном, 2-униформными иперграфами, т. е. графами и мультиграфами). Усилены известные ;остаточные условия о тотальной совместимости пар целочисленных екторов, совпадающих соответственно с последовательностями степеней ершин и ребер гиперграфов [1, 2, 5, б, 10, 12, 26,29, 31].
4. Определена новая модель мультитерминальной надежности — юнотонный граф, представляющий собой графовую суперпозицию простых иперграфов. Монотонные графы позволяют моделировать сложные системы
сетевой структурой и произвольной монотонной логикой )ункционирования в вершинах; они обобщают все традиционные модели [ультитерминальной надежности — ¿-тривиальные графы, являющиеся их пециальными случаями. На монотонные графы распространена теория ;оминирования. Это позволило достичь максимально возможной онденсации символьных выражений надежности монотонных графов на базе ыявленных свойств их функции доминирования, а также определить для них раничные случаи существования псевдополиномиальных и вазиполиномиальных алгоритмов решения проблемы комбинаторной 1адежности. Параллельно выявлена клаттерная природа всех ранее известных езультатов о доминировании ¿-тривиальных графов. Получена структурная арактеризация основных подклассов монотонных графов, обладающих юроговой живучестью, что завершает решение открытой задачи описания '-тривиальных графов с пороговой живучестью. Решена проблема азмерности, возникающая при реализации методов ортогонализации улевых функций, применяемых к анализу надежности монотонных графов 8, 11, 13, 14, 16, 22, 23, 27,28, 36—39].
5. Усилены известные результаты об алгоритмической сложности роблем вычисления полиномов надежности в классах графоидных иперграфов. Это позволило определить границы, разделяющие #/'-полные и
полиномиально разрешимые случаи проблемы вычисления полиномг надежностного покрытия в классах графоидных гиперграфов индуцированных деревьями ограниченной степени и диаметра, и проблемь вычисления полинома оллполюсной надежности в классах графов, близких i полным и полным двудольным графам. Завершена алгоритмическа» классификация оптимизационной проблемы покрытия графоидны> гиперграфов, индуцированных свойствами "пороговость" \ "расщепляемость". Проблема вычисления полинома резидуальноГ надежности решена для основных расширений класса пороговых графов; npi этом соответствующие результаты о полиномиальной р<",решимост1 получекы на основе единого декомпозиционного подхода [3, 4, 7, 9, 15, 20 24, 30,32,35,40].
РАБОТЫ, ОПУБЛИКОВАННЫЕ ПО ТЕМЕ ДИССЕРТАЦИИ
1. Тышкевич Р.И., Черняк А.А., Черняк Ж.А. Графы и степенньк последовательности. III Кибернетика. — 1987. — № б. — С. 12—19.
2. Тышкевич Р.И., Черняк А.А., Черняк Ж.А. Графы и степенньк последовательности. II //Кибернетика. — 1988. — № 2. — С. 1—13.
3. Черняк А.А. Псевдодоминантно-пороговые графы I // Весщ АН БССР Сер. <|нз.-мат. навук. — 1988. — № 4. — С. 37—43.
4. Черняк А.А. Псевдодоминантно-пороговые графы II // Весщ АН БССР Сер. ф1з.-мат. навук. — 1988.— № 5, —С. 18—22.
5. Тышкевич Р.И., Черняк А.А., Черняк Ж.А. Графы и степенны! последовательности. III // Кибернетика. — 1988. — № 5. — С. 1—8.
6. Chernyak А.А., Chemyak Z.A. Matrices with pres -d row, column and blocl sums //Combinatorica. — 1988. — Vol. 8, № 2. — P. 177—184.
7. Chernyak A.A., Chernyak Z.A. Pseudodomishold graphs // Discrete Math. —
1990. — Vol. 84. — P. 193—196.
8. Черняк А.А. Комбинаторно-графовый метод анализа надежности сложны: систем с монотонными булевыми функциями // Автоматика i телемеханика.— 1991. — №4. — С. 165—174.
9. Chernyak А.А., Chernyak Z.A. Split dimension of graphs // Discrete Math. —
1991. —Vol. 89, —P. 1—6.
10. Chernyak A.A., Chernyak Z.A. Joint realization of (0,1) matrices revisited / Linear Algebra and its Applications. — 1992. — Vol. 174. — P. 25—35.
11. Chernyak A.A., Chernyak Z.A. A unified domination approach for reliabilit; analysis of networks with arbitrary logic // IEEE Trans. Reliab. — 1996. — Vol. 45, № 1, —P. 114—119.
12. Chernyak A.A., Chernyak Z.A. R-multihypergraphs with prescribed edg degree sequences II Discrete Mathem. — 1997. — Vol. 170. — P. 237—240.
i. Chemyak A.A., Chernyak Z.A. On complexity of computing the domination of binary systems // Discrete Appl. Mathem. — 1997. — Vol. 73. — P. 289— 295.
1. Черняк A.A., Черняк Ж.А. Логико-вероятностный метод анализа надежности многозначных систем большой размерности И Автоматика и телемеханика. — 1998. — № 1. — С. 171—180.
i. Черняк A.A. Расщепляемые графы в задачах покрытия // Becui HAH Беларусь Сер. ф!з.-мат. навук. — 1998. — № 2. — С. 131—136.
). Черняк A.A. Ациклические монотонные графы: доминирование и надежность // Becui АН Беларуси Сер. ф!з.-тэхн. навук. — 1998. — № 3. —С. 108—114.
L Черняк A.A. Об алгоритмической сложности классической задачи надежности И Дискретный анализ и исследование операций. Серия 1. — 1998. — Т. 5, № 4. — С. 71—80.
!. Черняк A.A. Надежностные задачи покрытия для гиперграфов // Кибернетика и системный анализ. — 1999. — № 1. — С. 106—119.
К Черняк A.A., Черняк Ж.А. Надежность бинарных систем Н Дискретная математика. — 1999. — Т. 11,№ 1. — С. 129—139.
). Черняк A.A. Алгоритмическая сложность графовых задач надежности // Becui HAH Беларусь Сер. ф!з.-мат, навук. — 1999. — № 1. — С. 130— 135.
1. Черняк A.A. Двойственные задачи надежности к-униформных гиперграфов // Доклады HAH Беларуси. — 1999. — Т. 43, № 2. — С. 31— 32.
!. Черняк A.A. K-терминальные сети с пороговой системой связности // Becui HAH Беларусь Сер. ф1з.-мат. навук. — 1999. — № 3. — С. 122—126.
I. Черняк A.A. Универсальная графовая модель циклических сетей и их надежность // Проблемы передачи информации. —1999. — Т. 35, № 2. — С. 90—99.
к Черняк A.A. Резидуальная надежность Р-порогОвых графов // Дискретный анализ и исследование операций. Серия 1.—1999. — Т. 6, № 3. — С. 76— 86.
>. Черняк A.A. Надежность гиперграфов ограниченной степени // Becui HAH Беларусь Сер. фЬ.-тэхн. навук. — 1999. — № 4. — С. 84—93.
>. Chernyak A.A. Interchange theorems for hypergraphs and factorization of their degree sequences // European J. Combinatorics. — 1999. — Vol. 20. — P. 17— 27.
1. Черняк A.A. Структурно-сложные системы с пороговой живучестью // Дискретная математика. — 1999. — Т. 11, № 4. — С. 65—78.
?. Черняк A.A. Доминирование циклических монотонных графов // Математические заметки. — 2000. — Т. 67, № 2. — С. 288—294.
29. Черняк A.A. Синтез связных гнперграфов с предписанными napaMeTpaMV // Доклады HAH Беларуси — 1999. — Т. 43, № 6. — С. 38—41.
30. Черняк A.A., Черняк Ж.А. Полиномы надежности графоидны> гиперграфов //Becui HAH Беларуси Сер. фв.-тэхн. навук.—2000. —№ 1 — С. 76—80.
31. Chernyak A.A., Chernyak Z.A. Potentially connected degree sequences: th< unified approach // Graphen und netzwerke — theorie und anwendungen . Wiss. Koll.TH Ilmenau. —Ilmenau, 1988, —P. 171—174.
32. Тышкевич Р.И., Черняк A.A. Пороговые разложения булевых функций г графов // Комбинаторно-алгебраические и вероятностные методь дискретной математики: Сб. научн. тр. / Горьковский университет. — Москва: Наука, 1989. — С. 111—129.
33. A.c. 1472915 СССР, МКИ G 06 F 15/20. Устройство для исследопаниз графов. / А.И.Волошаненко, A.A. Черняк, М.Ш.Фелер, H.H. Рожкеви* (СССР). — № 4304960/24-24; Заявлено 08.09.87; Опубл. 15.04.89, Бюл. К 14.
34. A.c. 1451715 СССР, МКИ G 06 F 15/20. Устройство для исследовани; графов. / А.И.Волошаненко, A.A. Черняк, H.H. Рожкевич, В.И. Исае) (СССР). —Ks 4215158/24-24; Заявлено 24.03.87; Опубл. 15.01.89, Бюл. К 2.
35. Черняк A.A. Эффективный метод расчета надежности одного класс; сложных систем // Проблемы качества и надежности изделий электронно1 техники, радиоэлектронной аппаратуры и средств управления: Тез. докл респ. конф. — Минск, 1988. — С. 170.
36. Chernyak A.A. A new graph-combinatorial method for reliability analysis о monotone graphs // Proc. в1* Int. Simposium on Reliability in electronics Budapest. — 1991. —Vol. I. —P. 135—140.
37. Chernyak A.A., Chernyak Z.A. Discrete mathematics and reliability of comple; systems // Europ. Conf. on Math, for Industry: Abstracts / Prague, 1994. — Г 30.
38. Chernyak A.A., Chernyak Z.A. Universal reliability graph model of cycli networks // 4th Int. Congress on Industrial and Appl. Mathem.: Abstracts Edinburg, Scotland, 1999. — P. 248.
39. Chemyak A.A., Adintsova A.I. Monotone graphs with threshold survival // 4' Int. Congress on Industrial and Appl. Mathem.: Abstracts / Edinburg, Scotlanc 1999. —P. 234.
40. Камано Э.С., Черняк A.A. О пороговой и копороговой размерност расщепляемых графов / АН БССР. — Минск, 1990. — 15 с. — Деи. ВИНИТИ 12.01.90, № 220-В90 // Becui АН БССР. Сер. ф1з.-мат. навук. -1990. №5.— С. 118.
41. Черняк A.A. Регулярные гиперграфы, индуцирующие матроидные комплексы / HAH Беларуси — Минск, 1999. — 14 с. — Деп. в ВИНИТИ 29.03.99, №933-В99 // Becui HAH Беларусь Сер. ф]з.-мат. навук. — 1999. — №3, —С. 129.
РЕЗЮМЕ Черняк Аркадий Александрович
Комбинаторные методы математической теории надежности
Ключевые слова. Надежность гиперфафов, полиномы надежное! фафов и гиперфафов, #Р-полные перечислительные задач полиномиальные алгоритмы.
Объект исследования. Структурно-сложные системы, для которь возникает необходимость разработки комбинаторных методов анали: надежности.
Цель работы. Разработка универсальных комбинаторных моделей методов анализа надежности гиперфафов с предписанными структурны?, свойствами.
Методы исследования. В работе применяются методы теории сложное вычисления, теории фафов и гиперфафов, булевой и пороговой логик комбинаторной теории бинарных матриц, теории надежное коммуникационных сетей.
Полученные результаты и их новизна. Получена алгоритмическ классификация двойственных проблем надежности в классах гиперфафов офаниченными степенными параметрами. Разработан общий мет получения эффективно вычислимых нижних оценок основных полином надежности гиперфафов. Разработана единая теоретическая основа д решения задач синтеза максимально надежных элементов в класс гиперфафов с предписанными значениями переключательно совершенн! параметров. Построена теория доминирования для анализа надежное монотонных фафов, обобщающих традиционные модели сетевой наде поста; получены эффективные характеризации основных подкласс монотонных фафов с пороговой живучестью. Завершена алгоритмичеа классификация проблем вычисления полиномов надежности в подкласс фафоидных гиперфафов.
Степень использования н области применения. Методы и апгорлп работы могут быть использованы в задачах анализа и синтеза сложи систем, при оптимальном проектировании высоконадежных систем структурными офаничениями, в теоретических исследованиях прикл:. лным проблемам комбинаторного анализа.
РЭЗЮМЭ Чарняк Аркадзш Аляксандравт
Камбшаторныя мстады матэиатычнай тэорьа надзейнасщ
Клгочавыя словы. Надзейнасць пперфафау, палшомы надзейнасщ рафау I пперфафау, #/>-цяжк1я перал!чальныя задачы, палнтпальныя лгарытмы.
Аб'ект даследвання. Структурна-складаныя сютэмы, для яюх узшкае еабходнасць распрацоук! камбшаторных метадау ан&гаа надзейнасць
Мэта работы. Распрацаука ушверсальных камбшаторных мадэляу I етадау анашза надзейнасщ пперфафау з прадтсаным! структурным! ласшвасцямь
Метады даследвання. У рабоце ужываюцца метады тэорьй вьш.чальнай кладанасш, тэорьн фафау \ пперфафау, булявой 1 парогавай лопцы, шб'шаторнай тэорьп бшарных матрыц, тэорьн надзейнасц'1 камушкацыйных ;так.
Атрыманыя вын'па 1 ¡к нав^зна. Атрымана алгарытм^чная клаафкацыя ааютых праблем надзейнасщ у класах пперграфау з абмежаваным1 гупенным! параметрам!. Распрацаваны агульны метад атрымання эфектыуна >Ш1чных 1пжшх ацэнак асноуных палшомау надзейнасщ пперграфау. аспрацавана адзшая тэарэтычная аснова для вырашэння задач сштэза акс'1малыга надзейных элементау у класах пперфафау з прадшсаным! тчэнням1 пераключальна дасканалых параметрау. Пабудавана тэорыя мшавання для аналЬа надзейнасщ манатонных фафау, абагульняючых )адыцыйныя мадэл1 сеткавай надзейнасщ; атрыманы эфектыуныя фактарызацьп асноуных падкласау манатонных фафау з парогавай ывучасцю. Завершана алгарьпшчная клаафшацыя праблем вьипчэння шномау надзейнасщ у падкласах фафощных пперфафау.
Ступень выкарыстання 1 галшы убывания. Метады 1 алгарытмы 1боты могуць быць выкарыстаны у задачах аналпа 1 сштэза складаных стэм пры аптымальным праектаванш высоканадзейных с1с*тэм са руктурным1 абмежаванням!, у тэарэтычных даследваннях па прыкладным >аблемам камбшаторнага ан&гпза.
SUMMARY Arkadi A. Chernyak
Combinatorial methods of mathematical reliability theory
Keywords, Reliability of hypergraphs, reliability polynomials of graphs ai hypergraphs, ///'-complete enumeration problems, polynomial algorithms.
Object of research. Structurally complex systems for which the necessity developing combinatorial methods of reliability analysis appears.
Aim of research. Development of universal combinatorial models a methods for reliability analysis of hypergraphs with prescribed structui properties.
Methods of research. Methods of computational complexity theory, graph a hypergraph theory, Boolean and threshold logic, combinatorial theory of bina matrices, network reliability theory.
The obtained results and their novelty. The algorithmical classification the dual reliability problems for hypergraphs with restricted degree parameters obtained. The general method for effective computing lower bounds of the mi reliability polynomials of hypergraphs is developed. The unified approach 1 solving problems of constructing the most reliable hypergraphs with prescrib values of switching perfect parameters is presented. The domination theory i reliability analysis is extended to the monotone graphs generalizing traditioi models of network reliability; the effective characterizations of the main subsets the monotone graphs with threshold survival are given. The algorithmi classification of the problems of computing reliability polynomials in subclasses graphoid hypergraphs is completed.
The use and fields of applications. The presented methods and algorithms c be used in analysis and synthesis of complex systems, in optimal design of relia! systems with structural restrictions, in theoretical investigations on appl problems of combinatorics.
