Рабочие листы
к вашим урокам
Скачать
1 слайд
ГРАФЫ.
ПОИСК ПУТЕЙ В ГРАФЕ.
Автор: Сергеенкова И.М.,
ГБОУ Школа № 1191, г. Москва
2 слайд
Граф и его элементы. Основные понятия.
Граф – это совокупность объектов со связями между ними.
Объекты рассматриваются как вершины, или узлы графа,
а связи – как дуги, или ребра.
Ребро графа называется дугой, если одна из его вершин считается начальной, другая – конечной.
Основные элементы графа состоят из вершин графа, ребер графа и дуг графа. Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешанный граф.
А
Б
В
Дуга графа
Дуга графа
ребро графа
Вершина
графа
Вершина
графа
Вершина
графа
3 слайд
Неориентированный граф – это граф, для каждого ребра которого несуществен порядок двух его конечных вершин.
1
2
5
4
3
6
4 слайд
Ориентированный граф – это граф, для каждого ребра которого существенен порядок двух его конечных вершин.
Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра называются кратными.
1
2
3
5
4
5 слайд
Смешанный граф – это граф, содержащий как ориентированные, так и неориентированных ребра. Любой из перечисленных видов графа может содержать одно или несколько ребер, у которых оба конца сходятся в одной вершине, такие ребра называются петлями.
Путем в графе называют конечную последовательность вершин, в которой каждая вершина соединена ребром с последующей в последовательности вершин.
Длиной пути во взвешенном графе называют сумму длин звеньев этого пути. Количество k ребер в пути называется длиной пути. Путь называют циклом, если в нем первая и последняя вершины совпадают.
5
2
1
4
3
5
2
1
4
3
6 слайд
12
Задачи на поиск путей в Графе
Задача 1.
На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город M?
Решение
B
A
K
C
E
G
F
H
L
M
7 слайд
Решение задачи 1.
Начнем считать количество путей с конца маршрута – с города М.
NX — количество различных путей из города А в город X, N — общее число путей. В "М" можно приехать из C, F, L или H, поэтому
N = NM = NC + NF + N H + N L (1)
C
F
H
L
M
8 слайд
2. Аналогично:
NC = NB;
NF = NE;
NH = NF + NG;
NL = NK.
C
F
H
L
M
B
E
G
K
A
3. Добавим еще вершины:
NB = NA = 1;
NE = NB + NA + NG = 1 + 1 + 2 = 4;
NG = NA + NK = 1 + 1 = 2;
NK = NA = 1.
9 слайд
4. Преобразуем вершины:
NC = NB = 1;
NF = NE = 4;
NH = NF + NG = 4 + 2 = 6;
NL = NK = 1.
5. Подставим в формулу (1):
N = NК = 1 + 4 + 6 + 1 = 12
B
A
K
C
E
G
F
H
L
M
Ответ: 12
10 слайд
Задача 2.
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город И?
Решение
A
И
Б
Д
В
Ж
З
Е
Г
11 слайд
Решение задачи 2.
1. Начнем считать количество путей с конца маршрута – с города И. NX — количество различных путей из города А в город X, N — общее число путей. В "И" можно приехать из Д, Ж, или З, поэтому N = NИ = NД + NЖ + N З (1)
Д
Ж
З
И
12 слайд
2. Аналогично:
NД = NБ; NЖ = NБ + NВ + NЕ; NЗ = NЖ + NЕ.
Д
Ж
З
И
3. . Добавим еще вершины:
NБ = NА = 1;
NВ = NА + NГ = 1 + 1 = 2;
NЕ = NВ + NГ = 2 + 1 = 3;
NГ = NА = 1.
Б
В
Е
Г
А
13 слайд
4. Преобразуем первые вершины с учето значений вторых:
NД = NБ = 1;
NЖ = NБ + NВ + NЕ = 1 + 2 + 3 = 6;
NЗ = NЖ + NЕ = 6 + 3 = 9.
5. Подставим в формулу (1):
N = NК = 1 + 6 + 9 = 16. Ответ: 16
A
И
Б
Д
В
Ж
З
Е
Г
14 слайд
Задача 3.
На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город M?
Решение
B
C
D
E
F
L
G
H
K
M
A
15 слайд
Решение задачи 3.
1. Начнем считать количество путей с конца маршрута — с города M. Пусть NX — количество различных путей из города А в город X, N — общее число путей. В город M можно приехать из L, G, F, H или K, поэтому N = NM = NL + NG+NF+ NH + NK;(*)
2.Аналогично:
NL = NF+ NG = 5 + 5 = 10;
NG = NF = 5;
NH = NF = 5;
NK = NF + NE + NH = 5 + 1 + 5 = 11;
NF = NA + NB + NC + ND + NE = = 5.
3. Добавим еще вершины:
NB = NA = 1;
NC = NA = 1;
ND = NA = 1;
NE = NA = 1.
4. Подставим в формулу :
N = NM = 10 + 5 + 5 + 11 + 5 = 36.
Ответ: 36.
16 слайд
Решите самостоятельно:
1).
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Л?
Ответ: 30
B
E
Б
Д
Е
Г
Ж
К
Л
A
17 слайд
2).
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Ж?
Ответ: 11
А
Б
Е
Д
Ж
В
Г
18 слайд
3).
На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города A в город M?
Ответ: 12
А
М
H
B
C
D
E
K
L
F
G
19 слайд
Задание на дом:
На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города
А в город M?
B
C
D
E
F
G
H
K
L
M
А
20 слайд
Источники информации:
http://www.compress.ru/Archive/CP/2007/1/18/10.gif
http://kpolyakov.narod.ru/school/ege.htm
http://inf.reshuege.ru/test?theme=203
http://inf.reshuege.ru/get_file?id=3029
Рабочие листы
к вашим урокам
Скачать
6 662 871 материал в базе
«Алгебра», Бунимович Е.А., Кузнецова Л.В., Минаева С.С. и др.
1.4. Задачи на проценты
Больше материалов по этой теме
«Русский язык и литература. Русский язык. Базовый и углублённый уровни», Бунеев Р.Н., Бунеева Е.В., Комиссарова Л.Ю., Курцева З.И., Чиндилова О.В.
Занятие 3 (Б). Русский язык в современном мире
Больше материалов по этой теме
Настоящий материал опубликован пользователем Матюшин Никита Владимирович. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
500/1000 ч.
Курс повышения квалификации
36 ч. — 144 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Курс профессиональной переподготовки
300/600 ч.
Мини-курс
3 ч.
Мини-курс
4 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.