Видеоурок: Схемы.

Видеоурок: Информационные модели на графах. Использование графов.

В повседневной жизни нас окружает множество разнообразных схем: схема поезда, схемы дорожных развязок, схема зданий, схема расположения мест в зрительном зале кинотеатра и многие другие.

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

Например:

Схема радиоприемника

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

Схема зрительного зала

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

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

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

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

Граф состоит из вершин, связанных линиями.

Направленная линия (со стрелкой) называется дугой.

Линия ненаправленная (без стрелки) называется ребром.

Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей. 

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

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

Граф, отражающий отношение «переписываются» между объектами класса «дети»

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

Цикл – цепь, начальная и конечная вершины которой совпадают. Пример цикла – переписываются Маша Юра Аня Маша

Граф с циклом называют сетью.

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

Граф, отражающий отношение «пишет письма».

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

Каким весом характеризуются вершины и дуги данного графа? Вершины – это год основания города, а дуги (ребра) – это расстояние между этими городами.

Семантическая сеть – граф, в котором все связи различны, то есть, подписаны все вершины и дуги. Считается, что любую информацию можно представить в виде семантической сети, на которой будут отражены объекты (понятия) и связи (отношения) между ними.

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

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

Корень – главная вершина дерева.

Предок – объект верхнего уровня.

Потомок – объект нижнего уровня.

Листья – вершины, не имеющие потомков.

Давайте рассмотрим данное дерево: корень – компьютер, предок – суперкомпьютер, рабочая станция, персональный компьютер, потомок – настольный, портативный, карманный.

Файловая структура внешнего носителя (жесткий диск, флешка, карта памяти) тоже имеет иерархическую структуру – дерево.

Подумайте, что здесь корневая вершина (корень), объекты 1-го (предок), 2-го и 3-го уровней (потомки)?

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

1. На первый стул посадим  любого ученика: А, В, С

2. Если на первом стуле сидит ученик А, то на второй стул можно посадить В или С. Действуем аналогично и для других учеников

3. Очевидно, что третий стул в каждом случае займёт оставшийся ученик  

4. Выпишем все возможные случаи: А-В-С,  А-С-В,  В-А-С,  В-С-А,  С-А-В,  С-В-А.