Найти в Дзене
Уроки информатики
23 подписчика

Графы. Практическая работа "Анализирование информации, представленной в виде схем. Поиск путей из одного города в другой"

28
1 мин
Задача На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Решение У каждой вершины поставим число входящих путей. В пункты Б, В и Д есть одна дорога из пункта А. В город Г есть три пути из городов А, В, Д. В населенный пункт Е ведут две дороги из Б и В. У вершины Ж ставим число 4 = 3 (вес вершины Г) +1 (вес вершины Д). В город К ведут три дороги из Е, В и Ж. Складываем соответственно числа 2+1+4=7. Ответ: 7 Практическая работа 1. Выберите задание. 2. Скачайте по ссылке изображение к задаче. 3. Откройте изображение в растровом графическом редакторе. Решите задачу, подписав у каждой вершины количество путей, ведущих в неё. 4. Запишите ответ Задание №1 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных пут
Оглавление
Коллаж создан автором канала
Коллаж создан автором канала

Задача

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

Граф к задаче
Граф к задаче

Решение

У каждой вершины поставим число входящих путей. В пункты Б, В и Д есть одна дорога из пункта А. В город Г есть три пути из городов А, В, Д. В населенный пункт Е ведут две дороги из Б и В. У вершины Ж ставим число 4 = 3 (вес вершины Г) +1 (вес вершины Д). В город К ведут три дороги из Е, В и Ж. Складываем соответственно числа 2+1+4=7.

Решение к задаче
Решение к задаче

Ответ: 7

Скриншот задания. Задача взята из открытого банка заданий ФИПИ
Скриншот задания. Задача взята из открытого банка заданий ФИПИ

Практическая работа

1. Выберите задание.
2. Скачайте по ссылке изображение к задаче.
3. Откройте изображение в растровом графическом редакторе. Решите задачу, подписав у каждой вершины количество путей, ведущих в неё.
4. Запишите ответ

Задание №1

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

Номер: 08AD6A стр. 54. Банк открытых заданий ФИПИ.
Номер: 08AD6A стр. 54. Банк открытых заданий ФИПИ.

Ссылка для скачивания https://disk.yandex.ru/i/jN0X6QkXI4bCbQ

Задание №2

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

Номер: c7D45c стр. 96. Банк открытых заданий ФИПИ.
Номер: c7D45c стр. 96. Банк открытых заданий ФИПИ.

Ссылка для скачивания https://disk.yandex.ru/i/LYHS2ZgW6FtCUA

Задание №3

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

Номер: ecF85e. стр. 96. Банк открытых заданий ФИПИ.
Номер: ecF85e. стр. 96. Банк открытых заданий ФИПИ.

Ссылка для скачивания https://disk.yandex.ru/i/KngfeZNa7QRaZA