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

Основные понятия
Граф – это средство для наглядного представления состава и структуры системы
Граф состоит из вершин, связанных дугами или рёбрами.
ВЕРШИНЫ
дуга
ребро
смежные вершины
Граф , в котором все линии направленные, называется ориентированным
ЛИНИИ

Применение графов в жизни
Вершинами графа являются станции метро, линии отражают рельсовую связь между станциями.

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

Применение графов в жизни
Возможность переливания крови разных групп отражены с помощью графа. Глядя, на который легко понять, какие существуют варианты по переливанию крови.
I
I
III
III
II
II
IV
IV

Применение графов в жизни
Устройство шариковой ручки

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

Взвешенный граф
Ангарск
Китай
Савватеевка
Одинск
4
12
25
12

Основные понятия
Дерево – это граф, предназначенный для отображения таких связей между объектами как вложенность, подчинённость, наследование.
Принцип построения:
Рисуем «главную» вершину, которая не зависит ни от одной другой вершины(корень дерева или вершина «1 уровня»
Добавляем вершины второго уровня. (их может быть сколько угодно, все связаны с вершиной 1го уровня, но не связаны между собой.
И.т.д.

Дерево
Рюрик
(879)
Игорь
( 945)
Святослав
(972)
Ярополк (980)
Владимир Св (1014)
Олег (977)
Изяслав Полоцкий(1001)
Святополк
(1018)
Борис (1015)
Ярослав (1054)
Глеб (1015)
ПРЕДОК
ПОТОМКИ
КОРЕНЬ

Дерево
Признак «дерева».
Потомки связаны только с предком, но не связаны между собой

Дерево
Рюрик
(879)
Игорь
( 945)
Святослав
(972)
Ярополк (980)
Владимир Св (1014)
Олег (977)
Изяслав Полоцкий(1001)
Святополк
(1018)
Борис (1015)
Ярослав (1054)
Глеб (1015)
Восстановить всех предков Бориса.

Дерево
География: население и народное хозяйство России
Введение
Часть1. Общий обзор России
Россия на карте мира
Заселение территории
Сфера влияния России
Экономическое влияние России
Человек и природа
Природные условия и человек
Часть 2. Районы России
Подходы к районированию
Заключение
Иерархическая структура разделов книги

ЗАДАНИЯ
для самостоятельной работы
Отразите в виде графа структуру следующего объекта, рассматривая его как систему:
Плоские фигуры, круг, эллипс, трапеция, параллелограмм, прямоугольник, ромб, квадрат
Плоская фигура
Круг
Эллипс
Трапеция
Параллелограмм
Прямоугольник
Ромб
Квадрат

ЗАДАНИЯ
для самостоятельной работы
На рисунке приведена схема организации танкового батальона ФРГ, по состоянию на середину 70х годов 20 века. Ромбиками обозначены танки, входящие, в то или иное подразделение. Подсчитайте количество танков в танковой роте и общее количество танков в батальоне.
5 в танковой роте
8 в батальоне

Индивидуальное домашнее задание
Изобразить в виде графа информацию о:
Мотострелковый батальон армии СССР
Мотопехотный батальон армии США
Мотопехотный батальон армии ФРГ
Биологической классификации№1
Биологической классификации №2
Биологической классификации №3
Классификации в русском языке
Родословное дерево Владимира Мономаха