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