9-
.pdf
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Число компонент связности
Теорема 2. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k n. Доказательство. Индукция по m.
Пусть m = 0. Тогда k = n, и m + k = k = n n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0. Докажем теорему для m.
Для этого удалим из G какое-нибудь ребро e. Получим граф G0 c m 1 ребром, n вершинами и k0 компонентами связности.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Число компонент связности
Теорема 2. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k n. Доказательство. Индукция по m.
Пусть m = 0. Тогда k = n, и m + k = k = n n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0. Докажем теорему для m.
Для этого удалим из G какое-нибудь ребро e. Получим граф G0 c m 1 ребром, n вершинами и k0 компонентами связности. При этом k0 k 1.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Число компонент связности
Теорема 2. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k n. Доказательство. Индукция по m.
Пусть m = 0. Тогда k = n, и m + k = k = n n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0. Докажем теорему для m.
Для этого удалим из G какое-нибудь ребро e. Получим граф G0 c m 1 ребром, n вершинами и k0 компонентами
связности. При этом k0 k 1. По предположению индукции имеем (m 1) + k0 n:
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Число компонент связности
Теорема 2. Пусть в графе G = (V ; E) имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k n. Доказательство. Индукция по m.
Пусть m = 0. Тогда k = n, и m + k = k = n 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:
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Случай графов без циклов
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Случай графов без циклов
Теорема 3. Пусть в графе G = (V ; E) без циклов имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k = n.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Случай графов без циклов
Теорема 3. Пусть в графе G = (V ; E) без циклов имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k = n.
Доказательство. Индукция по m.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Случай графов без циклов
Теорема 3. Пусть в графе G = (V ; E) без циклов имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k = n.
Доказательство. Индукция по m. ’Пусть m = 0. Тогда k = n,
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Случай графов без циклов
Теорема 3. Пусть в графе G = (V ; E) без циклов имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k = n.
Доказательство. Индукция по m.
’Пусть m = 0. Тогда k = n, и m + k = k = n:
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Случай графов без циклов
Теорема 3. Пусть в графе G = (V ; E) без циклов имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k = n.
Доказательство. Индукция по m.
’Пусть m = 0. Тогда k = n, и m + k = k = n: Предположим, что теорема верна, если количество ребер равно m 1, m > 0.