Рис. 1

Расставим вдоль его ребер цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшими являются два числа по 28 км, соответствующие маршрутам M - B - Б - А - Г - М и M - Г - А - Б - В - М. Заметим, что это один и тот же путь, но пройденный в разных направлениях.

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

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

Рис. 2

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

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

Около вершин графа указаны числа – продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 2 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет. В этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т.д. И общее время строительства составит 160 дней, т.е. срок сократится лишь на 10 дней.

Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. Требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4л, т.е. разлить воду поровну в ведро и большую кастрюлю.

Ситуацию в каждый момент можно описать тремя числами (x,y,z), где x - количество литров воды в ведре, y - в большой кастрюле, z - в меньшей. В начальный момент ситуация описывалась тройкой чисел (8,0,0), от нее мы можем перейти в одну из двух ситуаций: (3,5,0), если наполним водой большую кастрюлю, или (5,0,3), если наполним меньшую кастрюлю.

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

Подобным образом можно составить граф любой позиционной игры: шахмат, шашек, «крестиков-ноликов», где позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки.

Однако для шахмат и шашек такой граф будет очень большим, поскольку различные позиции в этих играх исчисляются миллионами. А вот для игры в «крестики-нолики» на доске 3×3 соответствующий граф нарисовать не так уж трудно, хотя и он будет содержать несколько десятков (но не миллионов) вершин.

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

Впервые основы теории графов появились в работе Л. Эйлера, где он описывал решения головоломок и математических развлекательных задач. Широкое развитие теория графов получила с 50-х гг. XX в. в связи со становлением кибернетики и развитием вычислительной техники.

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

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

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

Рис. 3

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

Хроматическим числом графа называется наименьшее количество красок, с помощью которых можно так раскрасить вершины графа, что любые две вершины, соединенные ребром, окрашиваются при этом в разные цвета. Долгое время математики не могли решить такую проблему: достаточно ли четырех красок, для того чтобы раскрасить произвольную географическую карту так, чтобы любые две страны, имеющие общую границу, были окрашены разными красками? Если изобразить страны точками – вершинами графа, соединив ребрами те вершины, для которых соответствующие им страны граничат (рис. 4), то задача сведется к следующей: верно ли, что хроматическое число любого графа, расположенного на плоскости не больше четырех? Положительный ответ на этот вопрос был лишь недавно получен с помощью ЭВМ.

Рис. 4

ГРУППА

Группа – одно из основных понятий математики, применяемое в алгебре, геометрии, физике и других науках.

С точки зрения диалектической теории познания понятие группы является абстракцией второй ступени. Математические абстракции первой ступени можно назвать слепками с объектов и процессов реального мира, т.е. для них имеются «прототипы» в окружающей нас действительности. Например, человек многократно наблюдал множества, содержащие два элемента: две руки, два глаза и т.д. Постепенно, путем отвлечения от конкретных свойств элементов, входящих в эти множества, возникает новое понятие – число 2.

Математические абстракции первой ступени возникли в глубокой древности. Так, Евклид, который жил более двух тысяч лет назад, использовал уже сформированные понятия о числах и действиях над ними, о геометрических линиях, поверхностях и телах. У Архимеда мы находим представление о векторном понимании механических величин (силы, скорости) и их сложении по правилу параллелограмма.

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