Теория графов
В элементарном понимании граф – это непустое множество точек, некоторые из которых соединены линями (отрезками, дугами). Точки называются вершинами графа, а линии – рёбрами.
Число рёбер, выходящих из данной вершины, называется степенью этой вершины. В теории графов важно – чётной или нечётной является степень вершины. Для простоты сами вершины также именую чётными или нечётными в соответствии с их степенью.
Считается, что начало теории графов было положено Леонардом Эйлером (1707–1783) при отыскании решения головоломки о знаменитых Кенигсбергских мостах через реку Прегель (раннее название Переголя).
В своем письме, отправленном из Петербурга 13 марта 1736 года итальянскому математику Мариони, он описал решение проблемы прохождения каждого из мостов по одному разу и возвращения в исходную точку. Несколько позже Эйлер предложил графическую модель этой задачи, ввел специальную терминологию и сформулировал общие правила, по которым выясняется разрешимость головоломок подобного рода.
К ним, в частности, относится возможность изображать фигуры, не отрывая карандаша от бумаги и не проводя одну и ту же линию дважды. Эти развлечения являются очень давними (например, «сабля Магомета»).
Эйлер обратился к общему случаю: при каких условиях в конечном графе можно найти такой цикл, в процессе прохождения которого каждое ребро графа использовалось бы один раз? Впоследствии такие графы получили название Эйлеровых.
Общеизвестным детским развлечением является задание: нарисовать «открытый конверт», не отрывая карандаша от бумаги и не проводя дважды одну линию.
Успешность осуществления этого задания зависит от того, с какой точки начинается рисование.
А вот «конверт с двумя открытыми боковыми клапанами» таким образом можно изобразить, начиная с любой точки.
Фигуры, изображение которых подчиняется двум требованиям, сформулированными выше, называются уникурсальными.
Вопрос: а можно ли таким же образом изобразить «закрытый конверт»?
Нет, так как эта фигура не является уникурсальной.
Как это определить без затрат времени, бумаги и чернил?
Всё зависит от того, сколько нечётных вершин в фигуре. Если все вершины чётные (конверт с двумя клапанами), то выполнить задание можно всегда. И от выбора начальной вершины успех не зависит.
Если нечётных вершин две (открытый конверт), то задание выполняется, если начинать из одной нечётной вершина, а заканчивать в другой.
А вот если число нечётных вершин графа больше двух, то задание невыполнимо.
Постановка и решение задачи о Кенигсбергских мостах Эйлером знаменуют начало разработки теории графов как математической дисциплины. Эта работа была единственной на протяжении почти ста лет. Первая книга Д.Кенига о графах, датированная 1936 годом, вышла в Лейпциге спустя 200 лет после первой постановки проблемы Эйлером.
В середине XIX века возобновился интерес к проблемам теории графов по нескольким причинам. Прежде всего, многие популярные развлечения поддавались формулировкам в соответствующих терминах. В частности, головоломки об обходах и лабиринтах, по сути, были первыми задачами теории графов. Например, коридоры лабиринта принимаются за ребра, а перекрестки – за вершины графа. Необходимо определить в таком графе маршрут для прохождения из одной заданной вершины к другой. Первый систематический метод для нахождения выхода из лабиринта был предложен американским учёным Норбертом Винером (1894–1964).
В 1859 году ирландский математик Вильям Роуэн Гамильтон (1805–1865) придумал игру, в которой было необходимо обойти по ребрам каждую вершину додекаэдра, причем ровно один раз. Гамильтоновы циклы определяются аналогично эйлеровым графам только по отношению к вершинам: это маршрут, проходящий через каждую вершину один раз.
Существует еще одна известная интерпретация этого факта. В компании из нескольких человек некоторые являются друзьями. При каких условиях можно всех рассадить за круглым столом так, чтобы по обе стороны каждого сидели его друзья?
Популярная задача о коммивояжере также относится к гамильтоновым цепям. Формулировка её такова: найти кратчайшую дорогу, проходящую через все города некоторой местности, расстояния между которыми известны, и возвратиться в исходный пункт.
Ситуации, связанные с доставкой заказанных товаров, способствовали созданию эффективных методов решения транспортных задач. Основной задачей о схеме дорог обычно считается определение кратчайшего пути между двумя пунктами. Внешне напоминает задачу о торговце задача английского математика Артура Кэли (1821–1895) о минимальном соединении: проложить между n городами железнодорожные линии так, чтобы не строить лишних. Сколькими способами можно построить такую систему, и какая из них будет оптимальной?
Замечательным стимулом к изучению структур графов стала знаменитая проблема четырёх красок, первоначальный элемент решения которой высказал немецкий математик Август Фердинанд Мёбиус (1790–1868) на лекции в 1840 году: «… на плоскости нельзя начертить пять областей так, чтобы каждые две из них имели общую границу».
Около 1950 года шотландцем Огастесом де Морганом (1806–1871) была сформулирована и поставлена перед математиками задача о количестве цветов для правильной раскраски карты.
В 1878 году Кэли придал задаче прикладной характер: нужно было доказать, что каждую географическую карту на плоскости (или глобусе) можно правильно раскрасить четырьмя красками. Никакая другая проблема не породила такого числа работ в области теории графов, имеющих теоретическую и прикладную значимость.
К XX веку начали возникать задачи, связанные с графами, не только в физике (схема электрической цепи суть граф) или химии (графическая модель изомеров углеводородов), но и в экономике (сетевое планирование). Появились предпосылки для выделения теории графов в самостоятельный математический раздел.
Продолжение следует. До встречи!