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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A B CD E

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

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

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

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)= =

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

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