Графические информационные модели. Графы. Моделирование и формализация

Граф
Граф — это совокупность объектов со связями между ними.
Вершины — это объекты.
Рёбра — это связи.

Разнообразие вершин и связей

Граф
Ориентированный граф
Неориентированный граф

Пример графа
В соревнованиях по шахматам участвовало 6 учащихся с 9-го по 11-й класс.
встрече они все обменялись рукопожатиями.
Сколько всего было сделано
При
рукопожатий?
1
2
3
4
5
6
Ответ: на турнире было сделано 15 рукопожатий.

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

Пример взвешенного графа
Между городами A, B, C, D, E построены дороги.
путь из города А в город Е, если известно, что из города А в город В расстояние
100 км,
из А в С — 260 км,
Необходимо найти кратчайший
и из D в Е — 40 км.
из В в С — 140 км,
из В в Е — 400 км,
из С в D — 50 км,
из C в E — 100 км
А
В
С
D
E
100
260
140
50
400
100
40
АВ + ВЕ = 100 + 400 = 500
АВ + ВС + СЕ = 340
АС + СЕ = 360
АВ + ВС + CD + DE = 330
АC + CD + DE = 350
АC + CB + BE = 800

Цепь
Цепь — это путь по вершинам и рёбрам графа, в который любое ребро графа
входит не более одного раза.

Цикл
Цикл — это цепь, в которой начальная и конечная вершины совпадают.

Сеть
Сеть — это граф с циклом.

Пример
Ю
Т
М
А
У Антона в семье есть мама Татьяна, папа Юрий и сестра Маша.
сын
отец
мать
дочь
дочь
отец
сын
мать
брат
сестра
муж
жена

Семантическая сеть
Семантическая сеть — это информационная модель, имеющая вид графа,
вершинам которого соответствуют определённые объекты, а рёбра задают
отношения между ними.

Графы как информационные модели

Дерево и его составляющие
Дерево — это граф, в котором нет циклов, то есть в нём нельзя из некоторой
вершины пройти по различным рёбрам и вернуться в ту же вершину.
Между любыми двумя вершинами дерева существует единственный путь.
Корень дерева — это одна и единственная главная его вершина.
Потомки — это вершины, которые соответствуют классам нижнего уровня.
Листья — это вершины, которые не имеют потомков.

Пример

Пример