Ситуацию в каждый момент можно описать тремя числами (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.
Математические абстракции первой ступени возникли в глубокой древности. Так, Евклид, который жил более двух тысяч лет назад, использовал уже сформированные понятия о числах и действиях над ними, о геометрических линиях, поверхностях и телах. У Архимеда мы находим представление о векторном понимании механических величин (силы, скорости) и их сложении по правилу параллелограмма.