9-

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

Случай графов без циклов

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

Доказательство. Индукция по m.

’Пусть m = 0. Тогда k = n, и m + k = k = n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0. Докажем теорему для m.

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

Случай графов без циклов

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

Доказательство. Индукция по m.

’Пусть m = 0. Тогда k = n, и m + k = k = n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0. Докажем теорему для m.

Для этого удалим из G какое-нибудь ребро e.

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

Случай графов без циклов

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

Доказательство. Индукция по m.

’Пусть m = 0. Тогда k = n, и m + k = k = n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0. Докажем теорему для m.

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

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

Случай графов без циклов

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

Доказательство. Индукция по m.

’Пусть m = 0. Тогда k = n, и m + k = k = n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0. Докажем теорему для m.

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

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

Случай графов без циклов

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

Доказательство. Индукция по m.

’Пусть m = 0. Тогда k = n, и m + k = k = n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0. Докажем теорему для m.

Для этого удалим из G какое-нибудь ребро e. Получим граф без циклов G0 c m 1 ребром, n вершинами и k0 компонентами связности. При этом k0 k = 1. По предположению индукции имеем (m 1) + k0 = n:

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

Случай графов без циклов

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

Доказательство. Индукция по m.

’Пусть m = 0. Тогда k = n, и m + k = k = n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0. Докажем теорему для m.

Для этого удалим из G какое-нибудь ребро e. Получим граф без циклов G0 c m 1 ребром, n вершинами и k0 компонентами связности. При этом k0 k = 1. По предположению индукции имеем (m 1) + k0 = n: Тогда

m + k = m + (k0 1) = (m 1) + k0 = n:

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

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

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

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

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

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

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

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

Доказательство. Предположим в графе G имеется цикл, содержащий некоторое ребро e.

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

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

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

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