Степень (валентность) вершины. Путь в графе. Цепи и циклы
Урок №2
Повторение
Задача
Одноклассники Авдеев, Борисов, Варахтин, Гринько, Данилевский и Еремин устроили турнир по настольному теннису и решили играть каждый с каждым. Турнир ещё не закончен; на графе отмечено, кто с кем сыграл. Кто из участников сыграл больше всех партий? Кто меньше всех?
А
Б
В
Г
Д
Е
Степень вершины
Степень вершины в графе – это количество рёбер, которые из неё исходят.
Если ребро соединяет вершину с этой же вершиной (ребро образует петлю), то такое ребро считается дважды.
Иногда степень вершины называют валентностью.
А
Б
В
Г
Д
Е
2
2
0
3
2
3
Степень вершины
Какой может быть сумма степеней всех вершин графа, если в нём всего:
Степень вершины
Какой может быть сумма степеней всех вершин графа, если в нём всего:
Сумму степеней всех вершин графа называют суммарной степенью вершин
Сумма: 2
1
2
Сумма: 2
1
2
2
Сумма: 4
4
Сумма: 4
3
1
Сумма: 4
Одно
ребро
Два
ребра
Свойства степеней
Задача
Сколько рёбер в графе, суммарная степень вершин которого равна: а) 2; б) 4; в) 6 ?
Ответ:
а) 1
б) 2
в) 3
Задача
В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 6 дорог. Сколько всего дорог в государстве?
Решение:
Сложим количества дорог, выходящих из всех городов (найдем сумму степеней): 99 ∙ 2 + 6 = 204.
Поскольку каждая дорога связывает два города, то количество дорог будет вдвое меньше, а именно 102.
Ответ: 102 дороги.
Задача
Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?
Решение:
Пусть х – число городов.
Число дорог: (3х):2 или 100 дорог.
(3х):2 = 100
3х=200
х = 200:3 ≈ 66,666…
Число городов может быть только натуральным, значит 100 дорог в таком государстве быть не может.
Ответ: не может.
Теоремы
Теорема 1: сумма степеней всех вершин графа равна удвоенному числу ребер этого графа.
Следствие: сумма степеней вершин графа – чётное число.
Теорема 2: в графе число вершин с нечетной степенью чётно.
Задача
В графе 12 рёбер, а каждая вершина имеет степень 3. Сколько у него вершин? Нарисуйте такой граф.
Задача
В графе 12 рёбер, а каждая вершина имеет степень 3. Сколько у него вершин? Нарисуйте такой граф.
Решение:
12·2=24 – сумма степеней всех вершин
24:3=8 – вершин
Ответ: 8 вершин
Задача
В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ?
Ответ: Нет. Число вершин с нечетным индексом должно быть четным (9 человек – 3 друга).
Ориентированный граф
Граф называется ориентированным, если указано направление (начало и конец) каждого ребра.
Ориентированный граф
Назовем число ребер, входящих в вершину входящей степенью вершины. Аналогично, число исходящих ребер назовем исходящей степенью.
2
2
3
1
3
В ориентированном графе сумма исходящих степеней всех вершин равна сумме входящих степеней всех вершин и равна числу ребер
1
2
1
1
1
1
1
3
11 = 11
Путь в графе
Путем в графе будем называть последовательность ребер, по которой можно «пройти» из одной вершины в другую.
Если в графе любые две вершины соединены путем, то такой граф называется связным.
Цепь в графе
Путь в графе, у которого вершины не повторяются, называется цепью.
Цепью также называется граф, у которого вершины последовательно соединены ребрами.
Цикл в графе
Путь в графе, у которого первая и последняя вершины совпадают, а промежуточные вершины не повторяются, называется циклом.
Цикл
Цикл
АБСДА
Не цикл
А
Б
С
Д
Замечательные пути
Во многих практических задачах, если их выразить на языке графов, требуется выяснить, существуют ли в графе пути, обладающие некоторыми свойствами. Две важные задачи — построить эйлеров путь и построить гамильтонов путь.
Эйлеров путь проходит по одному разу через все рёбра графа.
Гамильтонов путь проходит по одному разу через все вершины графа.
Замечательные пути
Путь, который обходит все ребра связного графа по одному разу, называется эйлеровым путем.
Граф, в котором существует эйлеров путь, называется эйлеровым графом.
Замечательные пути
Гамильтонов путь
1-2-3-4-5
Эйлеров путь
4-1-2-3-4-5-2
1
2
3
4
5
Эйлеров граф
1
2
3
4
5
Гамильтонов путь
Эйлеров путь
Задание на дом