Урок 4. Графические модели
Решение задач с помощью графа
Интерактивные тесты
Ссылки на ресурсы ЕК ЦОР
В графических информационных моделях для наглядного отображения объектов используются условные графические изображения, дополняемые числами, символами и текстами: схемы, карты, чертежи, графики и диаграммы, графы.
Схема - это представление некоторого объекта в общих, главных чертах с помощью условных обозначений.
Чертеж - условное графическое изображение предмета с точным соотношением его размеров, получаемое методом проецирования.
График -графическое изображение, дающее наглядное представление о характере зависимости одной величины (например, пути) от другой (например, времени).
Диаграмма - графическое изображение, дающее наглядное представление о соотношении каких-либо величин или нескольких значений одной величины, об изменении их значений.
Граф состоит из вершин, связанных линиями - рёбрами.
У взвешенного графа вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин (рёбер).
Цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
Цикл - цепь, начальная и конечная вершины которой совпадают.
Сеть - граф с циклом.
Дерево - граф иерархической системы. Между любыми двумя вершинами дерева существует единственный путь
6. Грунтовая дорога проходит последовательно через населённые пункты А, В, С и D. При этом длина грунтовой дороги между А и В равна 40 км, между В и С — 25 км, и между С и D — 10 км. Между А и D дороги нет. Между А и С построили новое асфальтовое шоссе длиной 30 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге — 20 км/ч, по шоссе — 30 км/ч.
Решение:
По условию задачи строим взвешенный граф:
С учетом скорости движения велосипедиста по грунтовой дороге (20 км/ч) и по шоссе (30 км/ч) вычислим время (в часах), требуемое для преодоления расстояния между каждой парой населенных пунктов, соединенных дорогами.
По получившемуся взвешенному графу легко оценить минимально возможное время движения велосипедиста между любыми из имеющихся населенными пунктами.