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

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

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

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

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

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

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

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

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

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

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

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

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

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

14 Задания 3. Формальные описания реальных объектов и процессов

15 Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице: Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

16 По таблице построим граф A B CD E

17 1. Свяжем с каждой вершиной маркер, длина пути от А 2. Длина пути из А в А =0 3. Маркер вершины В равен маркеру вершины А + длина пути от А до В = 0+1=1 4. Вершина А больше ни с чем не связана. Исключим её из рассмотрения 5. Маркер С=1+2=3 6. Маркер D=1+2=3 7. Маркер Е=1+7=8 8. Исключим вершину B 9. C связана с E 10. Маркер Е=3+3=6 найден путь короче 11. Исключим С 12. Из D в E есть путь 13. Маркер E= 3+4=7 больше A B CD E

18 Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице: Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

19 По таблице построим граф A B CD E

20 A B CD E

21 A B CD E По графу найдите путь из А в Е

22 Задания 11. Анализ информации, представленной в виде схем

23 На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

24 1. Из А в А существует 1 путь 2. Найдем вершину соединенную с А, в которую входит только 1 путь (это вершины Б, В и Д) 3. В вершину Б ведет только 1 путь из А, Свяжем с вершиной Б количество путей ведущих из А (1), тоже можно сказать и о вершинах В и Д (новых путей в эти вершины не ведет) 4. В вершину Е ведет 1 путь из Б + 1 путь из В = 1+1=2 5. В вершину Г ведут пути из В(1), из А(1), из Д(1)=1+1+1=3 6. В вершину Ж идет только 1 путь из Д и новых путей нет = 1 7. В К – из Е(2), из В(1), из Г(3), из Ж(1)= =

25 На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? 1 1 Б В 2 Д 1 А Г Е Ж К 8

26 На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? А 1 Г 1 В Б Е Д К