X Международная студенческая научная конференция Студенческий научный форум - 2018

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

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

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

Для начала, Эйлер нарисовал граф для решения этой задачи, представленный на рисунке 1.

Рисунок 1

В процессе своих рассуждений, он пришел к следующим теоретическим выводам:

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

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

3. Граф с более чем 2 вершинами с нечетными степенями невозможно начертить одним росчерком [2].

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

Решая задачу о Кенигсбергских мостах, Леонард Эйлер заложил основы теории графов как математической науки. На современном этапе развития теории графов определение ключевого понятие – графа – определяют таким же образом, как совокупность множества точек и совокупность инцидентных им отрезков.

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

А

В

Рисунок 2

Например, на рисунке 2 изображен граф, все вершины которого четные, кроме вершин А и В (только у этих вершин имеется нечетное количество исходящих ребер). Так как нечетных вершин две, то данный граф можно начертить, не отрывая карандаша от бумаги.

Рисунок 3

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

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

Огромное значение теории графов имеет при визуализации, иллюстрации, представлении данных, что позволяет более конструктивно подходить к различным областям знаний. Графы нашли применение в самых разных областях науки, техники и практической деятельности. Они используются при проектировании электрических сетей, планировании транспортных перевозок, построении молекулярных схем. Применяется теория графов также в экономике, психологии, социологии, биологии [1].

Список используемых источников

1. Гладких, О.Б. Основные понятия теории графов: учебное пособие / О.Б. Гладких, О.Н. Белых. - Елец: ЕГУ им. И.А. Бунина, 2011. – 177 с.

2. Alisa. Задача о семи кенингсбергских мостах… Или все-таки о восьми? 28.08.2012 [Электронный ресурс] – Режим доступа: http://i-fakt.ru/zadacha-o-semi-keningsbergskix-mostax-ili-vse-taki-o-vosmi/

Код для цитирования: Скопировать