Algorithm for constructing T-irreducible extension of polygonal digraphs.pdf Под ориентированным графом (или орграфом) понимается пара G = (V, а), где V - конечное непустое множество вершин; а - отношение на множестве V (дуги орграфа). Вложение орграфа G = (V, а) в орграф H = (W, в) - это взаимно однозначное отображение : V ^ W, такое, что (Vu,v G V)((u,v) G а ^ (^(u),^(v)) G в). При этом говорят, что орграф G вкладывается в орграф H. Расширение орграфа G = (V, а) - это орграф H = (W, в), где |W| = | V| + 1, такой, что орграф G вкладывается в каждый максимальный подграф орграфа H [1]. Тривиальное расширение (ТР) орграфа G - это соединение G + w орграфа G с вершиной w, обозначается через ТР^). Т-неприводимое расширение (ТНР) орграфа G - это расширение орграфа G, полученное удалением максимального множества дуг из ТР^) [2]. Ориентированные графы представляют собой математические модели дискретных систем [3]. Вопросы отказоустойчивости на данный момент сформулированы в терминах теории графов [3, 4]. Конструкции оптимальных расширений, которыми являются Т-неприводимые расширения, широко применяются в диагностике дискретных систем и криптографии [5]. В общем случае задача определения того, является ли орграф H расширением для орграфа G, является NP-полной, а задача поиска ТНР по заданному орграфу G не принадлежит классу NP [6]. Контур в орграфе - это простой циклический путь. Контур, состоящий из n вершин, обозначим через Cn = v0v1... vra_iVo, считая v0 выбранной начальной вершиной. Многоугольным орграфом порядка n называется всякий орграф M, полученный переориентацией некоторых дуг контура Cn [7]. Далее все арифметические операции над индексами вершин в многоугольных орграфах будем производить по модулю n. Следующий алгоритм строит одно из ТНР для многоугольного орграфа. Алгоритм Дан многоугольный орграф M = (Z, y). Построим его ТНР следующим образом: 1. Добавим к M вершину w. 2. Для каждой вершины v Е Z добавим дуги следующим образом: - если v Е Z является источником, то добавим дугу (v,w); - если v Е Z является стоком, то добавим дугу (w,v); - если v Е Z такова, что d+(v) = 1 и d_(v) = 1, то добавим дуги (v,w) и (w,v). Обозначим построенный орграф H0 = (W, в0). Положим k = 0. 3. Рассматриваем вершины многоугольного орграфа M, имеющие степени исхода и захода 1, в порядке возрастания их индексов. Пусть, для определённости, вершины пронумерованы таким образом, что для вершины vi Е Z, имеющей степени исхода и захода 1, существуют vi_1,vi+1 Е Z, такие, что (vi_1, vi), (vi, vi+1) Е y. По построению в п. 2 алгоритма вершина vi соединена с вершиной w дугами (vi,w) и (w,vi) (рис. 1). Пунктирная линия на рис. 1, соединяющая две вершины, означает, что между ними может быть как одна дуга в любом из направлений, так и две дуги, если одна из инцидентных вершин является вершиной w. Возможны следующие случаи: Случай А: многоугольный орграф M вкладывается в орграф H - vi_1 - (w, vi). Строим орграф Hfc+1 = (W,ek+1), такой, что Hfc+1 = Hk - (w,vi), ^fc+1 = вк - (w,vi). Далее алгоритм продолжает работу с орграфом Hk+1, переходим к следующей вершине в п. 3. Случай B: многоугольный орграф M вкладывается в орграф Hk - vi+1 - (vi, w). Строим орграф Hk+1 = (W,вк+1), такой, что Hk+1 = Hk - (v,w), вк+1 = вк - (vi,w). Далее алгоритм продолжает работу с орграфом Hk+1, переходим к следующей вершине в п. 3. Случай С: орграф M не вкладывается ни в орграф Hk-vi_1 - (w, vi), ни в орграф Hk - vi+1 - (vi, w). Не производим никаких действий, переходим к следующей вершине в п. 3. Рис. 1. Иллюстрация п.3 алгоритма Уточнение: если в многоугольном орграфе M каждая вершина является либо источником, либо стоком, то п. 3 алгоритма пропускается. После того как все вершины в п. 3 рассмотрены, алгоритм завершает свою работу. Построенный из орграфа H0 орграф , где k - количество дуг, удалённых в п. 3 алгоритма, является ТНР для многоугольного орграфа M. Асимптотическая сложность алгоритма составляет O(n3), где n = |Z| -количество вершин в многоугольном орграфе M. Доказана теорема о корректности предложенного алгоритма. Алгоритм позволяет также получить верхние и нижние оценки количества добавленных дуг в ТНР для многоугольных орграфов.

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