Свойства связных графов

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

Утверждение 8.1. Для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины a и каждой другой вершины b существовала (a, b) - цепь.

Утверждение 8.2. Для любого графа G или он сам или его дополнение является связным.

Пусть G = <V,E> - несвязный граф, А - одна из его областей связности, B = V \ A. Тогда "aÎA, "bÎB в есть ребро (a,b). Поэтому любая вершина из B соединена с вершиной a цепью длины 1, а любая вершина из A соединена с вершиной a цепью длины не более 2. Из утверждения 8.1 теперь следует, что граф связен.

Теорема 1. Пусть G -связный граф, e - ребро в G. Тогда:

1) если ребро е принадлежит какому-либо циклу графа G, то граф G-e связен;

2) если ребро е не принадлежит ни какому циклу графа G, то граф G-e имеет ровно 2 компоненты.

1. Пусть ребро e = (u,v) принадлежит циклу C графа G (рис.8.1).

Заменив в каждой (x, y)-цепи, содержащей e, подцепь (u, e, v) (u,v)-цепью С - е, получим (x, y)-маршрут, не содержащий ребра e. Следовательно, в графе G любые две несовпадающие вершины x, y соединены маршрутом, не проходящем через ребро e. Поэтому граф G-e связен.

2. Пусть ребро e = (u,v) не входит ни в какой цикл графа G (рис. 8.2).

Тогда вершины u и v принадлежат разным компонентам G_u и G_v графа G - e. Для любой вершины x ¹ u в G существует (x, u)-маршрут. Если ребро e в этот маршрут не входит, xÎG_u. Иначе xÎG_v, поэтому граф G - e имеет 2 компоненты.

Теорема 2. Если n, m, k - количество вершин, ребер и компонент графа G, то выполняется неравенство: n - k £ m £ .

Не останавливаясь на подробном доказательстве неравенства, заметим, что при фиксированных n, m, k £ n нижняя оценка достигается на графе G₁ = O_k-1ÈP_n-k+1, а верхняя оценка - на графе G₂ = O_k-1ÈK_n-k+1.

Дата добавления: 2014-01-11