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

Пусть G1 = (V1, X1); G2 = (V2, X2); 1. Объединение графов G1 и G2 – граф

V1 G1



p
1
G	2

,

X	1	q
		1
V , X :

;

V	2	p
V V
		1

2 ,

X		2
V	2		&

q

2 , X

V1

X

V		2
1

X2 .

.

V p p1 p2 , X q q1 q2 .

2.

Соединение графов G1 и G2 – граф G1

G2

V , X : V V1

V2

&

v

: v V & v

&

X X

1

X

2

, v

j

j

V

i

i

1

2

V p p1 p2 , X q q1 q2 p1q2 .

3.

Произведение

графов (прямое / декартово) G1 и G2 – граф

G1

G2

V , X :V V1 V2

&

& v,w V : v,w X Пр1 v Пр1 w & Пр2 v см Пр2 w Пр1 v см Пр1 w & Пр2 v Пр2 w .

V p p1 p2 , X q p1q2

p2 q1 .

4.

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

G2 V , X :V V1

V2 & v,w V : v,w X

Пр1 v см Пр1 w Пр1 v Пр1 w & Пр2 v см Пр2 w .

V p p1 p2 , X q p1q2

2

q1 p2 .

5.

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

V , X :

V V1 V2

&

X X1

X 2 .

Операции

, +,

, коммутативны,

т.е. к

примеру,

G1 G2 G2

G1 .

Если

графы

рассматривать с точностью до изоморфизма, то операция × также коммутативна:

G1

G2

~ G2

G1 .

Операция не коммутативна, т.е. G1 G2 ~ G2

G1 .

Точки сочленения, мосты и блоки

Точка сочленения графа G = (V, X) – такая его вершина, при удалении которой получается

граф G – v с числом компонент большим, чем у графа G.

Мост графа – его ребро x, удаление которого увеличивает число компонент.

Граф неразделимый, если он связный, непустой и без точек сочленения, иначе – разделимый.

Блок графа – его максимальный (в смысле ) неразделимый подграф.

Приведем некоторые признаки точки сочленения, моста и блока.

Теорема 15. Вершина v связного графа G = (V, X) является точкой сочленения тогда и только

тогда, когда выполняется одно из следующих условий:

v – точка сочленения

а) существует

разбиение {V1, V2} множества

V \ {v}

такое,

что

v1 V1 v2 V2

вершина v принадлежит любой простой (v1 – v2)-цепи;

б) существуют вершины u, w V , отличные от v,

такие,

что вершина v

а)

б)

принадлежит любой простой (u – w)-цепи.

Теорема 16. Ребро x связного графа G = (V, X) является мостом тогда и только тогда, когда

выполняется одно из следующих условий:

а) существует

разбиение

{V1, V2}

множества

V

такое,

что

x – мост

v1 V1 v2 V2

ребро x принадлежит любой простой (v1 – v2)-цепи;

в)

а)

б) существуют вершины v1 , v2 V такие,

что x принадлежит любой

простой (v1 – v2)-цепи;

б)

в) x не принадлежит ни одному простому циклу графа G.

Теорема 17. Пусть G = (V, X) – связный граф и

V 3 . Тогда G является блоком тогда и

только тогда, когда выполняется одно из следующих условий:

а) любые две вершины графа G принадлежат некоторому общему простому циклу;

3