12.4. Реализация цикломатической матрицы и матрицы сечений

В этом разделе обсуждается задача построения неориентированного графа, имеющего данную систему циклов и сечений. Не нарушая общности, можно допустить, что нам задаются базисные матрица сечений или базисная цикломатическая матрица графа, который необходимо построить.

Предположим, что базисная цикломатическая матрица по отношению к остову Т. Тогда ее можно записать в виде где F и U относятся к остову Т и соответствующему ко-остову. Из определения следует, что ненулевые элементы в каждой строке F соответствуют ветвям, которые образуют в остове Т путь между концевыми вершинами соответствующей хорды. Другими словами, каждая строка F соответствует пути в остове Т. По этой причине F называется матрицей путей дерева по отношению к Т. При заданной матрице F из выражения (6.13) известно, что . Таким образом, можно видеть, что реализации не являются независимыми задачами. Обе они эквивалентны реализации F как матрицы путей дерева.

Существенной частью процесса реализации F является определение структуры дерева, имеющего ветви, соответствующие таким столбцам F, что путь в дереве, описываемый каждой строкой из F, присутствует в этом дереве. Ясно, что задача построения искомого графа по определенному таким образом дереву обязательно влечет за собой введение хорд между соответствующими вершинами для каждой строки матрицы F. Теперь обсудим алгоритм касающийся реализации матрицы F как матрицы путей в дереве неориентированного графа

12.4.1. Подготовка

Сначала рассмотрим правила, которые можно использовать для упрощения матрицы F, перед тем как приступить к ее реализации. Если матрица F является блочной, т. е. представимой в виде

то каждую из подматриц можно реализовать отдельно и, чтобы получить искомое дерево Т, можно соединить произвольно реализованные подграфы (деревья). Если в матрице F имеется много идентичных строк, это означает наличие параллельных хорд в графе G. При реализации соответствующего дерева Т все строки, за исключением одной, можно удалить из матрицы F. Строку с единственным ненулевым элементом можно также исключить, поскольку она не накладывает ограничений на взаимосвязь ветвей дерева Т.

В случае когда присутствует особая ветвь в единственном к? заданных путей, реализации дерева можно достичь после удаления

из матрицы F соответствующего столбца. Ветвь можно добавить позже к одному из концов соответствующего пути. Далее, если некоторые k столбцов матрицы F являются одинаковыми, то достаточно реализовать матрицу, полученную удалением из этих столбцов. Ветвь, соответствующая оставшемуся столбцу, позже заменяется множеством последовательно соединенных ветвей, упорядоченных произвольным способом. Используя перечисленные правила, сложность данной матрицы F можно снизить последовательным удалением избыточных строк и столбцов. Эта процедура называется подготовкой к реализации матрицы

12.4.2. Выделение концевых ветвей

Первым основным шагом в алгоритме для реализации матрицы F является идентификация концевой ветви дерева, реализующего матрицу F. Обсудим процедуру, позволяющую идентифицировать такую концевую ветвь. Эта процедура применима к любой матрице общего вида F, и если она допускает различные реализации, то существует по крайней мере одна реализация с выделенной ветвью в качестве концевой. Пусть — симметричная матрица, определяемая в виде

    (12.37)

где умножение и сложение выполняется в поле действительных чисел. Ясно, что элемент равен числу путей, задаваемых матрицей F, в которых присутствует как ветвь i, так и ветвь Предполагалось, что строка или столбец матрицы W соответствуют ветви дерева Т.

Допустим, что G — граф, реализующий данную матрицу соответствующий остов. Если рассматривать каждое ребро графа G как проводимость в 1 См и если является матрицей короткого замыкания результирующей -полюсной цепи по отношению к полюсной конфигурации Т, то можно видеть, что для Отсюда имеем следующие свойства, которые являются очевидными повторениями теорем 12.3-12.5:

Свойство 12.1. Если ветви и k образуют линейное дерево в указанном порядке, когда все другие ветви дерева Т короткозамкнуты,

Свойство 12.2. Пусть максимальное значение элементов в строке матрицы W равняется и пусть этот элемент М, - встречается одновременно в этой строке в позициях столбцов и только в них. Тогда ветви, соответствующие образуют поддерево дерева Т.

Свойство 12.3. Пусть наименьший элемент строки матрицы W равен где возможно, равно нулю. Пусть в этой строке наименьший элемент встречается одновременно в позициях столбцов

и только в них. Тогда ветви дерева Т, отличные от образуют поддерево дерева Т.

Для дальнейшего обсуждения введем следующие определения: -множество является множеством ветвей, которые образуют поддерево дерева Т, имеющее только одну вершину, общую со своим дополнением в дереве Т, и только одну ветвь из этого множества, называемую ведущей ветвью L-множества, инцидентную этой вершине.

Для иллюстрации приведенного выше определения отметим, что на рис. 12.8 ветви I, k, m и образуют -множество с ветвью I в качестве ведущей ветви, тогда как ветви k, m и не образуют L-множества.

Рис. 12.8. Иллюстрация L-множества.

В простейшем случае в качестве L-множества можно рассматривать концевую ветвь. Очевидно, что дополнением -множества по отношению к дереву Т является поддерево этого дерева Т. Для любой ветви , отличной от концевой ветви дерева Т, существуют два L-множества, причем каждое имеет ветвь в качестве ведущей.

Проверим условия, при которых концевая ветвь поддерева дерева Т может также быть концевой ветвью дерева Т. Пусть ветви дерева Т разделены на два таких множества и R, что ветви множества Т образуют поддерево дерева Т. Далее, пусть выполняются соотношения

Покажем, что концевая ветвь дерева, которое было бы получено замыканием накоротко всех ветвей множества R, является концевой ветвью дерева Т или Г, образованного ребрами, соответствующими ветвям дерева Т в графе, который -изоморфен данному графу. Если равенство

выполняется, то матрица F является блочной матрицей, а подматрицы матрицы F, соответствующие ветвям множеств S и R, можно реализовать раздельно. В таком случае концевая ветвь поддерева, построенного из ветвей множества S, может, очевидно, стать концевой ветвью Т в общей реализации.

С другой стороны, пусть существует некоторое для которого не равен нулю. Множество S можно разбить

на непересекающиеся L-множества, поскольку ветви множества R образуют поддерево дерева Т. Сначала докажем, что каждое из этих L-множеств является линейным поддеревом дерева Т.

Пусть в одном из L-множеств, имеющих в качестве ведущей ветви, существуют такие ветви s, и что образуют звезду, тогда как другие ветви дерева Т являются короткозамкнутыми. Поскольку пути, в которых присутствуют ветви как так и отличны от путей, в которых присутствуют ветви и поскольку ветвь присутствует в обоих типах путей, получаем

    (12.40)

Однако в соответствии с формулой Далее, все они являются ненулевыми. Поэтому неравенство (12.40) удовлетворить нельзя. Отсюда ветви должны входить в линейное поддерево дерева Т. Рассуждая далее, можно показать, что все ветви в каждом из -множеств, на которые разбивается множество S, образуют линейное поддерево дерева Т.

Таким образом, когда ветви множества R являются коротко-замкнутыми, из графа G получается новый граф который в общем случае является разделимым, и каждая его неразделимая компонента содержит одно или более -множеств, на которые разбито множество

Пусть некоторая неразделимая компонента графа содержит только одно -множество, а его ветви образуют линейное поддерево с ветвями х и у в качестве концевых.

Рассмотрим задание F, определяемое путями, которые включают ветви в поддерево . Некоторые из этих путей могут содержать ветви только поддерева Остальные должны содержать как ветви из так и некоторые ветви, не принадлежащие но каждый из последних путей должен включать все ветви потому что все рассматриваемые элементы матрицы W равны. Поэтому подграф состоящий из ветвей поддерева и хорд, которым соответствуют пути, содержащие только ветви поддерева можно «перевернуть», чтобы получить граф, -изоморфный графу Если в одном графе концевой ветвью является то в другом — у.

Например, для графа G, представленного на рис. 12.9, а, соответствующий граф содержит три неразделимые компоненты, как показано на рис. 12.9, б. Заметим, что является концевой ветвью остова этого графа. Граф показанный на рис. 12.9, в, является -изоморфным к графу является концевой ветвью соответствующего дерева Таким образом, другая реализация (рис. 12.9, г) матрицы путей дерева F для графа G существует с в качестве концевой ветви. Используя алгоритм, который будет приведен ниже, можно определить концевую ветвь некоторого дерева, реализующего данную матрицу F. Используя этот алгоритм,

Рис. 12.9. Пример для концевой и дентификадии из полученного графа. а — граф G; б — граф в — граф G; г — граф

можно выделить любую из ветвей как концевую вгтвь дерева, реализующего -матрицу. Для каждой из этих возможностей существуют три реализации для матрицы F, имеющие выбранную ветвь в качестве концевой. Результат, который получается из приведенных выше рассуждений, можно сформулировать следующим образом. Когда ветви дерева Т можно разделить на два множества R и S, имеющих свойство, определяемое выражением (12.38), то для нахождения концевой ветви Т, которая по определению существует в множестве S, можно рассмотреть граф, полученный замыканием накоротко ветвей в множестве R, и найти концевую ветвь дерева, построенного из ветвей множества . Определенную таким образом концевую ветвь можно считать концевой ветвью дерева искомого графа.

Ниже приведен алгоритм нахождения концевой ветви дерева Т, реализующего данную матрицу

Шаг 1. Получить матрицу

Шаг 2. Рассмотреть произвольную строку i матрицы

Пусть (возможно, равный нулю) — минимальный элемент в этой строке. Если существует только один элемент в строке, например элемент имеющий это минимальное значение, то концевая ветвь. В противном случае пусть столбцы, в которых элементы в строке i равны образуют множество Очевидно, что множество S содержит концевую ветвь дерева Т. Пусть подмножество ветвей дерева Т, которые не входят в множество S, обозначается как множество

Шаг 3. Рассмотреть произвольную строку

Если , где исключаем элемент s; из множества S. Применяя это правило ко всем подходящим парам элементов в строке исключим все возможные элементы из множества и обозначим оставшееся множество через а дополнительное множество — через

Шаг 4. Повторить шаг 3 для других строк матрицы W, выбирая каждый раз такую строку , что — элемент множества R, например применимого на данной стадии. Эта процедура повторяется до тех пор, пока либо

а) множество содержит только один элемент, который в таком случае соответствует концевой ветви, либо

б) множество более не сократимо, т. е. —wris. Для всех и каждой пары элементов из множества

Шаг 5. Если множество содержит более одного элемента (случай 6 шага 4), выбрать любой элемент из множества чтобы заменить им элемент в шаге 3 и далее выполнить 3, 4 и 5, шаги 3—5, т. е. удалить произвольный элемент из множества добавив его к множеству и продолжить процесс дальнейшего сокращения множества Повторное применение этих шагов неизбежно ведет к множеству содержащему только один элемент, который можно считать концевой ветвью дерева Т.

Приведем доказательство корректности этого алгоритма. Сначала отметим, что, согласно свойству 12.3, элементы множества в шаге 2 образуют поддерево дерева Т. Поэтому дополнительное множество обязательно содержит по меньшей мере одну концевую ветвь. Заметим далее, что если элемент множества S, то из свойства 12.1 следует, что все элементы выделенного -множества, которое не содержит i и для которого является ведущим ребром, присутствуют в множестве 5. В шаге 3 получаем сокращенное множество (удаляя такие элементы, подобные что ). Необходимо показать, что множество содержит по крайней мере одну концевую ветвь дерева Т. Этот факт очевиден 1) когда и s находятся в одном и том же -множестве, а ветви содержатся в линейном поддереве Т. С другой стороны, если принадлежат одному -множеству, а ветви образуют звезду, когда все другие ветви Т короткозамкнуты,

это -множество содержит по крайней мере две концевые ветви. Отсюда в этом случае, даже если является концевой ветвью, сокращенное множество (полученное удалением такого ) содержит концевую ветвь Т. Как оказывается, когда удаляется ребро (свойство 12.1), то также следует удалить каждую ветвь, присутствовавшую в дереве, содержащем , и в качестве концевых. Таким образом, снова после завершения шага 3 множество ветвей, содержащееся в R, образует поддерево дерева Т.

Приведенная выше рекурсивная процедура повторяется в шаге 4, при этом выбирают другую соответствующую строку матрицы W. На каждой стадии сокращенное множество по определению содержит концевую ветвь, и ветви в продолжают образовывать поддерево дерева Т. Во многих случаях можно определить концевую ветвь, выполняя эту процедуру (применение шага 4) до тех пор, пока не получится содержащее только один элемент. Однако, если этого не получается и оказывается невозможным далее сократить число элементов в применением шага 4, это означает, что для всех и для всех Таким образом, на этом этапе элементы образуют поддерево дерева Т, а элементы множеств удовлетворяют формуле (12.38).

Если граф, полученный из графа G замыканием ветвей то, как уже упоминалось выше, граф является разделимым графом, имеющим, например, в качестве неразделимых компонент. Множество включает ветви остова графа

В шаге 5 элемент из множества выбираем произвольно, например ветвь из переносим этот элемент в множество и выполняем шаги 3 и 4, используя строку, соответствующую этому элементу. Как можно было видеть, оставшиеся элементы множества в конце этих шагов являются ветвями во всех неразделимых компонентах кроме Повторение этих шагов неизбежно приводит к множеству, содержащему ветви, присутствующие только в одной компоненте, и, следовательно, к концевой ветви искомого дерева Т.

Приведенные выше рассуждения доказывают корректность алгоритма определения концевой ветви дерева, реализующего данную матрицу

12.4.3. Нагруженные пути

Пусть b — концевая ветвь, определенная, как и ранее. Пусть матрица, полученная удалением из F столбца, соответствующего ветви b. Если дерево Т, реализующее получено, то дерево Т для F можно построить добавлением оконечной ветви b к только если пути в Т, содержащие ветвь b, имеют общую концевую. Однако это выполняется не всегда. Например, рассмотрим матрицу

Легко определить, что ветвь 1 является концевой. Тогда матрица полученная удалением столбца 1 из матрицы F, имеет вид

Можно показать, что матрица является реализуемой деревом представленным на рис. 12.10, а. Но это дерево нельзя увеличить, чтобы получить дерево, реализующее матрицу F, поскольку не будут удовлетворять условию пути, соответствующие хордам 6 и 7.

Рис. 12.10. а — дерево б — дерево в — дерево Т.

Однако это не означает, что матрица F нереализуема, поскольку одна из других реализаций может привести к реализации матрицы F. Фактически дерево показанное на рис. 12.10, б, также реализует и может быть расширено до дерева Т (рис. 12.10, в), реализующего матрицу F. Чтобы преодолеть выше упомянутую трудность, введем дополнительные пути в т. е. нагрузим матрицу такими дополнительными строками, что дерево, реализующее

нагруженную матрицу, по определению окажется дополнением концевой ветви в искомую реализацию дерева Т.

Пусть пути, содержащие концевую ветвь, задаваемую матрицей F, обозначаются через . Считается, что все эти пути различны и что каждый содержит более одной ветви. В целях дальнейшего обсуждения определим путь как тривиальный, если существует другой путь, идентичный этому, «ли когда он содержит только одну ветвь. Таким образом, при данных допущениях среди нет тривиального пути. Добавлением концевой ветви к каждому из этих путей получаем также пути в Т. Пусть этими путями будут . Заметим, что все эти пути имеют общую концевую вершину в Т.

Далее, любое дерево, реализующее матрицу также содержит эти пути. Теперь опишем процедуру такого нагружения что в каждом дереве, реализующем пути имеют общую концевую вершину. Из такого дерева легко построить искомое дерево Т добавлением ветви b к общей концевой вершине этих путей.

Рассмотрим три произвольных пути из множества Если то не существует реализации, в которой пути имели бы общую концевую вершину. Это следует из того факта, что все могут быть путями в дереве только двумя различными способами, показанными на рис. 12.11. Таким образом, матрица F является нереализуемой, если сумма по любых трех путей в является пустым множеством.

Рис. 12.11.

Чтобы проверить наличие такой ситуации, необходимо отдельно просмотреть множеств путей. Однако поскольку нашей целью является реализация F, то проверим только из этих множеств на согласованность и затем дополним матрицу дополнительными строками, чтобы убедиться, что нагруженная матрица F, оказывается нереализуемой, если F нереализуема. Сначала убедимся, что рръфрь, г. Если для некоторого k, то матрица F является, конечно, нереализуемой. После этой проверки матрица дополняется строками, соответствующими следующим путям:

Дополнительные пути, определенные в п. 1, накладывают условие, что каждый из путей имеет общую с концевую вершину в дереве, реализующем нагруженную матрицу так как являются путем, только если имеют общую концевую вершицу. Аналогично условие существования второго множества путей заставляет каждый из путей иметь также общую концевую вершину с Поскольку в не может существовать цикла и предыдущая проверка, гарантируя, что , обеспечивает существование в путей, подобных показанным на рис. 12.11, то общая концевая вершина является также концевой вершиной каждого пути . Таким образом, если нагруженная матрица реализуема, то в любой реализации этой матрицы пути имеют общую концевую вершину. В таком случае можно дополнить до дерева, реализующего матрицу F. С другой стороны, если нагруженная матрица нереализуема, то это означает, что справедлив один из следующих случаев:

1) является нереализуемой или 2) не существует реализации матрицы в которой пути имеют общую концевую вершину.

В обоих случаях матрица F является также нереализуемой. Теперь можно сформулировать процедуру для определения дерева Т, реализующего данную матрицу

12.4.4. Построение дерева

Сначала многократно применим к матрице F операции подготовки до тех пор, пока не получим матрицу F, которая дальше будет несократимой. Когда получено дерево Т, реализующее F, реализацию Т в виде дерева можно построить на его основе. На следующем шаге определяем концевую ветвь . Далее выполняется предварительная проверка путей на согласованность. Столбец, соответствующий выделенной концевой ветви, удаляется из F, а результирующая матрица затем заполняется добавочными строками, как описано ранее. Теперь выполняются операции подготовки над строками этой нагруженной матрицы и результирующая матрица обозначается как . Выделим теперь концевую ветвь дерева которое могло бы реализовать и продолжим аналогично, чтобы найти Эта процедура повторяется до тех пор, пока не будет получена матрица содержащая только два столбца. В случае если бы F и, следовательно, F были нереализуемыми, этот факт был бы обнаружен на одном из этапов процесса сокращения.

Если матрица F является реализуемой, то, начиная с дерева , т. е. дерева, реализующего концевые ветви присоединяются

в обратном порядке относительно той последовательности, в которой они удалялись.

Применение процедуры подготовки гарантирует существование двух путей, содержащих концевую ветвь, и, следовательно, положение этой концевой ветви можно однозначно определить на каждом этапе. Таким образом, можно построить Т и, следовательно, Т. Добавляя к последнему дереву хорды, соответствующие строкам матрицы F, получим реализацию графа

Можно отметить, что не обязательно сокращать данную матрицу F до матрицы F применением процедуры подготовки. Процесс сокращения можно применить непосредственно к матрице F, так как пути рассматриваемые на каждом этапе, различны и каждый из них содержит более одной ветви. Если в процессе построения дерева Т из ни на каком этапе не образуются два различных пути, содержащих концевую ветвь, то концевую ветвь можно присоединить к любому концу подходящего пути. Проиллюстрируем двумя примерами материал данного раздела. Пусть необходимо реализовать матрицу

Можно видеть, что данную матрицу нельзя сократить применением процедуры подготовки. Тогда получим

Рассматривая первую строку, заключаем, что ветвь 2 является концевой ветвью дерева Т. Так как существует только два пути, включающих эту ветвь, нет необходимости проверять согласованность путей, как описано в разд. 12.4.3. Удаляя столбец 2 и дополняя матрицу строкой, соответствующей получим

После удаления строк, соответствующих тривиальным путям, имеем

для которой матрица

Анализируя первую строку, заключаем, что ветвь 3 является концевой для Дерево реализующее матрицу которая получается удалением из матрицы столбца, соответствующего ветви 3, имеет только две ветви и представлено на рис. 12.12, а.

Рис. 12.12. а — дерево б - дерево в — дерево Т.

К этому дереву добавляем такую ветвь 3, что являются путями, и получаем как показано на рис. 12.12, б. Далее ветвь

2 добавляется к дереву так что являются путями. Таким образом, получается дерево Т, показанное на рис. 12.12, в. В качестве второго примера рассмотрим следующую матрицу:

Соответствующая матрица W теперь определяется в виде

Строке 1 соответствует множество Так как это множество S далее не сократимо, то удаляем из него произвольный элемент, например 2. Теперь находим, что 3 и, следовательно, ветвь 3 является концевой. Таким образом, Далее имеем рргфрз. Теперь удаляем столбец 3 из матрицы F и дополняем ее строками удаления строк, соответствующих тривиальным путям, получим матрицу

Соответствующая матрица W имеет вид

Множество S, соответствующее первой строке матрицы W, состоит из элементов 2 и 4. Так как это множество далее не сократимо, то удаляем произвольный элемент, например 2. Теперь элемент 4 является концевой ветвью, так как в множестве 5 на этом шаге существует только один элемент. Тогда имеем . Сумма по равна и, следовательно, матрица F нереализуема.