математический вестник выпуск №2
статья

Математический школьный вестник

«Мы – вместе с математикой»

МБОУ «СОСОШ №2»                                  Выпуск № 2 – февраль 2024

Знакомьтесь – граф

В истории черпаем мы мудрость, в поэзии –

остроумие, в математике – проницательность.

Ф. Бэкон

Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями.

Граф как математический объект представляет собой совокупность двух множеств:

∙ множества самих объектов, называемого множеством вершин;

∙ множества их парных связей, называемого множеством рёбер.

Элемент множества рёбер — это пара элементов множества вершин.

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

Начнём наше знакомство с нескольких задач.

Задача 1. Петя хочет нарисовать фигурку кенгуру одним росчерком, не отрывая карандаша от бумаги и не проводя по одной линии дважды. С какой точки ему нужно начать?

Задача 2. У Пети есть моток жёсткой проволоки длиной 12 дм. На какое наименьшее число кусков его надо разрезать, чтобы собрать каркас куба с ребром 1 дм?

Задача 3. Пять джентльменов, А, В, С, D и Е, встретились в клубе. Некоторые из них приветствовали друг друга рукопожатиями, причём А и В пожали руку по одному разу, С, D, и Е – по два. Известно, что А пожал руку Е. Какого рукопожатия наверняка не было?

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

 Первым применил графы для решения математических задач великий математик Леонард Эйлер (1707 – 1783). Эйлер родился и вырос в Швейцарии, а работал в основном в России и в Германии. Он был первопроходцем во многих областях математики.

 А слово «граф» первым стал использовать английский математик Джеймс Дж. Сильвестр (1814 – 1897).

Задача о Кенигсбергских мостах

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

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

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

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

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

 Маршрут на графе, который проходит по каждому ребру в точности один раз, называется эйлеровым, а граф, в котором существует эйлеров маршрут, называется эйлеровым графом. С эйлеровыми графами тесно связаны уникурсальные кривые, то есть линии, которые можно провести одним росчерком пера, не проводя ни по какому участку этой линии дважды (например, окружность или «восьмёрка»).

Кстати, не надо думать, что уникурсальные кривые обязательно проще, чем неуникурсальные – рассмотрим две линии, изображённые на рисунке.

Вернёмся к нашим задачам

 Начнём с задачи 1. Хорошо видно, что она очень похожа на задачу о мостах Кенигсберга, ведь для её решения тоже надо придумать способ обойти всю линию, не проходя нигде дважды. Заменим рисунок Пети графом, вершины которого – все отмеченные точки.

  На этом графе четыре вершины с нечётным числом рёбер – это B, C, D, и К, следовательно, Петя не сможет найти нужную ему точку.

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

 Наконец, рассмотрим задачу 3. Посмотрим граф с пятью вершинами (по количеству джентльменов). Обозначим вершины А, В, С, D и Е и будем соединять две вершины ребром, если джентльмены, названные этими буквами, обменялись рукопожатиями. Из условия задачи известно, что в нашем графе должно быть ребро АЕ, кроме того, из вершин А и В должно выходить по одному ребру, а из остальных вершин – по два. Таким образом, из вершины А больше не выходит ни одного ребра, а из вершины Е должно выходить ещё одно ребро. Если оно соединяет вершину Е с С или с D, то получаем один из графов, изображённых на рисунке. Если же предположить, что это ребро соединяет Е с В то окажется, что невозможно провести по два ребра, выходящих из вершин С и D (новые рёбра не могут проходить через вершины А, Е и В). Таким образом, джентльмен В не мог пожать руку джентльмену Е.

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

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

В выпуске участвовали ребята из 8 «б» класса: Колмакова Кира, Калитикова Настя