9

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Равенство m + k = n

Теорема 4. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности, причем m + k = n. Тогда в графе G нет циклов.

Доказательство. Предположим в графе G имеется цикл, содержащий некоторое ребро e. Удалим из G какое-нибудь ребро e. Получим граф G0 c m 1 ребром, n вершинами и k компонентами связности.

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Равенство m + k = n

Теорема 4. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности, причем m + k = n. Тогда в графе G нет циклов.

Доказательство. Предположим в графе G имеется цикл, содержащий некоторое ребро e. Удалим из G какое-нибудь ребро e. Получим граф G0 c m 1 ребром, n вершинами и k компонентами связности. По теореме 2 имеем

(m 1) + k n:

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Равенство m + k = n

Теорема 4. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности, причем m + k = n. Тогда в графе G нет циклов.

Доказательство. Предположим в графе G имеется цикл, содержащий некоторое ребро e. Удалим из G какое-нибудь ребро e. Получим граф G0 c m 1 ребром, n вершинами и k компонентами связности. По теореме 2 имеем

(m 1) + k n: Но тогда

n 1 = (m + k) 1 = (m 1) + k n;

что невозможно.

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Леса и деревья

Определение. Граф G = (V ; E; ) называется лесом, если он не содержит циклов.

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Леса и деревья

Определение. Граф G = (V ; E; ) называется лесом, если он не содержит циклов.

Теорема 5. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности. Тогда следующие условия эквивалентны:

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Леса и деревья

Определение. Граф G = (V ; E; ) называется лесом, если он не содержит циклов.

Теорема 5. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности. Тогда следующие условия эквивалентны:

I G лес;

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Леса и деревья

Определение. Граф G = (V ; E; ) называется лесом, если он не содержит циклов.

Теорема 5. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности. Тогда следующие условия эквивалентны:

IG лес;

Iкаждое ребро из G мост.

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Леса и деревья

Определение. Граф G = (V ; E; ) называется лесом, если он не содержит циклов.

Теорема 5. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности. Тогда следующие условия эквивалентны:

IG лес;

Iкаждое ребро из G мост.

Iкаждая цепь, соединяющая две вершины, единственна;

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Леса и деревья

Определение. Граф G = (V ; E; ) называется лесом, если он не содержит циклов.

Теорема 5. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности. Тогда следующие условия эквивалентны:

IG лес;

Iкаждое ребро из G мост.

Iкаждая цепь, соединяющая две вершины, единственна;

Im+k=n;

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Деревья

Определение. Связный лес называется деревом.