Поиск цикломатического числа графа

Для нахождения цикломатического числа нужно прежде всего определить число компонент связности графа (см. 3.3.1.6) Это необходимо для вычисления цикломатического числа по формуле:

l(G)=m-n+k(G)

Затем следует составить матрицу циклов и выбрать наиболее оптимальное сочетание удаляемых ребер для устранения всех циклов в графе.

Пример: на рис. 3.17 дан граф. Составить матрицу циклов и найти цикломатическое число.

 

Ниже представлена матирица циклов.

c	r1	r2	r3	r4	r5	r6	r7	r8
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10

Интересно отметить, что операция (с_iÅс_j) формирует вектор-строку другого цикла.

с₁=10001100 с₁=10001100 с₆= 01110100

Å Å Å

с₂=11001010 с₄=11111000 с₈= 01100001

с₇=01000110 с₆ =01110100 с₁₀=00010101 и т.д.

 

В данном графе четыре базовых цикла: {r₁, r₅, r₆}, {r₄, r₆, r₈}, {r₂, r₃, r₈}, {r₃, r₄, r₇}. Если удалить четыре ребра в каждом базовом цикле, то будут устранены в графе все циклы. Например, {r₁, r₃, r₄, r₆}.

Если k(G)=1, то l(G)=m-n+k(G)=4.

Поиск хроматического числа графа

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

Если клика содержит n³3, то хроматическое число должно быть равным g(G)=n. В противном случае можно оценивать g(G) числу ребер в цикле.

Если число ребер в цикле есть четное число, то g(G)=2, если нечетное - g(G)=3.

 

Пример: На рис. 3.17а) дан граф. Определить его хроматическое число.

Проверим число красок по трем основаниям:

1) граф содержит циклы четной и нечетной длины, т. е. число красок должно быть g(G)³3;

2) наибольшая степень вершин x2 и x5 равна 4, т. е. Число красок должно быть g(G)<5;

3) плотность графа r(G)=4 (см. таблицу ниже), т. е. полный подграф содержит четыре вершины. Следовательно, число красок должно быть g(G)4.

r

x

x2

x3

x4

x5

q

x1

x2

x3

x4

x5

x1

x1

x2

x2

x3

x3

x4

x4

x5

x5

Бинарные операции

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

При исполнении операций над двумя графами G₁=<X₁, r₁> и G₂=<X₂, r₂> следует обратить внимание на наличие общих элементов для X₁ и X₂ и/или r₁ и r₂. Это позволяет выделить три конструктивных объекта:

a) вершины и рёбра (дуги) не имеют общих элементов, т.е. (X₁ÇX₂)=Æ и (r₁Çr₂)=Æ;

b) вершины имеют общие элементы, а рёбра (дуги) - нет, т.е. (X₁ÇX₂)¹Æ и (r₁Çr₂)=Æ;

c) вершины и рёбра (дуги) имеют общие элементы, т.е. (X₁ÇX₂)¹Æ и (r₁Çr₂)¹Æ.

Объединение графов

Граф G=G₁ÈG₂), для которого X=(X₁ÈX₂) и r=(r₁Èr₂) есть объединение графов G₁=<X₁, r₁> и G₂=<X₂, r₂>.

Для вычисления матрицы смежности формируемого графа сле­дует использо­вать матрицы смежности исходных графов. Матрицы смежности всех графов должны иметь число строк и столбцов |X|=|(X₁ÈX₂)|. Значение смежности вычисляют по формуле:

 

r(i, j)=r⁽¹⁾(i, j) Ú r⁽²⁾(i, j).

На рис. 3.18 показан результат этой операции для трех конструктивных объектов.

 

Ниже приведены матрицы для вычисления объединения графов G₁ и G₂ по рис. 3.18с).

 

r1	x1	x2	x3	x4		r2	x1	x2	x3	x4
x1						x1
x2					È	x2					=
x3						x3
x4						x4
						r	x1	x2	x3	x4
					=	x1
						x2
						x3
						x4

Пересечение графов

Граф G=(G₁ÇG₂), для которого X=(X₁ÇX₂) и r=(r₁Çr₂) есть пересечение графов G₁=<X₁, r₁> и G₂=<X₂, r₂>. На рис. 3.19 дан результат исполнения этой операции.

Для вычисления матрицы смежности формируемого графа сле­дует использо­вать матрицы смежности исходных графов.

Матрицы смежности всех графов должны иметь число строк и столбцов |X|=|(X₁ÈX₂)|. Значение смежности вычисляют по формуле

: r_i,j=r⁽¹⁾(i, j) × r⁽²⁾(i, j).

 

Ниже приведены матрицы для вычисления пересечения графов G₁ и G₂ по рис. 3.19с).

r1	x1	x2	x3	x4		r2	x1	x2	x3	x4
x1						x1
x2					Ç	x2					=
x3						x3
x4						x4
						r	x1	x2	x3
						x1
						x2
						x3
						x4

Композиция графов

Граф G=(G₁·G₂)=<X, r>, для которого XÍ(X₁ÈX₂), а r_i,jÎr существует тогда и только тогда, когда есть хотя бы одна вершина x_k, принадлежащая графам G₁ и G₂, что обеспечивает маршрут через вершину x_k, с началом в x_i⁽¹⁾ÎX₁ и концом в x_j⁽²⁾ÎX₂.

На рис. 3.20 дан результат исполнения этой операции.

 

Значение смежности вычисляют по формуле:

r(i, j)= _k=1 Ú ⁿ(r⁽¹⁾(i, k) × r⁽²⁾(k, j).

Ниже приведены матрицы смежности для вычисления композиции графов G₁ и G₂ по рис. 3.17с).

 

r1

x1

x2

x3

x4

r2

x1

x2

x3

x4

r

x1

x2

x3

x4

x1

x1

x1

x2

·

x2

=

x2

x3

x3

x3

x4

x4

x4

Соединение графов

Граф G=(G₁+G₂)=<X, r> представляет собой объединение графов G₁ и G₂ и двудольного полного графа, построенного на носителях X₁\(X₁ÇX₂) и X₂\(X₁ÇX₂). Каждая вершина xÎX₁, не вошедшая в пересечение (X₁ÇX₂), соединяется со всеми вершинами X₂, не вошедшими в пересесчение (X₁ÇX₂), и наоборот.

X=X₁ÈX₂, r=r₁Èr₂È{(x⁽¹⁾, x⁽²⁾)| x⁽¹⁾Î(X₁\(X₁ÇX₂)), x⁽²⁾Î(X₂\(X₁ÇX₂)))}.

На рис. 3.21а) X₁ÇX₂=Æ. Следовательно, ребра двудольного графа соединяют каждую вершину графа G₁ с каждой вершиной графа G₂. На рис. 3.21b) X₁ÇX₂=x₃. Следовательно, ребра двудольного графа соединяют только вершины x₁ и x₂ графа G₁ с вершинами x₄, x₅, x₆ графа G₂. На рис. 3.21c) X₁ÇX₂={x₁, x₂, x₃}. Следовательно, X₁\(X₁ÇX₂)=Æ, а X₂\(X₁ÇX₂)=x₄. Следовательно, множество ребер двудольного графа (x⁽¹⁾, x⁽²⁾)=Æ.

⇐ Предыдущая891011121314151617Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: