Многообразие схем. Информационные модели на графах. Использование графов при решении задач

Ключевые слова
Схема
Граф
Сеть
Дерево

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

Жидкокристаллический дисплей
Схема
Оригинал

Схема зала
театра им. Вахтангова

Схема кабинета информатики
Что можно узнать из этой схемы?
Лекционные места
РМУ
РМП
?

Схема типовой квартиры
ВХОД
Сколько комнат в квартире?
Какова площадь каждой из них?
Каковы длина и ширина комнат?
Из какой комнаты есть выход
на балкон?
Какова площадь коридора?
Где на кухне находятся плита и раковина?
Давайте обсудим
?

Схема района Жулебино
(г. Москва)

Схема движения электропоездов
Показывает:
последователь-ность станций
расположение станций по зонам удаления
от Москвы
станции пересадок (узловые)

Схема метро
Санкт-Петербурга
Метро Санкт-Петербурга - самое глубокое в мире. Глубина многих станций – свыше 70 метров, а спуск на эскалаторе может занимать больше трех минут!

Карта центра
Санкт-Петербурга
Покажите досто-
примечательности,
представленные
на карте.
?

Пример блок-схемы алгоритма

Чертёж - условное графическое изображение предметов с точным соотношением размеров, получаемое методом проецирования. Он даёт представление о форме, величине, масштабе изображения предмета.
Болт и гайка из стали
Многообразие схем

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

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

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

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

Ориентированный граф
Ориентированный граф - граф, вершины которого соединены дугами.
Граф, отражающий отношение «пишет письма».
Приведите примеры цепи и цикла.
?
С помощью таких графов могут быть представлены схемы односторонних отношений.

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

Семантическая сеть

Информационные модели на графах
Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему.
Отношения подчиненности в школе

Классификация компьютеров
Дерево – граф иерархической структуры.
Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов
и петель.
Информационные модели на графах

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

Файловая структура
Укажите корневую вершину,
объекты 1-го, 2-го и 3-го уровней.
?

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

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