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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задания для самостоятельного выполнения Задача 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). Текстовый редакторГрафический редактор