afcc5723209b4899b5e37944756c952e

1.

2. Информационные модели на графах

16.04.2026
Ссылка на урок на ютубе: https://youtu.be/ryyx7rhJXX4
Информационные модели
на графах

3. Задача 1: Сколько двухзначных чисел можно записать с помощью цифр 1, 2, 3

а) При условии: в числе не должно быть одинаковых цифр.
1
2
2
3
1
3
3
1
2
Ответ: можно записать 6 чисел – 12, 13, 21, 23, 31, 32

4. Задача 1: Сколько двухзначных чисел можно записать с помощью цифр 1, 2, 3.

б) При условии: в числе могут быть одинаковые цифры.
1
1
2
2
3
1
2
3
3
1
Ответ: можно записать 9 чисел – 11, 12, 13,
21, 22, 23,
31, 32, 33
2
3

5. Многообразие схем. Информационные модели в виде графа. Что такое граф?

ГРАФ это множество точек или вершин
и множество линий или ребер,
соединяющих между собой все
или часть этих точек.

6.

Граф состоит из вершин, связанных линиями.
Направленная линия (со стрелкой) называется
дугой.
Линия ненаправленная (без стрелки) называется
ребром.
Линия, выходящая из некоторой вершины и
входящая в неё же, называется петлей.
дуга
А
В
ребро
петля
С

7. Неориентированный граф

Неориентированный граф - граф,
вершины которого соединены ребрами,
можно двигаться в любом направлении
С помощью таких графов могут быть представлены
схемы двухсторонних (симметричных) отношений.
Юра
Аня
Маша
Коля
Витя

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

Ориентированный граф - граф, вершины
которого соединены дугами, движение по
направлению стрелок
С помощью таких графов могут быть представлены
схемы односторонних отношений.
Юра
Аня
Маша
Коля
Витя
Граф, отражающий отношение «пишет письма».
?

9. Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).

Взвешенный граф
Взвешенный граф - граф, у которого
вершины
или
рёбра
(дуги)
несут
дополнительную информацию (вес).
182
127
158
Москва, 1147
Владимир, 1108
Переславль Залесский, 1152
?

10. Изобразите схему ( взвешенный граф) к соответствующей таблице

А
5
D
4
В
6
3
С
Изобразите в виде взвешенного графа данные из таблицы

11.

Самый короткий путь: ABCE. Длина
маршрута 6 км.

12.

В
АВСЕ = 3+1+3 = 7 КМ
АBDE= 3+2+3 = 8 КМ
ABE= 3+6 = 9 КМ
Ответ: Самый короткий путь АВСЕ = 7 км.
1
3
А
С
2
6
3
3
Е
D

13.

14. Домашнее задание

Задача 2. Решение оформлять
рисуя, ГРАФ
Задача 3. Решение оформлять,
рисуя ГРАФ
С разных сторон на холм (обозначим
его буквой О) поднимаются три
тропинки (А,Б,В) и сходятся в
вершине на холме.
а)
Перечислите
множество
маршрутов, по которым можно
подняться на холм и спуститься
с него.
б) Решите ту же задачу, если
вниз надо идти по разным
тропинкам
Сколько трёхзначных чисел
можно записать с помощью
цифр 1, 3, 5, 7 при условии,
что в записи числа не должно
быть одинаковых цифр?
Перечислить все
полученные комбинации.