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

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

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

3 Вербальное описание Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино

4 Схематическое описание Это не карта местности. Здесь не выдержаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними

5 Граф Граф отображает элементный состав системы и структуру связей Составными частями графа являются вершины и ребра. Вершины это элементы системы Ребра это связи (отношения) между элементами. Вершина Ребро (симметричная связь)

6 Пример 1 Вершинами являются станции метро, линии отражают рельсовую связь между станциями - ребра. Никакой другой информации, кроме структуры метрополитена, схема-граф не содержит

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

8 Пример 3. Ориентированный граф Группы крови это вершины графа с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови Дуга (несимметричная связь) Вершина Петля

9 Взвешенный граф Взвешенный граф это граф, в котором с вершинами или линиями связана дополнительная информация. Эта информация называется весом вершины или линии.

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

11 Дерево Дерево это граф, предназначенный для отображения таких связей между объектами как вложенность, подчиненность, наследование и т.п. Сначала рисуем «главную» вершину, которая не зависит ни от одной другой вершины. Эта вершина называется корнем дерева и является единственной вершиной «1-го уровня». Далее добавляем вершины «2-го уровня». На каждом шаге добавляем вершины очередного уровня, каждая из которых будет связана ровно с одной вершиной предыдущего уровня и не будет иметь никаких иных связей

12 Дерево Дерево ориентировано, причем дуги направлены от верхних вершин к нижним. Верхняя вершина называется предком для связанных с ней нижних вершин Нижние вершины потомками соответствующей верхней вершины. На любом дереве существует единственная вершина, не имеющая предка, корень и может быть сколько угодно вершин, не имеющих потомков, листьев. Все остальные вершины имеют ровно одного предка и сколько угодно потомков

13 Родословное дерево первых русских князей

14 иерархическая структура разделов книги

15 граф классификации геометрических объектов

16 Даны значения трех переменных величин: А, В, С. Следует найти наибольшее из них, присвоить его переменной МАХ и вывести на экран

17 Биологическая классификация - 1 Согласно биологической классификации выделяют 3 империи (надцарства): археобактерии, эукариоты и прокариоты. К империи эукариотов относятся царства грибов, растений и животных. К царству животных относятся типы членистоногих, моллюсков, иглокожих, кишечнополостных, хордовых и др. К типу хордовых относятся классы рыб, амфибий, рептилий, млекопитающих, птиц. К классу млекопитающих относятся отряды китов, ластоногих, хищных, грызунов, копытных и др. К отряду хищных относятся семейства медвежьих, енотовых, псовых, виверровых, кошачьих и др. К семейству псовых относятся роды лисиц, енотовидных собак, собак, фенеков, песцов и др. К роду собак относятся виды собак домашних, волков, шакалов, койотов. К виду собак домашних относятся овчарки, спаниели, водолазы, сенбернары, доги, болонки и др. Построить граф классификации. Является ли он деревом?

18 Построить граф классификации. Используя граф, определить, какими признаками будут обладать следующие существа: 1) морской гребешок из класса двустворчатых, 2) трепанг из класса голотурий, 3) виноградная улитка из класса брюхоногих, 4) голова Горгоны из класса змеехвосток, 5) осьминог из класса головоногих, 6) мидия из класса двустворчатых, 7) теребра из класса брюхоногих, 8) каракатица из класса головоногих, 9) лилия стебельчатая из класса морских лилий, 10) кукумария из класса голотурий, 11) устрица из класса двустворчатых, 12) кальмар из класса головоногих.