Впервые понятие «граф» ввел в 1936г. венгерский математик Денни Кениг. Но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана в 1736г. С помощью графов изображаются схемы различных дорог, линии воздушных сообщений, газопроводов, теплотрасс, электросетей, а также микросхемы, дискретные многошаговые процессы, системы различных бинарных отношений, химические структурные формулы и другие диаграммы и схемы. Применяются графы для решения задач химии, экономики, электротехники и автоматики. Также они широко используются в информатике и строительстве. Без графов сложно анализировать классификации в различных науках.
Теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Дело в том, что теория графов предоставляет очень удобный язык для описания программных (да и многих других) моделей.
Специфика теории графов заключается в том, что изучение ее понятий и методов происходит в форме открытия новых инструментов познания окружающего мира. У педагогов появляется возможность использования новых подходов к обучению, называемых современными педагогическими технологиями.
Педагогическая технология - совокупность, специальный набор форм, методов, способов, приёмов обучения и воспитательных средств, системно используемых в образовательном процессе, на основе декларируемых психолого-педагогических установок. Это один из способов воздействия на процессы развития, обучения и воспитания студента. Сюда можно отнести такие методы, как метод проблемного изложения, дискуссии, метод мозгового штурма, метод критического мышления, мини-исследования, деловые игры, метод анкетирования и др.
Особенно важно наличие наглядной графической интерпретации понятия графа. Само название «граф» подразумевает наличие графической интерпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.
Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.
Например:
Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис.1). Эта задача была решена Эйлером в 1736 году.
Рис. 1. Иллюстрация к задаче о Кенигсбергских мостах
Задача о трех домах и трехколодцах. Имеется три дома и три колодца.
Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена Куратовским в 1930 году.
Рис. 2. Иллюстрация к задаче о трех домах и трех колодцах
Это две задачи, решенные всемирно известными учеными.
Я предлагаю решение нескольких задач с использованием графов, которые были решены студентами на уроках дисциплины «Дискретная математика».
Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля - Меркурий; Плутон - Венера; Земля - Плутон; Плутон - Меркурий; Меркурий - Вене; Уран - Нептун; Нептун - Сатурн; Сатурн - Юпитер; Юпитер - Марс и Марс - Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса? (Используем метод мини-исследования)
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет - линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Задача 2. В государстве 100 городов. Из каждого города выходит 4 дороги. Сколько всего дорог в государстве? (Используем метод дискуссии)
Решение. Подсчитаем общее количество выходящих городов дорог - 100 · 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза - она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.
Задача 3. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз? (Используем метод проблемного изложения)
Решение: нет.
Основой педагогической технологии служит четкое определение конечной цели. Высокие результаты обученности теории графов могут быть достигнуты при применении вышеописанных современных педагогических технологий.
Литература
- Спирина, М.С. Дискретная математика: учебник / М.С.Спирина, П.А.Спирина. - Москва, издательский центр «Академия», 2012.
- Кочетков, Е.С. Теория вероятностей и математическая статистика: учебник / Е.С.
- Кочетков, Е.С., С.О.Смерчинская, В.В.Соколов. - Москва, ФОРУМ-ИНФРА-М, 2003.