Фундаментальные циклы графа

Определение чисел устойчивости графа

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

Поиск числа внутренней устойчивости по методу Магу сводится к составлению систем логических (булевых) уравнений по матрице смежности графа с последующим ее решением. Результатом решения являются все максимальные внутренне устойчивые множества вершин графа, среди которых и выбирается число внутренней устойчивости. При составлении логических уравнений для каждой i-ой строки для всех клеток матрицы с единицами выписываются выражения вида: ivj, где j - номер столбца, на пересечении которого с i-ой строкой стоит единица, причем, i ¹ j. Затем все полученные выражения объединяются с помощью конъюнкций и выполняются всевозможные упрощения (раскрываются скобки и выполняются поглощения).

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

Пример

Рис.2

Граф задан матрицей смежности (рис.2).

Для него имеем: (2v1)(3v1)(4v2)(3v2)=(23v13v12v1)(43v23v24v2)=

=(23v1)(43v2)=134v234v23v12=134v23v12;

Максимальными внутренне устойчивыми будут множества:{2},{1,4},{3,4}.

Максимальная мощность полученных множеств - 2, следовательно, число внутренней устойчивости тоже равно двум.

Поиск числа внешней устойчивости по методу Магу состоит в составлении для каждого j-го столбца матрицы смежности выражений вида: jvivkvlv...vm, где i,k,l,m - номера строк матрицы смежности, на пересечении которых со столбцом j ставится единица. Подобные выражения записываются для каждого столбца матрицы, затем они объединяются с помощью конъюнкций. После преобразований и упрощений получаются конъюнкции, определяющие устойчивые множества. Для рассмотренного примера (рис.2) имеем:

1v(1v2v3)(2v3v4)(3v3)(4v4)=(1v2v3)(2v3v4).3.4=

(12v2v23v13v3v14v24v34).3.4=3.4(2v3v14)=134v34v234=34.

Т.о., внешне устойчивым является множество {3,4}, а число внешней устойчивости равно двум.

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

В рассмотренном примере ядро графа образуют вершины 3 и 4.

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

Остовной подграф графа - это подграф, содержащий все вершины графа.

Остовом называется остовной подграф, являющийся деревом.

Хордой остова D в связном графе G называется всякое ребро графа, не принадлежащее D.

Любой подграф, состоящий из хорды и остова, имеет точно один цикл.

Рис.3

На рис.3 показан граф и его остовные подграфы, являющиеся деревом. Остов не содержит циклов. Чтобы построить остов графа, нужно в графе ликвидировать все циклы (выбрасывая из графа соответствующие ребра). Ребра остова обеспечивают его минимальную связность, т.е., если из остова удалить любое ребро, он распадается на две связные компоненты графа. Если граф имеет n вершин, то его остов всегда имеет (п-1) ребро.

Отличительной особенностью остова является следующая: добавление к остову графа хотя бы одного ребра, не принадлежащего остову, образует цикл, который называется фундаментальным (базисным) циклом графа. Число фундаментальных циклов графа всегда постоянно, не зависит от выбранного остова и равно числу хорд, не входящих в остов. Это число называется цикломатическим числом графа. Цикломатическое число графа можно определить по формуле

V(G)=R-(N-1), где R - число ребер графа; N - число вершин графа.

Цикломатическое число V{G} определяет связность графа.

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

Матрица строится следующим образом. На графе выбирают остов и ребра, не входящие в него, нумеруют натуральными числами, начиная с 1. Затем нумеруют ребра остова. Матрица фундаментальных циклов содержит столько столбцов, сколько ребер имеется в графе, и столько строк, сколько ребер не входит в остов (т.е. равно числу фундаментальных циклов).

На пересечении i-ой строки и j-ro столбца ставится единица, если ребро j входит в фундаментальный цикл, образованный добавлением к остову ребра i, и ставится нуль - в противном случае. Каждая строка матрицы есть фундаментальный цикл, представленный в виде двоичного вектора. Любой не фундаментальный цикл графа может быть получен суммированием по модулю 2 некоторого числа фундаментальных циклов.

Матрица фундаментальных циклов для графа на Рис.3 а) имеет вид:

Сф (G) =	с m d a b e f g h
			1

хорды

Рис.4

Дата добавления: 2017-01-13