графы

1.

ГРАФИЧЕСКИЕ
ИНФОРМАЦИОННЫЕ
МОДЕЛИ
МОДЕЛИРОВАНИЕ И
ФОРМАЛИЗАЦИЯ

2.

Ключевые слова
схема
карта
чертёж
график
диаграмма
граф
сеть
дерево

3.

Многообразие графических
информационных моделей
Схема
Граф
Карта
Графическая
модель
Чертёж
График
Диаграмма

4.

Схемы
Схемыввбиологии
физике
истории
Р
генотип
гаметы
F1
♀
♂

5.

Географическая карта Евразии

6.

Чертёж детали

7.

График описания движения

8.

Диаграмма

9.

Графы
Граф состоит из вершин, связанных линиями.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в
неё же, называется петлей.
дуга
А
ребро
В
петля
С

10.

Взвешенный граф
Граф называется взвешенным, если его вершины или
рёбра
характеризуются
некоторой
дополнительной
информацией - весами вершин или рёбер.
90
80
C
D
70
60
B
E
50
A
90
Протяжённость дорог в километрах

11. Неориентированный граф

Неориентированный граф - граф, вершины
которого соединены ребрами.
С помощью таких графов могут быть представлены
схемы двухсторонних (симметричных) отношений.
Юра
Аня
Маша
Коля
Витя
Граф, отражающий отношение «переписываются»
между объектами класса «дети»

12. Ориентированный граф

Ориентированный граф - граф, вершины
которого соединены дугами.
С помощью таких графов могут быть представлены
схемы односторонних отношений.
Юра
Аня
Маша
Коля
Витя
Граф, отражающий отношение «пишет письма».

13.

Сеть и дерево
Цепь – путь по вершинам и
рёбрам графа, в который любое
ребро графа входит не более одного
раза.
Цикл - цепь, начальная и конечная
вершины которой совпадают.
Сеть - граф с циклом.
Дерево – это граф, в котором нет циклов.

14.

Информационные модели
на графах
Корень – главная вершина дерева.
Предок – объект верхнего уровня.
Потомок – объект нижнего уровня.
Листья – вершины, не имеющие потомков.
?
Укажите перечисленные объекты у дерева
Чемпион
Финалисты
Участники ½ финала
Участники ¼ финала
Первоначальные игроки
Олимпийская система спортивных соревнований

15.

Генеалогическое древо
Родословная А. В. Суворова

16. Графы при решении задач

?
Сколькими способами можно рассадить
в ряд на три стула трёх учеников?
Выписать все возможные случаи.
Чтобы выписать все случаи,
решение можно представить в виде дерева.

17. Решение в виде дерева

О
А
В
С
С
В
С
В
А
С
С
А
А
В
В
А
Если
на первом
стуле
сидит
А,
то на
Выпишем
все
возможные
случаи:
Очевидно,
На первый
что
стул
третий
посадим
стул
любого
в ученик
каждом
ученика:
случае
второй
стулВ-А-С,
можно
посадить
В илиС-В-А.
С.
А-В-С,
А-С-В,
В-С-А,
С-А-В,
займёт
оставшийся
А,В,С
ученик
Действуем аналогично и для других учеников.

18.

Вопросы и задания
Сколько трёхзначных чисел можно записать с помощью
цифр 2, 4, 6 и 8 при условии, что в записи числа не
должно быть одинаковых цифр?
Для составления цепочек используются бусины,
помеченные буквами: A, B, C, D, E.
На первом месте в цепочке стоит одна из бусин A, C,
E. На втором — любая гласная, если первая буква
гласная, и любая согласная, если первая согласная.
На третьем месте — одна из бусин C, D, E, не
стоящая в цепочке на первом месте.
Сколько цепочек можно создать по этому правилу?

19. Ориентированный граф

20. Ориентированный граф

21. Задание 1:

22. Задание 2:

23.

Самое главное
В графических информационных моделях для наглядного
отображения объектов используются условные графические
изображения, дополняемые числами, символами и текстами:
схемы, карты, чертежи, графики и диаграммы, графы.
Граф состоит из вершин, связанных линиями - рёбрами.
У взвешенного графа вершины или рёбра характеризуются
некоторой дополнительной информацией - весами вершин (рёбер).
Цепь – это путь по вершинам и рёбрам графа, в который любое
ребро графа входит не более одного раза.
Цикл - цепь, начальная и конечная вершины которой совпадают.
Сеть - граф с циклом.
Дерево - граф иерархической системы. Между любыми двумя
вершинами дерева существует единственный путь.