Цепи и цикл. Путь в графе (5)

1.

вероятность
и статистика
7 класс

2.

Граф - это изображение объектов и связей между ними
с помощью точек и линий.

3.

Точки в графе называют
вершинами графа. Некоторые
(не обязательно все) вершины
соединены
линиями.
Эти
линии называют ребрами.

4.

?
?
?
Степень вершины в графе - это
количество исходящих из нее
рёбер. Определите степени всех
вершин графа, изображенного на
рисунке.

5.

Работаем устно:
Определите по рисунку, сколько рёбер имеет граф.
Правильный
ответ: 5.

6.

Работаем устно:
На рисунке изображён граф. Найди степень каждой
вершины.
C
(1)
D
(0)
(1)
K
(2)
(4)
A
B
L (0)
(1)
E
N
(1)

7.

Работаем письменно:
Постройте граф по условию задачи и ответьте на
вопрос.
Ребята, которые дружат, могут помочь друг другу с
подготовкой к контрольной работе. Известно, что
Роман дружит с Димой и Дашей, Даниил — с Димой и
Лерой, Арсений — с Евой и Василисой, Ксения — с
Василисой. Может ли Роман помочь Василисе
подготовиться к контрольной работе?

8.

Работаем письменно:
В графе 3 вершины, каждая степени 6. Сколько в этом
графе рёбер?
Чтобы найти количество рёбер, нужно сумму степеней
его вершин разделить пополам.
3∙6
=9
2

9.

Работаем письменно:
В некотором графе 5 вершин, степени которых равны:
6; 13; 8; 12; 9. Сколько в этом графе рёбер?
Чтобы найти количество рёбер, нужно сумму степеней
его вершин разделить пополам.
6 + 13 + 8 + 12 + 9
= 24
2

10.

Цепи и цикл.
Путь в графе
§ 20

11.

В путешествиях нам приходится
тщательно выстраивать свой маршрут.
Выбирать
оптимальный
путь
из
нескольких, которые предлагают нам
онлайн-карты.
Мы помним, что графы применяют
для
изучения
связей
между
различными
объектами.
Введём
понятие пути в графе.

12.

Предположим, что в некотором графе можно по рёбрам “пройти”
из
вершины
А
в
вершину
В,
то
есть
существует
последовательность рёбер, соединяющих вершины А и В. Такую
последовательность называют путём.
A
F
C
D
K
E
B
В графе на рисунке путь от
точки A до точки B можно
записать так:
AD — DB или
AC — CD — DB.

13.

Длина пути — это количество рёбер в этом пути.
A
F
C
D
K
E
B
в графе на рисунке длина пути
AD — DB равна 2, а длина
пути AC — CD — DB равна
3.

14.

Найди в графе кратчайший путь из вершины A в
вершину L. Чему равна длина этого пути?
K
A
D
C
L
B
E
N
AC — CD —
DL.
Правильный
ответ: 3.
F

15.

Найдите возможные пути из вершины А в
вершину В.
F
G
E
D
A
B
C
ACB
ADFEB
ADCADCB и т.д.
-простые пути или цепи, потому что в них
вершины и рёбра не повторяются.

16.

Путь в графе, у которого вершины не повторяются,
называется цепью.
Цепь в графе можно задавать
перечислением только вершин
или только рёбер.
A
F
C
D
K
E
B
Например,
A — C — D — B или AC —
CD — DB.

17.

На рисунке изображён граф. Составь цепь из вершины L
в вершину B.
L
K
B
N
M
D
C
E
Правильный
ответ: LKEB.

18.

Цикл в графе — это путь, у которого начало и конец
— в одной вершине, а рёбра и промежуточные
вершины не повторяются.
A
Обозначается цикл
A — C — D — B — A или
C — D — B — A — C.
F
C
D
K
E
B
Началом можно считать любую
вершину графа.

19.

Граф называется связным, если две любые вершины
соединены путём.
а) связный граф
б) несвязный граф

20.

Существует ли в графе, изображённом на рисунке, путь
из вершины D в вершину E?
A
D
N
C
B
L
F
K
E
M
Правильный
ответ: нет.

21.

Работаем письменно:
В таблице представлены рейсы
авиакомпании «Полёт № 1» страны
Цветной. По данным в таблице
построй граф, в котором вершины
— это города, и рёбра соединяют
города, только если между ними
есть
авиарейс.
Есть
ли
в
построенном графе цикл?
Город
отправления
Гранатовый
Гранатовый
Гранатовый
Жёлтый
Кварцевый
Город
прибытия
Малахитовый
Жёлтый
Кварцевый
Бирюзовый
Белый

22.

ДОМАШНЕЕ ЗАДАНИЕ
§ 20, СТР 87 № 131-135