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

*Текст выделенный синим цветом и соответствующие примеры выписать в тетрадь

Здравствуйте. Сегодня на уроке мы с вами изучим новый материал и выполним практическую работу, после чего подведем итоги урока и запишем домашнее задание.

Теперь открываем свои тетради и записываем

Пятнадцатое февраля.

Классная работа

Тема: Многообразие схем. Информационные модели на графах. Деревья.

Видео к уроку - https://www.youtube.com/watch?v=_h4SlGZgNNY (6 мин)

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

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

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

• Граф – это схема, состоящая из множества точек, которые соединены линиями.

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

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

Наглядным средством представления состава и структуры системы является граф.

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними – отрезками или дугами.

 Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о Кёнигсбергских мостах.

По легенде один из жителей Кенигсберга спросил у своего товарища, сможет ли он пройти во всем мостам, связывающим островки на реке Преголь и вернуться в ту же самую точку, побывав на каждом мосту ровно один раз ?

Решить на практике эту задачу никто из жителей не смог (более 200 лет). Покорилась она лишь математику Эйлеру, решившему её с помощью графов.

*Для любознательных. Подумайте над решением задачи о Кёнигсбергских мостах.

Граф – это схема, состоящая из множества точек, которые соединены линиями.

Точки называются вершинами графа, а соединяющие линии – рёбрами.

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

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

Количество рёбер, выходящих из вершины графа, называется степенью вершины.

В ершина графа, имеющая нечётную степень, называется нечётной, а чётную степень – чётной.

Изолированная вершина – вершина, степень которой равна 0.

Конечная вершина графа – вершина, степень которой равна 1.

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

 Виды графов

Рассмотрим отношение «дети переписываются» (пишут письма друг другу). Отношение является двусторонним, поэтому вершины соединены линиями без стрелок.

Неориентированный граф – это граф, в котором все вершины соединены рёбрами.

Ориентированный граф – граф, рёбрам которого присвоено направление (в котором вершины соединены дугами).

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

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

Задача

Дан граф удалённости проживания 5–х друзей друг от друга по времени. Веса показывают время кратчайшего пути друг к другу в минутах. Витя пошёл в гости к Юре. Сколько времени займёт его кратчайший путь? Предположим, что дорогу, которая ведёт через улицу, на которой живёт Аня, перекрыли. Вите пришлось пойти другой дорогой. Сколько времени он потратил на дорогу?

Зарисуйте рисунок!

Имена вершин можно сокращать первыми буквами, если они не совпадают.

6

8

1. ВАЮ=14 (мин ) займёт кратчайший путь

6

11

7

1. ВКАЮ=24 (мин) займёт путь в обход

Ответ: кратчайший путь – 14 мин., путь в обход – 24 мин.

Цепь – путь по вершинам и рёбрам, включающий любое ребро графа не более одного раза.

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

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

Решение задач с помощью графов

Пример 1

Рассмотрим пример на видео https://www.youtube.com/watch?v=kuKW-fm9fA4

Пример 2

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E. Передвигаться можно только по указанным дорогам.

Решение.

1) Построим граф.

2) Решение методом последовательного перебора путей с заменой на лучший вариант

Получается пункты A—?.—D—E—F обязательны (по условию).

1–й вариант (добавим пункт В) A—B—D—E—F, его длина равна 2 + 3 + 5 + 5 = 15 (км)

2–й вариант A—С—D—E—F, его длина равна 4 + 3 + 5 + 5 = 17 (км)

3–й вариант A—D—E—F, его длина равна 8+5 + 5 = 18 (км)

Веса при решении можно записывать над линиями (или стрелочками, соответственно графу), как указано в задаче выше, можно рядом, как Вам удобнее

Рассуждения записывать не нужно!

Рассуждения. Заметим, что в Е можно попасть только из D и F, следовательно, в маршруте также обязательно должен присутствовать пункт D (видно по графу, попасть в Е можно только пройдя через D). Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут A—B—D—E—F, его длина равна 2 + 3 + 5 + 5 = 15 км. Теперь, начиная с начала маршрута, будем изменять путь, пользуясь следующим соображением: если расстояние, например, A—B—D больше расстояния A—D, то заменяем участок маршрута A—B—D на A—D. Попробовав произвести все такие замены, получим, что маршрут A—B—D—E—F — самый короткий из тех, что удовлетворяют условию задачи.

Любое другое изменение пути, через которые проходит маршрут, приводит к увеличению его длины.

Ответ: кратчайший путь между пунктами A и F, проходящий через пункт E = 15 км.

*задание переписывать не нужно, только таблицу и вопрос.

Задание 1

Построить граф и найти решение.

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет).

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Деревья

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

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

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

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

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

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

Структура диска в виде дерева:

Пример

1. Путь к папке Рисунки D:\Отдых\Рисунки

2. Полное имя файла урок D:\Документы\урок.doc

3. Имя и тип файла урок урок.doc

4. Диск D:\

Задание 2

*задание переписывать не нужно. Цифра и рядом ответ.

Укажите:

1. Путь к папке Рисунки

2. Полное имя файла Письмо

3. Имя и тип файла Интересный фильм

4. Полное имя файла Море

Домашнее задание

§ 13 стр. 89–96 и конспект изучить.