Сколько существует различных путей из А в Ж?

2.72M

Category:

informatics

Графические модели___

1. Графические информационные модели

2.

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

3. Типы информационных моделей

вербальные
математические
графические
табличные

4. Графические информационные модели

5.

ПРИМЕРЫ ГРАФИЧЕСКИХ МОДЕЛЕЙ
x
1
y
z
A
&
1
~
1
B
Т0С
Время

В районе четыре населенных пункта: Репкино,
Дедкино, Мышкино и Кошкино. Между некоторыми
из них проложены дороги. Информация об этом
представлена в таблице:
Репкино
Репкино
Дедкино
Мышкино
Кошкино
1
1
1
1
0
Дедкино
1
Мышкино
1
1
Кошкино
1
0
0
0
Можно ли проехать из населенного пункта Мышкино в Кошкино?
Сколько маршрутов из Мышкино в Кошкино существует?

7.

Вершины
Репкино
Кошкино
неориентированный граф
Дедкино
Мышкино
Ребра
Граф – это набор вершин и соединяющих
их ребер или дуг.

8.

В районе четыре населенных пункта: Репкино,
Дедкино, Мышкино и Кошкино. Между некоторыми
из них проложены дороги. В таблице представлена
информация о протяженности дорог в километрах:
Репкино
Репкино
Дедкино
Мышкино
Кошкино
10
4
2
3
0
Дедкино
10
Мышкино
4
3
Кошкино
2
0
0
0
Определите кратчайшее расстояние между населенными
пунктами Мышкино и Кошкино, при условии, что
передвигаться можно только по проложенным дорогам.

9.

10
Репкино
2
Кошкино
взвешенный граф
Дедкино
4
Мышкино
3

10.

Представьте в виде графа информацию о мужском
составе некоторой семьи: Лев является отцом Андрея
и Петра, Андрей – отец Алексея, а Петр – отец
Михаила и Дмитрия.
Дуги
Лев
Андрей
Алексей
Петр
Михаил
Дмитрий
ориентированный граф
Деревом называют граф, в котором нет связанных по
замкнутой линии вершин.

11.

Можно ли назвать граф, отражающий соединение
населенных пунктов дорогами, деревом?
Репкино
Кошкино
Дедкино
Мышкино
Какое изменение нужно внести, чтобы этот граф
можно было назвать деревом?

12.

Цепь – путь по вершинам и рёбрам графа, в который
любое ребро графа входит не более одного раза.
цикл
Репкино
Кошкино
Дедкино
Мышкино
Сеть – граф с циклом.

13.

Грунтовая дорога проходит последовательно
через населенные пункты А, B, С и D. При
этом длина дороги между А и В равна 80 км,
между В и С – 50 км, и между С и D – 10 км.
Между А и С построили новое асфальтовое
шоссе длиной 40 км. Оцените минимально
возможное время движения велосипедиста из
пункта А в пункт В, если его скорость по
грунтовой дороге – 20 км/час, по шоссе – 40
км/час.
1) 1 час
2) 1,5 часа
3) 3,5 часа
4) 4 часа

14.

80
20
A
40
40
B
50
20
C
D
10
20
4
B
2,5
A
1
3
C
D
0,5

15.

A
A
B
C
D
E
2
10
8
16
B
2
9
1
C
10
9
3
4
D
8
1
3
11
E
16
4
11

16.

17.

A B
2
A
B 2
C 4 1
D
E 6
C D E
4
6
1
5 1
5
3
1 3
Определите кратчайший путь
между пунктами A и D.
A
2
B
4
С
2
6
E
4
1
С
5
D
8
1
С
3
6
3
7
D
1
E
4
3
дерево возможных
маршрутов
D
7
17
9

18.

ДЕМО-2024
8

19.

Домашнее задание
§ 1.3,
№ 9, 10, 11, 12, стр.26

20. Сколько существует различных путей из А в Ж?

20
Сколько существует различных путей из А в Ж?
1
1
Б
Д
1+1+1+1+3=7
1+1+1=3
А
Ж
Г
В
!
1
Е 1
Количество путей в вершину X равно
Nсуммарному
количеству
путей
в каждую
из
Ж= NД + N
Б + NГ + N
В+ N
Е
вершин, из которых есть ребро в X.

21.

На рисунке – схема дорог, связывающих города А,
Б, В, Г, Д, Е, К. По каждой дороге можно двигаться
только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города
А в город К?
8

22. Количество путей из А в К

22
Информация и информационные процессы, 10 класс
Количество путей из А в К
Д
Б
B
Е
А
Г
© К.Ю. Поляков, Е.А. Ерёмин, 2013
З
Ж
К
И
http://kpolyakov.spb.ru

23. Решение:

23
Информация и информационные процессы, 10 класс
Решение:
Б
1
B
3
А
11
Д
11
Е
З
К
7
33
4
Г
© К.Ю. Поляков, Е.А. Ерёмин, 2013
1
Ж
И
4
http://kpolyakov.spb.ru

24. Количество путей из А в К

24
Информация и информационные процессы, 10 класс
Количество путей из А в К
Д
Б
B
Е
А
Г
З
Ж
К
И
21
© К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru