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

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

Например структура молекулы углеводорода.

Здесь компоненты системы (атомы) соединены между собой линиями. Причем способ соединения выбран определенный, так как при другом варианте соединения получится другое вещество.

Такой чертеж будет называться граф.

Граф — это средство для наглядного представления состава и структуры системы.

Вершины графа — это компоненты системы изображаемые кругами, овалами, прямоугольниками и пр.

Дуги — это направленные линии (стрелки), связывающие компоненты между собой определенным образом.

Ребра - это ненаправленная линия, связывающие компоненты между собой определенным образом.

Дерево — это граф, предназначенный для отображения вложенности, подчиненности, наследования и т.п. между объектами. В таком графе нет связанных по замкнутой линии вершин. Каждая вершина связана только с верхней и не связана больше ни с чем.

Сеть — это граф, в котором вершины связаны между собой по принципу «многие ко многим».

Блок-схема — это граф, отображающий последовательность выполнения действий. Его вершины отображают отдельные действия и изображаются определенными геометрическими фигурами, а связи изображаются дугами.

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

Повторение. Для данных таблиц укажите:

А. тип; Б. номер таблицы; В. Заголовок таблицы; Г. объекты или класс объектов;

Д. свойства объектов или их значение.

Урожайность сельхозкультур

«Звери»

Сельхозкультура

Год

1985

Картофель

96ц

1990

Овощи

1995

153ц

Сахарная свекла

99ц

154ц

211ц

117ц

140ц

213ц

176ц

Название

Проживание

Волк

Дикое

Питание

Корова

Хищник

Домашнее

Лев

Размер

Средний

Дикое

Травояд­ное

Кошка

Крупный

Хищник

Домашнее

Крупный

Хищник

Мелкий

«Температура»

«Планеты»

Планета

Месяц

Меркурий

Средняя температура

Расстояние до Солнца

Период обращения

Венера

Январь

39у.е.

2002 г.

Земля

Средние сутки

Февраль

2003 г.

20°С

72 у.е.

88 суток

Марс

Март

18°С

25 суток

1 76 суток

20041

100 у.е.

25°С

356 суток

10°С

20°С

23°С

117 суток

152 у.е.

24 часа

19°С

8°С

687 суток

25 часов

5°С

Определение понятия «граф» и его структуры

Для того, чтобы представить информацию о составе и структуре системы графически, необходимо в виде чертежа изобразить компоненты системы И соединить их между собой какими-либо линиями. Например:

Структура молекулы углеводорода

Здесь компоненты системы (атомы) соединены между собой линиями. Причем способ соединения выбран определенный, так как при другом варианте соединения получится другое вещество.

Такой чертеж будет называться граф.

Граф — это средство для наглядного представления состава и структуры системы.

Вершины графа — это компоненты системы изображаемые кругами, овалами, прямоугольниками и пр.

Дуги — это направленные линии (стрелки), связывающие компоненты между собой определенным образом.

Ребра - это ненаправленная линия, связывающие компоненты между собой определенным образом.

Дерево — это граф, предназначенный для отображения вложенности, подчиненности, наследования и т.п. между объектами. В таком графе нет связанных по замкнутой линии вершин. Каждая вершина связана только с верхней и не связана больше ни с чем.

Сеть — это граф, в котором вершины связаны между собой по принципу «многие ко многим».

Блок-схема — это граф, отображающий последовательность выполнения действий. Его вершины отображают отдельные действия и изображаются определенными геометрическими фигурами, а связи изображаются дугами.

Г еометрические фигуры, которые используются для обозначения вершин, следующие :

заполните таблицу.

Термин

Ключевые слова

Граф

Примеры

Средство представления

Вершины графа

компоненты системы

Дуги

Ребра

направленные линии

Не направленные линии

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

ориентируется на что то

Дерево

используется для отображения

Сеть

Решите задачи.

№ 1

На следующем графе изображена система возможного переливания крови. Изучите его и укажите:

А) тип графа; Б) вершины; В) тип линий связей;

Г) какую кровь может получить человек с первой группой, со второй группой, с третьей группой, с четвертой группой крови.

№ 2

Составьте родословное дерево потомков Владимира Мономаха.

Владимир Мономах умер в 1125 г. Он оставил 4 сыновей: Мстислава (год смерти — 1132), Ярополка (1139), Вячеслава Туровского (1154) и Юрия Долгорукого (1157). После Мстислава осталось 3 сына: Изяслав Волынский (1154), Всеволод Новгородский (1138) и Ростислав Смоленский (1168). У Изяслава Волынского был сын Мстислав (1170), у Мстислава сын Роман (1205), у Романа - Даниил Галицкий (1264). Ростислав Смоленский имел 4 сыновей: Романа (1189), Рюрика (1215), Давида (1197) и Мстислава Храброго (1180). После Романа Ростиславича остался сын Мстислав Киевский (1224), после Мстислава Храброго - сын Мстислав Удалой (1228). Юрий Долгорукий имел 3 сыновей: Андрея Боголюбского (1175), Михаила (1177) и Всеволода (1212). Сыновьями Всеволода были Константин (1217), Юрий (1238) и Ярослав (1246). У Ярослава Всеволодовича было 3 сына: Александр Невский (1263), Андрей Суздальский (1264) и Ярослав Тверской (1272). Сыновья Александра Невского: Димитрий Переяславский (1294), Андрей Городецкий (1304) и Даниил Московский (1303). У Андрея Сульдальского был сын Василий (годы его жизни неизвестны), у Ярослава Тверского - сын Михаил.

№ 3

Нарисуйте в виде графа систему, состоящую из одноклассников, между которыми существуют следующие взаимоотношения: дружат Андрей и Даша, Андрей и Маша, Даша и Коля, Коля и Андрей.

С кем Андрей может поделиться секретом, не рискуя, что он станет известен кому-то другому.

№ 4