Схемы. Многообразие схем

1.

МОУ «Киришская средняя общеобразовательная школа №8»
Тема урока:
Схемы
Многообразие схем
Информационные модели на графах
Использование графов при решении задач

2.

Многообразие схем
Схема - это представление объекта в общих,
главных чертах с помощью условных обозначений.
Схема радиоприёмника

3.

Схема зала
кинотеатра «Олимп»

4.

Схема кабинета информатики

5.

Схемы города Кириши

6.

Схема метро
Санкт-Петербурга

7.

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

8.

Изображение
вершин графа

9.

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

10.

Граф отношения «переписываются»
Цепь – путь по вершинам и ребрам, включающий любое
ребро графа не более одного раза.
Цикл – цепь, начальная и конечная вершины которой
совпадают.
Граф с циклом называют сетью.
Юра
Аня
Маша
Коля
Витя
Приведите примеры цепи и цикла.

11.

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

12.

Взвешенный граф
Взвешенный граф - граф, у которого вершины или
рёбра (дуги) несут дополнительную информацию (вес).
182
127
158
Москва, 1147
Владимир, 1108
Переславль Залесский, 1152
Каким весом характеризуются вершины и дуги данного графа?