Степень (валентность) вершины. Число рёбер и суммарная степень вершин. Путь в графе. Цепи и циклы

1.

Степень (валентность)
вершины.
Число рёбер и суммарная
степень вершин.
Путь в графе. Цепи и
циклы

2. Повторение

Что называется графом?
Что называется вершиной графа?
Что называется ребром графа?

3.

Степень (валентность)
вершины графа
Степень вершины в графе — это
количество ребер, которые из нее исходят.
Если ребро соединяет вершину с этой же
вершиной (ребро образует петлю), то такое
ребро считается дважды.
Иногда степень вершины
называют валентностью.

4.

На рисунке вершины A и B имеют
степень 2, вершина D имеет степень 0,
вершина C имеет степень 3. Степень
вершины E тоже равна 3, поскольку из
нее идет одно ребро к вершине C, а еще
одно ребро образует петлю: оба конца
этого ребра входят в вершину E.

5. Свойство степеней вершин

У каждого ребра в графе два конца.
Поэтому в любом графе сумма
степеней вершин в два раза
больше числа рёбер.

6.

Еще раз убедитесь в этом, подсчитав
число ребер и сумму степеней вершин
на примере графа:
У этого графа 7 ребер, а суммарная
степень вершин составляет
2 + 1 + 3 + 4 + 2 + 2 = 14.

7. Количество рёбер графа равно сумме степеней всех его вершин, делённой на 2.

A 1
Пример
C
2
D
3
3
B
E
2
1
F
(1+3+2+2+3+1):2=6

8.

Подсчет числа ребер графа
Задача 1. В государстве 100 городов, из каждого
выходит 2 дороги, кроме столицы, откуда выходит
6 дорог. Сколько всего дорог в государстве?
Решение. Сложим количества дорог, выходящих из
всех городов (найдем сумму степеней):
99 ∙ 2 + 6 = 204.
Поскольку каждая дорога связывает два города, то
количество дорог будет вдвое меньше, а именно
102.
Ответ: 102 дороги.

9.

2. Может ли в государстве, в котором из
каждого города выходит ровно 3 дороги,
быть ровно 100 дорог?
Решение.
Пусть х – число городов.
Число дорог:
(3х)/2 или 100 дорог.
(3х)/2 = 100
3х=200
х = 200/3
Число городов может быть только натуральным,
значит 100 дорог в таком государстве быть не
может.
Ответ: не может.

10.

3. В графе 12 рёбер, а каждая вершина
имеет индекс 3. Сколько у него вершин?
Нарисуйте такой граф.
12·2=24 – сумма степеней всех вершин
24:3=8 – вершин
Ответ: 8 вершин.

11.

Ориентированный граф
Граф называется ориентированным,
если указано направление (начало и
конец) каждого ребра.

12.

Путь в графе
Путем в графе будем называть
последовательность ребер, по которой
можно «пройти» из одной вершины в
другую. Если в графе любые две
вершины соединены путем, то такой
граф называется связным.

13.

Цепи и циклы
Путь в графе, у которого вершины не
повторяются, называется цепью. Цепью
также называется граф, у которого
вершины последовательно соединены
ребрами.

14. Ориентированный граф

Цепи и циклы
Иногда путь «идет по кругу». Говорят,
что такой путь образует цикл. Путь, у
которого первая и последняя вершины
совпадают, а промежуточные вершины
не повторяются, называется циклом.

15. Степень вершины ориентированного графа

Цепи и циклы
Пример.
В графе, изображенном на рисунке а),
есть цикл DВFD. В графе на рисунке б)
циклов нет.

16. Свойство степеней вершин ориентированного графа

Цепи и циклы
Иногда весь граф состоит из одного
цикла. Такие графы мы также будем
называть циклами.