Конспект урока по теме "Моделирование на графах"

Конспект урока по теме «Моделирование. Моделирование на графах».

Модель - это новый объект, который отражает существенные с точки зрения цели моделирования признаки изучаемого предмета, процесса или явления.

Моделирование - метод познания, заключающийся в создании и исследовании моделей.

Натурные модели – реальные предметы, в уменьшенном или увеличенном виде воспроизводящие внешний вид, структуру или поведение объекта моделирования. Пример: муляжи и макеты.

Информационные модели – описание объекта-оригинала на языках кодирования информации.

Знаковые – текст, формула.

Образные – рисунки и фотографии.

Смешанные – карты, схемы, таблицы и т.д. (где текст смешивается с графикой)

Моделирование на графах.

Граф состоит из вершин, связанных линиями. Если линия направленная (со стрелкой), то она называется дугой. Линия ненаправленная (без стрелки) называется ребром.

Виды графов:

1) ориентированный, если его вершины соединены дугами	2) неориентированный, если его вершины соединены рёбрами.
3) взвешенный, когда над рёбрами (дугами) есть дополнительная информация, например расстояние между двумя пунктами.	4) граф в виде дерева (между любыми двумя вершинами существует единственный путь)

Решение задач с помощью графов (условие задач переписывать НЕ НАДО!!!)

Задачи №1-2 (рассматриваем устно – не надо переписывать в тетрадь!!!)

Для решения задач №1-2 надо посмотреть в таблицу, какие пункты соединены между собой и на стоимость перевозок между ними – на графе должны быть соединены эти же пункты с данной стоимостью.

Ответ:3

Ответ: 2

Для решения задач №4,5,6 запишем в тетрадь алгоритм:

Чтобы найти кратчайшее расстояние между двумя пунктами, наиболее удаленными друг от друга надо:

1) найти кратчайшее расстояние между любыми двумя пунктами, заданными в задачи;

2) выбрать среди полученных расстояний – наибольшее.

4)      На схеме нарисованы дороги между пятью городами A, B, C, D, E и указаны протяжённости дорог. Определите, какие два города наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими городами.

1) 14               2) 15                  3) 16               4) 17

Запись в тетради:

№4.

АВCDE

1) По алгоритму находим все минимальные расстояния между любыми двумя точками:

AB=4

AC=4

AD=13

AE=8

BC=6

BD=10

BE=12

CD=16

CE=12

2) Из всех расстояний выбираем наибольшее. Это 16.

Ответ: 3 (вариант ответа)

5)      На схеме нарисованы дороги между четырьмя населенными пунктами A, B, C, D и указаны протяженности данных дорог. Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами.

1) 11;

2) 15;

3) 18;

4) 20.

6)      На схеме нарисованы дороги между четырьмя населенными пунктами A, B, C, D и указаны протяженности данных дорог. Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами.

1) 12;

2) 16;

3) 18;

4) 19.

Запись в тетради:

№5.

1) ABCD

AB=9    AC=8    AD=6   BC=11   BD=15   CD=7

2) максимальное -15

Ответ: 2

№6.

№6.

1) ABCD

AB=18    AC=10    AD=6   BC=9    BD=12     CD=8

2)  максимальное -18

Ответ: 3

Для решения заданий №7-9 необходимо построить граф в виде дерева:

№7

Почтальону необходимо последовательно посетить 6 населенных пунктов. На схеме они обозначены латинскими буквами, числа указывают расстояние между пунктами. Найдите длину наиболее короткого пути.

1) 14;

2) 15;

3) 16;

4) 18.

№8

Для построения графа-дерева смотрим в таблицу по строчно, т.е. сначала первую строку – видим что из А можно доехать в В и Е, затем вторую строку из В можно только в D. И т.д.