Табличные модели, диаграммы

Таблицы
Свойства объектов:

Таблицы
Связи между объектами:

Таблицы
Изменение свойств:

Оптимальный маршрут
Березовое: 8:00
Полевое
Б
16:00
07:30
11:50
14:00
14:40
16:10

Анализ диаграмм

Анализ диаграмм
а) все «Форды» могут принадлежать менеджерам
б) все охранники могут ездить на «Ауди»
в) все «Тойоты» могут принадлежать рабочим
г) все рабочие могут ездить на «Фордах»
10 + 40 + 30 + 20 = 100
25
25
50

Моделирование. Деревья

Что такое дерево?
Дерево – это структура данных, которая служит моделью многоуровневой структуры (иерархии).
Лес – это несколько деревьев.

Из чего состоит дерево?
A –
D, E, F, G –
корень
листья
B, C –
промежуточные
узлы
Путь — это последовательность узлов, где каждый следующий связан с предыдущим.
Высота дерева — это количество уровней.
Поддерево — это часть дерева, которая тоже представляет собой дерево.
левое
поддерево
правое
поддерево

Родители и дети
B – родитель для D и E
D и E – сыновья для B
Предок – потомок: между ними есть путь.
A и B – предки для D и E
B, D и E – потомки для A
Родитель – сын: между ними есть ребро.

Генеалогическое дерево
Иванов А.Б.
Иванова Д.А.
Семёнова М.А.
Иванов К.А.
Семёнов C.C.
Семёнов А.C.
Иванов C.К.

Классификации
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2. Кошкоообразные 2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые

Файловая система

Моделирование. Графы

Графы
«От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и Ягодное. Между Солнцевым и Грибным и между Грибным и Ягодным также есть дороги. Кроме того, есть дорога, которая идет из Грибного в лес и возвращается обратно в Грибное».

Графы
Граф – это набор вершин (узлов) и связей между ними (рёбер).

Матрица и список смежности
петля
Матрица смежности
Степень вершины – это количество связанных с ней рёбер (петля считается дважды!).
2
3
5
2

Постройте матрицу смежности

Постройте матрицу смежности

Нарисуйте граф

Нарисуйте граф

Нарисуйте граф

Связность графа

Дерево – это граф?
дерево
ABC ABDC
BCD CCC…

Взвешенные графы
12
8
2
5
4
6
Весовая матрица:
вес ребра

Постройте весовую матрицу

Постройте весовую матрицу

Нарисуйте граф

Нарисуйте граф

Нарисуйте граф

Кратчайший путь (перебор)
A
B
С
E
С
D
С
D
E
D
2
4
6
2
4
6
1
3
1
3
9
7
5
8
4
1
3
7
дерево возможных путей
Определите кратчайший путь между пунктами A и D.

Кратчайший путь
Определите кратчайший путь между пунктами A и E.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра называю дугами.

Нарисуйте орграф

Нарисуйте орграф

Количество путей из А в Ж
1
1
1
1+1+1=3
1
1+1+1+1+3=7
1

Количество путей из А в К

Количество путей из А в К