ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2013, том 49, № 2, с. 106-111
ЗАМЕТКИ И ПИСЬМА
ОБ ИСПОЛЬЗОВАНИИ ТЕОРИИ ГРАФОВ ПРИ АНАЛИЗЕ ИННОВАЦИЙ НА ПРЕДПРИЯТИИ*
© 2013 г. А.И. Вересков
(Москва)
1. ЗАДАЧА СОГЛАСОВАНИЯ ИННОВАЦИОННЫХ РЕШЕНИЙ
Приведем формальную постановку задачи, возникающей при оценке реализуемости инновационных проектов на предприятии. Рассмотрим прямоугольную таблицу Т размера М х Ы, в каждой ее ячейке с координатами (т, п) имеется Ктп > 1 элементов (вершин графа). Обозначим их (т, п, к), число к ! {1,..., Ктп} соответствует номеру вершины внутри ячейки. В каждой строке и каждом столбце таблицы Т между вершинами из разных ячеек задано бинарное отношение 8, означающее взаимную допустимость элементов и определяющее систему ребер неориентированного графа (Т 8)1. Так, условие (1, 2, 5)8(1, 4, 2) означает, что элемент 5 ячейки (1, 2) и элемент 2 ячейки (1, 4) совместимы и ребро [(1, 2, 5), (1, 4, 2)] ! 8 (вершины из одной ячейки несовместимы по определению). Понятие совместимости, а вместе с ним и отношение 8, не распространяется на ячейки, не входящие в одну горизонталь или вертикаль (ячейки (1, 1) и (2, 3)). Отношение 8 симметрично, но не транзитивно: условия (1, 2, 5)8(1, 4, 2) и (1, 4, 2)8(1, 6, 3) не означают, что (1, 2, 5)8(1, 6, 3).
Если в каждой ячейке (т, п) выбрать по одному элементу ктп > 1 или не выбрать ни одного ктп = 0, то в результате образуется числовая матрица х размера М х Ы:
х I I ктп II, ктп ^{0,.--, Ктп}. (1)
Имеет место взаимно-однозначное соответствие между всевозможными матрицами (1) и подмножествами Я вершин из Т, такими что в Я входит не более одной вершины из каждой ячейки (т, п); смысл обозначений х(Я) и Я(х) очевиден.
Назовем х вида (1) 8-матрицей (согласованной), если условия 8 выполнены для всех выбранных элементов в каждой строке т = 1,., М:
(т п, ктп)8(т, Ч, ктд) 6ктт ктд >1, Ч Ф Щ (2)
и в каждом столбце п = 1,., Ы:
(т, п, ктп)8(р, п, крп) 6ктт кРп >1, р Ф т. (3)
Существование хотя бы одной 8-матрицы, в которой заполнены все МЫ ячеек (Уктп > 1), свидетельствует о том, что инновационный проект удовлетворительно согласуется с наличной структурой предприятия (изменения, необходимые для осуществления проекта, могут быть реализованы) (Вересков, Зотов, Пономарева и др., 2012, с. 3-14). Если из таблицы Т не удается извлечь такой матрицы, то для анализа ситуации окажутся полезны 8-матрицы с небольшим числом нулей, указывающих экспертам на "узкие места" в системе "предприятие - инновация".
Пусть матрица х2 = 11 к2тп 11 получена из произвольной х1 = 11 к 1тп 11 заменой некоторых кхтп > 1 нулями (обозначим ее х2 ' х1), тогда
к1тп >1 & к2тп = к]пп \ 7(т п): к]пп >1, к1т = 0 (4)
* Работа выполнена при финансовой поддержке Российского гуманитарного научного фонда (проект 12-02-00325А).
1 Символ Т (название таблицы) используется также и для обозначения множества вершин графа; аналогично,
8 - бинарное отношение и порождаемое им множество ребер.
Если x1 - это S-матрица и x2 ' x1, очевидно, что x2 также принадлежит классу S, но представляет
меньший интерес, чем x1, для содержательного анализа, нацеленного на корректировку инновационного проекта (Вересков, Зотов, Пономарева и др., 2012). Поэтому сузим класс (2), (3), назвав М-матрицами (максимальными) те S-матрицы x, которые удовлетворяют дополнительному условию:
3 S-матрицы x' такой, что x ' x'. (5)
Принятые определения имеют параллели в общепринятой терминологии теории графов. Кликой называют максимальный полный подграф неориентированного графа, т.е. такой подграф, в котором все вершины попарно связаны ребрами (определение полноты) и который не является частью другого полного подграфа. Существуют алгоритмы, позволяющие отыскать все клики произвольного графа. Покажем, как их можно использовать для построения всех М-матриц x.
Расширим граф (T S) до (T, S'), дополнив множество S ребрами
n:, k^ (t, s, l) ] ! S \S + m ф t, n ф s, k .. ^ Kmn; l 1 .. ^ Kts . (6) Имеет место следующее утверждение.
Утверждение 1. Если x - это S-матрица, то R(x) порождает полный подграф в (T, S'). Верно и обратное утверждение: полному подграфу R соответствует S-матрица x(R). Если x - это M-матрица, то R(x) порождает клику в (T, S'); верно и обратное утверждение.
Первая половина утверждения следует из (2), (3), (6). Вторая - из первой, если заметить, что в силу (4) выражение x ' x' эквивалентно включению R(x) С R(x').
Таким образом, построив все клики графа (T S) мы получаем описание множества M-мат-риц таблицы T. Известно, что задача отыскания клик в неориентированном графе может быть сведена к построению максимальных независимых множеств (МНМ) в дополнительном графе.
2. АЛГОРИТМ ПОСТРОЕНИЯ МНМ
2.1. Нужный нам алгоритм приведен в (Кристофидес, 1978), однако в его описании и обосновании имеются неточности, которые необходимо исправить2. Упростим обозначения, принятые в (Кристофидес, 1978), отождествив вершины неориентированного графа G(X, Г) с их номерами X = {1,.. .,Ж}. Вершины x ! X, выбираемые для расширения Sk и обозначенные в тексте алгоритма как xik, будем записывать в виде xk.
Остановимся на определении МНМ (Кристофидес, 1978, с. 44, формулы (3.1), (3.2)). Применительно к графам с петлями эти определения не эквивалентны. Приведем то, которого мы будем придерживаться. Независимым множеством (НМ) называется S 3 X, если в S не содержится пара вершин, соединенных ребром. МНМ - это такое НМ, которое не является подмножеством другого НМ. В силу этого определения граф G(X, Г) с петлей X = {1,2}, Г(х 1) = {x 2}, Г(х 2) = {x 1, x 2} содержит два МНМ: {1} и {2}. Рассматриваемый алгоритм вырабатывает именно эти множества. Наличие петель не влияет на ход алгоритма: если из графа удалить петли, то совокупность МНМ от этого не изменится.
Алгоритм построения МНМ (Кристофидес, 1978).
Шаг 1. Положим S0 = Q- = 0, Q + = X, k = 0.
Шаг 2 (шаг расширения). Выбираем xk, следуя одному из двух правил (два варианта алгоритма): AL1 - выделяем произвольную вершину xk ! Q+; AL2 - находим x ! Q- с минимальным значением показателя | T(x) П Q+| и выбираем xk ! T(x ) П Q+. Формируем Sk+1, Q-+1, Q++1, оставляя Q-, Q+ нетронутыми:
Sk+1 = Skи{xk}, Q-+1 = Q-\r(xkX Q++1 = Q+\({xk} ,r(xk)).
Положим k = k +1.
2 Считая, что читатель знаком с исходным текстом, мы цитируем его лишь по мере надобности. Отме-
тим прежде всего очевидные опечатки. В начале разд. 2.3.1 формулу П Qk = 0 следует читать как
и Г(£к)) П Qk = 0, в конце раздела вместо Q- = 0 должно быть Q ~ = 0.
Шаг 3 (проверка 1). Если удовлетворяется условие
Эх ! Q-: C(x) ПQ+ = 0, (7)
то переходим к шагу 5, иначе - к шагу 4.
Шаг 4 (проверка 2). Если Q+ = Q- = {, то Sk - МНМ; переходим к шагу 5.
Если Q+ = 0, Q- Ф 0, то также переходим к шагу 5, иначе - к шагу 2.
Шаг 5 (возвращение). Положим k = k - 1. Удалим xk из Sk+1, чтобы получить Sk. Исправим Q-и Q+, удалив xk из Q+ и добавим ее к Q-. Если k = 0 и Q+ = 0, то алгоритм прекращает работу (т.е. к этому моменту все МНМ построены), иначе переходим на шаг 3.
Вариант AL2 (частный случай по отношению к AL1) нацелен на уменьшение числа итераций, необходимых для завершения работы алгоритма.
Пример 1. Приведем протокол работы AL2 в графе с X = {1, ...,5}, Г = {(i, i + 1), i =1, .,4}:
Sо = Q- = 0, Q +={1, .,5}, k =0; xо = 3, S1 = {3}, Q- = 0, Q + = {1,5}, k =1; x 1 = 5, S2={3,5}, Q° = 0, Q+={1}, k = 2; x2=1, S3= {3,5,1}-MHM, Q- = Q + = 0, k =3; k =2, S2= {3,5}, Q° = {1}, Q + = 0; k =1, S1 = {3}, Q- = {5}, Q+={1}; k =0, Sо = 0, Qо = {3}, Q+= {1,2,4,5}; xо = 2, S1 = {2}, Q- = 0, Q +={4,5}, k = 1; x 1 = 4, S2 = {2, 4} - MHM, Q° = Q + = 0, k = 2; (8)
k =1, S1 = {2}, Q-={4}, Q +={5}; x 1 = 5, S2 = {2,5}-MHM, Q° = Q + = 0, k = 2; k =1, S1 = {2}, Q- = {4,5}, Q + = 0; k = 0, S0 = 0, Q о = {3, 2}, Q +={1,4,5}; x0=1, S1 = {1}, Q- = {3}, Q + = {4,5}, k =1; x 1 = 4, S2 = {1,4}- MHM, Q° = Q + = 0, k =2; k =1, S1 = {1}, Q - = {3, 4}, Q+={5}; k = 0, S0 = 0, Q о = {3, 2,1}, Q +={4,5}.
Все МНМ построены, однако критерий k = 0& Q + = 0 (прекращения работы алгоритма) не выполнен. Согласно алгоритму необходимо перейти на шаг 3, где Г(1) ПQ + = 0, затем - на шаг 5 при k = 0. Индекс k обращается в -1, и все рекуррентные определения теряют смысл. При описании алгоритма не учтено, что и после построения всех МНМ возможно Q + Ф 0.
Приведенный пример не является чем-то исключительным, он допускает различные обобщения. Пусть, например, X = {1,2, X'}, где X' - произвольное множество вершин, а Г(1) = {2}; при этом безразлично, будет ли Г(2) П X' = 0. Здесь и в дальнейшем будем нумеровать вершины x0 в порядке их использования алгоритмом. Если xd = 1, x02 = 2, то после построения всех МНМ окажется, что Qо = {1, 2}, Q + = X', Г(1) ПQ + = 0, и снова k = - 1.
В дальнейшем мы убедимся, что критерий прекращения работы алгоритма можно сформулировать следующим образом:
k = 0 & (Q + = 0 V (7x ! QUx) ПQ + = 0)). (9)
Далее, обоснование алгоритма существенно опирается на следующее положение: множество Q- состоит из тех вершин, которые уже использовались для расширения множеств3 Sk. Ошибочность этого положения обнаруживается на шаге (8): вершина 3 е Q- не использовалась указанным образом, она была взята лишь для расширения S0. Вершины 1 и 3 входили в S3 = {3, 5,1}, но наличие S3 вида {3, p, 1}, вообще говоря, не позволяет корректно провести рассуждение, предложенное в (Кристофидес, 1978). Уточнять цитированное утверждение и с его помощью давать обоснование алгоритма было бы слишком сложно, поэтому мы пойдем иным путем.
2.2. Пусть (У) - подграф графа G(X, Г), порожденный множеством Y 3 X, <X> = G(X, Г); 2(Y) - совокупность МНМ графа (Y), 2(0) = 0. Наша цель доказать, что AL1 (а значит, и его частный случай AL2) вырабатывает 2(X). Поясним ход дальнейших рассуждений, используя граф с X ={1,...,4}, Г = {(i, i + 1), i =1,2,3}.
Пример 2. Пусть работа AL1 начинается с x ° = 1.
Этап I. Далее выявляются МНМ подграфа {qQ= \{1, 2}) = ({3, 4}), т.е. {3} и {4}; добавляя их к S1 = {1}, AL1 строит МНМ {1, 3}, {1,4} е 2(X).
Этап II. Затем алгоритм формирует Q += X\{1} = {2,3,4} и переходит к анализу подг
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.