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

г) для любых двух вершин v, w и любого ребра x существует простая (v – w)-цепь, содержащая ребро x;

д) для любых трех разных вершин графа G существует простая цепь, соединяющая две из них и проходящая через третью;

е) для любых трех разных вершин графа G существует простая цепь, соединяющая две из них и не проходящая через третью.

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

Граф блоков графа G – граф B(G), вершины которого соответствуют блокам графа G, и две вершины в B(G) смежны тогда и только тогда, когда соответствующие им блоки имеют общую точку сочленения.

Граф точек сочленения графа G – граф C(G), вершины которого соответствуют точкам сочленения графа G, и две вершины C(G) смежны тогда и только тогда, когда соответствующие им точки сочленения принадлежат одному блоку.

Теорема 19. Граф H является графом блоков некоторого графа G тогда и только тогда, когда

каждый блок графа H является полным графом.
Двудольные графы. Паросочетания
Граф G = (V, X) называется двудольным / биграфом и обозначается G = (V1, V2, X), если						V
можно разбить на два подмножества (доли) V1 и V2 так, чтобы каждое ребро графа G соединяло
вершины из разных множеств; он				называется полным, если v1 V1 v2	V2 v1 , v2 X ,	и
обозначается Km,n, где m V1 , n		V2		. Граф K1,n называется звездой.
Граф G = (V, X) называется n-дольным, если существует разбиение {V1, …, Vn} множества V
такое, что каждое ребро x X соединяет вершины из разных подмножеств Vi,					i 1, n , (долей). n-

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

вершинами остальных долей и обозначается K p								, p		, , p	, где pi Vi , i 1, n .
				1				2			n
						p			p	. В частности, Km,n Km Kn .
Легко показать, что K p , p		, , p	n		K		K
1	2			1						n
Если граф несвязный,	то он будет двудольным тогда и только тогда, когда каждая его

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

Теорема 20 (Кенига). Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину.

Доказательство. Достаточность ( ). По условию все простые циклы четны. Выберем

произвольную вершину v V . Определим множества W w V : v , w четно , V				v W ,
1	1	1	1	1	1
V2 = V \ V1. Имеем разбиение {V1, V2} множества V. Покажем, что граф G имеет вид G = (V1, V2, X).
Допустим противное. Рассмотрим разные случаи.
1. Пусть u, v V2 : u см v . По определению	множества	V2, ρ(v1, u) –	нечетно и	ρ(v1, v)	–

нечетно. Обозначим P1 и P2 кратчайшие простые (v1 – u) и (v1 – v)-цепи: а) если P1 и P2 не имеют

общих	вершин,	кроме v1, то простой цикл Z = v1 P1 u v P2 v1 и имеет нечетною	длину
X Z	X P1	X P2 1; наличие такого цикла противоречит условию; б) если P1 и P2	имеют

общие вершины, кроме v1, обозначим последнюю из таких вершин (от v1) через w. Тогда отрезки

4

простых цепей P1 и P2 от w к u и v и ребро x = {u, v} образуют простой цикл нечетной длины (в

обоих возможных случаях	w V2 (рис. 8.2.а) и	w V1	(рис. 8.2.б), что противоречит условию.
2. Предположение, что	u, v V1 : u см v	также	приводит к противоречию с условием о

четности простых циклов, которое доказывается по аналогии со случаем 1.

Таким образом, доказано, что в каждом из множеств V1 и V2 нет смежных вершин, т.е. граф является двудольным и имеет вид: G = (V1, V2, X).

Приведенное доказательство достаточности теоремы Кенига является конструктивным и дает метод построения долей, если граф G двудольный.

Пусть G = (V1, V2, X) – двудольный граф, S V1 . Взаимно-однозначное соответствие

f : S → V2 такое, что

v S f v см v

называется паросочетанием из S в V2. Его можно описать

множеством

X f

S v, f v , v S ,

удовлетворяющем

условиям:

1) X S

S

и

2) x, y X f S x y ,

т.е. иначе,

паросочетание из S в V2 – это

множество

попарно

несмежных ребер, инцидентных вершинам S, число которых равно

S .

Паросочетание из V1 в V2 в графе G = (V1, V2, X) называется полным / совершенным.

Введем множества

M v w V2

: w см v ,

M S M v , где

S V1 .

v S

Если S M S , то не существует паросочетания из S в M(S), а следовательно, и в V2.

Дефицит подмножества S V1 – число S S M S .

Дефицит графа G – число G max S .

S V

1

Отсюда следует, что σ(G) ≥ 0, т.к.

0 . Если σ(G) = 0,

то

S V1 : S M S . Если

σ(G) > 0, то

S V1 : S M S и не существует совершенного паросочетания из S в V2.

Теорема 20 (Холл).

Совершенное

паросочетание

из

V1

в

V2

в

двудольном

графе

G = (V1, V2, X) существует тогда и только тогда, когда S V1

: S M S

, т.е. когда σ(G) = 0.

Теорема 21. Число ребер в максимальном паросочетании П двудольного графа G = (V1, V2, X)

равно V1 G , т.е

max П V1 G .

П X

Теорема 22.

Пусть

G = (V1, V2, X)

–

непустой

двудольный

граф.

Тогда,

если

min d v max d w , то существует совершенное паросочетание V1 с V2.

v V1

w V2

Системы различных представителей

Пусть S – непустое конечное множество, а F Si S,i 1, n .

si S,i 1, n ,

Системой различных представителей (трансверсаль) семейства F множество

для которого si ≠ sj

при i ≠ j , i 1, n : si Si

представители множества Si.

Не для всякого семейства F существует с.р.п.. Задача об с.р.п. может быть сведена к задаче о

полном паросочетании в двудольном графе: G = (F, S, X):

X Si

, s : Si F, s Si .

F

Si ,i

Теорема 23.

Трансверсаль для семейства

множеств

1, n

существует

тогда и

k

только тогда, когда k

1, n

i1 , i2 , , ik

1, n

: Sil

k .

l 1

5