Урок информатики на тему «Теория графов. Решение задач» (8–9 классы)

©кабинет 21, 2006-2017

Теория графов. Решение задач

Класс: 8-9 класс.

Цели урока.

Образовательные: формирование понятия «граф» и его основных элементов; формирование умения составлять граф по таблице.

Развивающие: развивать логическое мышление, внимание, памяти, умение планировать свою деятельность.

Воспитательные: воспитывать усидчивость, трудолюбие.

Ход урока:

1. Введение. Для того, чтобы представить информацию о составе и структуре системы графически, необходимо в виде чертежа изобразить компоненты системы и соединить их между собой какими-либо линиями. Например: Структура молекулы воды: компоненты системы (атомы) соединены между собой линиями.

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

Элементы графа: Вершины графа — это компоненты системы изображаемые кругами, ова­лами, прямоугольниками. Ребра — это линии, связывающие компоненты между со­бой определенным образом.

2. История происхождения. Издавна среди жителей Кёнигсберга (Калининград) была распространена загадка: как пройти по всем мостам (через реку Преголь), не проходя ни по одному из них дважды. Многие люди пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но доказать или опровергнуть возможность существования такого маршрута никто не мог.

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

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Созданная Эйлером теория графов нашла широкое применение (в транспортных системах – составление оптимальных маршрутов доставки грузов, экономике и т.д.).

3. Решение задач. Нахождение кратчайшего маршрута по таблице.

Задача, разбор и решение ее – находится в Презентации:

https://www.emaze.com/@AOORWLRII/breaking-news?hidebuttons