Энциклопедический словарь юного математика

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

В строительстве графы используются при планировании проведения работ. Граф, изображенный на рис. 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

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