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

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

2.

Граф – это информация о составе и
структуре системы, представленная в
графической форме

3.

Граф состоит из вершин, связанных дугами или
рёбрами.
Граф
, в котором все линии направленные,
называется ориентированным

4. Применение графов в жизни

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

5. Применение графов в жизни

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

6. Применение графов в жизни

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

7. Применение графов в жизни

Устройство
шариковой
ручки

8. Основные понятия

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

9. Взвешенный граф

Репкино
Дедкино
Кошкино
Репкино

10. Примеры решения задач

Построить граф классификации геометрических
объектов.

11.

Иерархические системы –
системы, элементы которых находятся
друг с другом в отношении вложенности
или подчинённости.
Примеры:
система образования,
географические системы,
файловые системы,
системы классификации в науке.

12.

Дерево – это граф иерархической системы, в
котором нет петель. Вершины верхнего уровня
связаны с вершинами нижнего уровня как
«один ко многим»
1-й уровень
2-й уровень

13.

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

14. Дерево

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

15. Дерево

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

16. Дерево

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

17.

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