Информационные модели на графах Информационные модели на графах Смогоржевская Светлана Юрьевна, учитель информатик МОУ «Гимназия 25» городского округа. - презентация

1

2 Информационные модели на графах Информационные модели на графах Смогоржевская Светлана Юрьевна, учитель информатик МОУ «Гимназия 25» городского округа Ревда Свердловской обл

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

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

5 Основные понятия. Теоретическое введение. Граф, в котором все линии направленные, называется ориентированным. Две вершины, соединенные дугой или ребром, называются смежными. Две вершины, соединенные дугой или ребром, называются смежными. В случае представления информации о системе в виде графа компоненты системы изображаются вершинами, а связи между ними линиями.

6 Графы используются во многих областях человеческой деятельности Например:Например: Знакомую всем схему метрополитена можно рассмотреть как граф. Вершинами являются станции метро, линии отражают рельсовую связь между станциями. Другие примеры: 2 3 продолжить

7 Пример 2 Этот пример относится к органической химии. Известно, что свойства химических веществ, называемых углеводородами, зависят не только от того, из какого количества атомов углерода и водорода состоит молекула, но и от способа их соединения, структуры молекулы. На рисунке изображены структуры молекул трех разных веществ, состоящих из одинакового числа атомов углерода (С) и водорода (Н). Принятый в химии способ отображения структуры молекулы тоже является графом. назад

8 Пример 3: Этот пример относится к медицине. Как известно, у разных людей кровь отличается по группе. Всего групп крови четыре. В нормальных условиях номер группы крови роли не играет, а вот при переливании, играет и весьма существенную. Дело в том, что не все группы крови совместимы. Возможность переливания крови разных групп может быть отражена с помощью графа. Этот пример относится к медицине. Как известно, у разных людей кровь отличается по группе. Всего групп крови четыре. В нормальных условиях номер группы крови роли не играет, а вот при переливании, играет и весьма существенную. Дело в том, что не все группы крови совместимы. Возможность переливания крови разных групп может быть отражена с помощью графа. Назад

9 О некоторых типах графов Взвешенный (размеченный) граф –это граф, в котором с вершинами или линиями связана некоторая дополнительная информация. Это информация называется весом вершины или линии. Дерево – это граф, предназначенный для отображения таких связей между объектами как вложенность, подчиненность, наследование и т.д. Взвешенный (размеченный) граф –это граф, в котором с вершинами или линиями связана некоторая дополнительная информация. Это информация называется весом вершины или линии. Дерево – это граф, предназначенный для отображения таких связей между объектами как вложенность, подчиненность, наследование и т.д.

10 Последовательность формализации при создании графа Выявление всех элементов объекта; Определение характеристик элементов (названий, весов, номеров и т.д.); Установление наличия и вида связей между элементами; Определение характеристик связей – весов ребер и дуг; Выбор формы изображения вершин и ребер, ввод условных обозначений в случае необходимости; Представление выделенных элементов и связей в графической форме. Выявление всех элементов объекта; Определение характеристик элементов (названий, весов, номеров и т.д.); Установление наличия и вида связей между элементами; Определение характеристик связей – весов ребер и дуг; Выбор формы изображения вершин и ребер, ввод условных обозначений в случае необходимости; Представление выделенных элементов и связей в графической форме.

11 Примеры решения задач Задача 1 Построить граф классификации геометрических объектов.

12 Примеры решения задач Задача2 Построить схему организации танкового батальона ФРГ по состоянию на середину 70-х гг. ХХ в.

13 Для создания компьютерных информационных моделей в виде графов можно использовать текстовые и графические редакторы. Графический редактор Текстовый редактор Microsoft Word Логическая схема понятия «Информация» Логическая схема понятия «Модель» Родословное дерево первых русских князей

14 Задания для самостоятельного выполнения Задача 1 Отразите в виде графа структуру следующих объектов, рассматривая их как системы: а)велосипед б)зонтик в)учебник по математике. Задача 1 Отразите в виде графа структуру следующих объектов, рассматривая их как системы: а)велосипед б)зонтик в)учебник по математике. Внимание! При выполнении задания результат своей работы сохраните в своей папке, а в исходный файл не вносите изменений.Внимание! Текстовый редакторГрафический редактор

15 Задания для самостоятельного выполнения Задача 2 Изобразить в виде графа биологическую классификацию.Согласно биологической классификации выделяют 3 империи (надцарства): археобактерии, эукариоты, прокариоты. К империи эукариотов относятся царства грибов, растений и животных. К царству животных относятся типы членистоногих, моллюсков, иглокожих, кишечнополостных, хордовых и др. К типу хордовых относятся классы рыб, амфибий, рептилий, млекопитающих, птиц. К классу млекопитающих относятся отряды китов, ластоногих, хищных, грызунов, копытных и др. К отряду хищных относятся семейства медвежьих, енотовых, псовых, виверровых, кошачьих и др. К семейству псовых относятся роды лисиц, енотовидных собак, собак, фенеков, песцов и др. К роду собак относятся виды собак домашних, волков, шакалов, койотов. К виду собак домашних относятся овчарки, спаниели, сенбернары, доги, болонки и др. Задача 2 Изобразить в виде графа биологическую классификацию.Согласно биологической классификации выделяют 3 империи (надцарства): археобактерии, эукариоты, прокариоты. К империи эукариотов относятся царства грибов, растений и животных. К царству животных относятся типы членистоногих, моллюсков, иглокожих, кишечнополостных, хордовых и др. К типу хордовых относятся классы рыб, амфибий, рептилий, млекопитающих, птиц. К классу млекопитающих относятся отряды китов, ластоногих, хищных, грызунов, копытных и др. К отряду хищных относятся семейства медвежьих, енотовых, псовых, виверровых, кошачьих и др. К семейству псовых относятся роды лисиц, енотовидных собак, собак, фенеков, песцов и др. К роду собак относятся виды собак домашних, волков, шакалов, койотов. К виду собак домашних относятся овчарки, спаниели, сенбернары, доги, болонки и др. Текстовый редакторГрафический редактор

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