Теорема 8.2 Если G1; G2; : : : ; G· – компоненты связности графа G, то

¸(G) = m(G) ¡ n(G) + ·(G) = m(Gi) ¡ n(Gi) + · =

=1 i=1

Теорема 8.3 Граф G с n(G) ¸ 2 содержит по крайней мере две вершины, не являющиеся точками сочленения (шарнирами).

Д о к а з а т е л ь с т в о . Считаем, что граф связен и m(G) ¸ 1: Выберем в G простую цепь

Q = x0 u1 x1 : : : xl¡1 ul xl

наибольшей длины l (очевидно, l ¸ 1). Концевые вершины x0 и xl этой цепи и являются искомыми: действительно, если бы граф Gnxl (т.е.G0 = (X n fxlg; U0; P )) обладал более чем одной компонентой, то вершина xl в G была бы смежна с некоторой вершиной y, не принадлежащей той компоненте графа Gnxl, которая содержит x0.

Но тогда цепь

x0 u1 x1 : : : xl¡1 ul xl (xl; y) y

в графе G была бы простой и имела длину l + 1. Это противоречит предположению о том, что Q – цепь наибольшей длины. £

8.2 Деревья

Связный граф без циклов называется деревом.

Граф, все компонеты связности которого – деревья, называется лесом.

Висячие вершины дерева называются листьями.

Будем обозначать дерево через T = (X; U): Неориентированное дерево есть обыкновенный граф, поэтому в дереве T 8x 2 X[v(x) = s(x)] (в дереве нет петель).

8.2.1 Свойства дерева

1.·(T ) = 1 & ¸(T ) = 0 (определение дерева).

2.¸(T ) = 0 & n ¡ m = 1 (из определения).

3.Каждое ребро в T – перешеек (т.е. при удалении любого ребра · увеличивается на единицу).

4.Для любых двух вершин x; y дерева T существует одна и только одна соединяющая их цепь из x в y, и эта цепь необходимо простая.

5.Соединение любых двух вершин x; y дерева T новым ребром приводит к появлению цикла.

6.Вершина x дерева T является точкой сочленения (шарниром) тогда и только тогда, когда ее степень s(x) > 1:

7.Если n(T ) ¸ 2, то в T есть по крайней мере две висячие вершины.

До к а з а т е л ь с т в о .

Свойство 2 непосредственно следует из определения дерева. Свойство 3 выражает тот факт, что в дереве нет циклов, т.е. следует из определения.

Свойство 4. (Доказательство от противного.) Предположим, что существуют две различные цепи

x0 u1 x1 u2 x2 : : : xl¡1 ul xl

и

x0 v1 y1 v2 y2 : : : yk¡1 vk xl;

cоединяющие вершину x = x0 с вершиной y = xl, причем l ¸ k. При этом первая из этих цепей имеет ненулевую длину. Тогда ребро ui, где

i = minfjj uj =6 vj g

(если l > k и uj = vj при j = 1; 2; : : : ; k, то положим i = k + 1), является цикловым, так как после его удаления из G вершины xi¡1

и xi останутся соединенными маршрутом

xi¡1 vi yi : : : yk¡1 vk xl ul xl¡1 : : : xi+1 ui+1 xi: