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

Что такое система? Система – это сложный объект, состоящий из множества взаимосвязанных частей и существующий как единое целое.

Информационная модель любой системы должна отражать её состав и связи между частями.

Основные понятия. Теоретическое введение. Граф– это средство наглядного представления состава и структуры системы. Это совокупность точек, соединенных между собой линиями.

Основные понятия. Теоретическое введение. Точки называются вершинами графа. Они могут изображаться точками, кружочками, прямоугольниками и пр. Линии, соединяющие вершины, называются дугами (если задано направление от одной вершины к другой) или ребрами (если направленность двусторонняя).

Многообразие схем

Блок-схема

Неориентированный граф Связи между объектами взаимные. Вершины соединены рёбрами.

Ориентированный граф Связь между объектами односторонняя. Вершины соединены дугами (стрелками)

Ориентированный граф «Дерево»

Граф переливание крови по группам

Задача 1 Сколькими способами можно рассадить в ряд на три стула троих учеников?

Задача 4 Между населёнными пунктами A, B, C, D, E построены дороги. Протяженность которых приведена в таблице: Определите кратчайший путь между дорогами A и D. ABCDE A246 B21 C4151 D53 E613

Задача 5 Между планетами Солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Основные этапы разработки и исследования моделей на компьютере 1.Описательная информационная модель выделяет существенные, с точки зрения целей проводимого исследования, параметры объекта, а несущественными параметрами пренебрегают. 2.Формализованная модель. С помощью формул, уравнений или неравенств фиксируются формальные соотношения между начальными и конечными значениями свойств объектов, нужные ограничения, или применение приближенных математических методов. 3.Компьютерная модель. – Создание проекта модели на одном из языков программирования – Построение компьютерной модели с использованием ЭТ и других приложений: систем компьютерного черчения, СУБД, ГИС. 4. Компьютерный эксперимент. Ввести исходные данные и получить результат. 5. Анализ полученных результатов и корректировка исследуемой модели. В случае несоответствия полученных результатов измеряемым параметрам реальных объектов, можно сделать вывод, что на предыдущих этапах были допущены ошибки или неточности.

ТерминОпределениеПримеры Граф Схема метрополитена, структура молекул, карта дорог, компьютерная сеть... Вершины графа Станции метро, атомы в молекуле, города на карте ; дорог... Дуги Линии на родословном дереве Ребра Линии, соединяющие атомы в молекуле, линии дорог на карте дорог, линии дорог метрополитена Ориентированный граф Различные классификации (биологические, орга­ низационные и др.) Дерево Генеалогическое дерево, классификации, файловая система Сеть Всемирная паутина

Словарь урока Граф – это средство для наглядного представления состава и структуры системы. Вершины графа – это компоненты системы изображаемые кругами, овалами, прямоугольниками и пр. Дуга – это направленные линии (стрелки), связывающие компоненты между собой определенным образом. Ребра – это ненаправленная линия, связывающие компоненты между собой определенным образом. Дерево – это граф, предназначенный для отображения вложенности, подчиненности, наследования и т.п. между объектами. В таком графе нет связанных по замкнутой линии вершин. Каждая вершина связана только с верхней и не связана больше ни с чем.