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

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) кальмар — из класса головоногих.