Дискретно-непрерывная математика (стр. 67 )

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

Дополнительные сведения

Метод ПЕРТ показывает, что теория графов явля­ется мощным инструментом решения задач планирова­ния реализации проектов, С графотеоретической точки зрения ПЕРТ оперирует с временными характеристика­ми, определенными на графе. Такие временные харак­теристики позволяют найти график выполнения опера­ций, распределение событий во времени и дерево длин­нейших путей (критический путь).

Успех метода ПЕРТ содействовал применению тео­рии графов для решения других задач управления про­ектами. Как указывалось выше, первоначальный метод ПЕРТ был основан на определении временных парамет­ров на графе. Bпоследствии были введены на графе и характеристики другого типа, напри­мер, такие, как стоимость, ресурсы. (Под ресурсами имеются в виду люди, материалы, механизмы.) Помимо чисел, каждой дуге графа можно сопоставить такие функции, как, например, время-стоимость, или время-ресурсы. Эти функции показывают, как изменяются сто­имость или ресурсы операции в зависимости от ее дли­тельности. Задание функции стоимости на каждой дуге графа проекта позволяет найти кривую стоимость-время для всего проекта. Для вычисления таких кривых предложено множество алгоритмов. Эти алгоритмы мож­но использовать также для нахождения такого графика выполнения проекта, который обеспечивает минималь­ную стоимость выполнения при заданном времени.

Алгоритмы Келли (1961), Фалкерсона (1962), Гросмана и Лерха (1961), оптимизирующие проект по сто­имости, иллюстрируют возможности теории графов при построении моделей задач, разработке вычислительных алгоритмов и проведении простых доказательств. Труд­ность восприятия названных работ обратно пропорциoнальна степени использования теории графов. Доказа­тельства Келли, основанные на методике параметриче­ского линейного программирования Гасса и Саати (1955), оказываются очень громоздкими. Метод Фалкерсона, заключающийся в сведении исходной задачи пара­метрического линейного программирования к задаче оп­ределения потока в сети, проще метода Келли. Нако­нец полностью графотеоретический подход Гроссмана и Лерха представляется почти очевидным, но вместе с тем он является достаточно строгим. Аналогичный подход использован Берманом (1964) при нелинейных функци­ях стоимости и Фейем (1964) для планирования много­темных разработок.

Pешенo много задач на графах при заданных функциях ресурсов. В этом случае типичная задача состо­ит в том, чтобы найти такое распределение ресурсов, при котором выдерживаются все требуемые графики выполнения проектов и количество ресурсов, необходи­мое для их выполнения, никогда не превышает имею­щегося на данном интервале времени. Основные допущения, лежащие в основе метода ПЕРТ, были исследованы Мак-Криммом, кото­рый показал, что одна из проблем обусловлена задани­ем длительности операций не в виде действительных чисел, а в виде распределений вероятности. Для преодо­ления осложнений, вызванных стохастическими перемен­ными, Фей и Ван Слейк предложили ме­тод статистического моделирования сетей.

КОМБИНАТОРНЫЕ ЗАДАЧИ

5.5. Примеры комбинаторных задач в теории графов

Ниже будут кратко рассмотрены комбинаторные задачи, возникающие в теории графов. Так как некото­рые методы, применяемые в комбинаторике, являются сложными и их рассмотрение выходит за рамки данной книги, мы удовлетворимся одной или двумя задачами.

При решении задач перечисления следует различать помеченный и непомеченный или свободный (топологи­ческий) граф.

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

Можно, наоборот, рассматривать графы с заданным числом непомеченных вершин и заданным числом поме­ченных ребер. Так как помеченные графы могут разли­чаться, несмотря на топологическую эквивалентность, вычисления для них оказываются более простыми. Дей­ствительно, здесь нет необходимости определять число эквивалентных графов, поэтому общее число вычислений уменьшается. Во многих случаях возникает задача определения числа графов, обладающих определенным свойством, например, содержащих циклы длины 3.

Число помеченных графов (не обязательно связных) с п помеченными вершинами и k непомеченными ребра­ми, в которых каждая пара вершин связана не более чем одним ребром, равно

Для того чтобы получить это число, последовательно выбираем по k различных ребер из п(п—1)/2 ребер полного n-вершинного графа. Если взять 4 вершины и 4 ребра, то су­ществует 15 возможных пометок на двух топологиче­ски различных графах. На рис. 5.8 показано число пометок для двух топологически неэквивалентных гра­фов с четырьмя вершинами и тремя, четырьмя, пятью и шестью ребрами

Рис. 5.8.

Многие задачи перечисления в теории графов яв­ляются абстракциями физических задач (например, за­дач статистической механики). Графическая формули­ровка таких задач облегчает вычислительный процесс. Некоторые из используемых при этом понятий связаны с деревьями специального типа. Граф без точек сочле­нения называется звездой, и следовательно, связный граф можно представить как объединение звезд, свя­занных в точках сочленения. Из обычного определения дерева следует, что дерево есть граф с точками сочле­нения, составляющие звезды которого состоят из един­ственного ребра. Если составляющие звезды являются многоугольниками, то граф называется деревом Хусими. Граф, показанный на рис. 5.9, становится деревом Хусими, если две его точки сочленения соединить второй цепью.

Pис. 5.9

Если звезды, составляющие граф, более сложны, то граф называется звездчатым деревом (деревом звезд). Если все звезды изоморфны, то имеем чистое звездча­тое дерево, в противном случае граф называется сме­шанным звездчатым деревом. Когда типы звезд не ого­вариваются, мы имеем просто связный граф. Дерево, ребра которого помечены значками плюс или минус, на­зывается знаковым деревом.

Многие комбинаторные задачи теории графов при­водят к интересным формулам. Например, с помощью довольно сложных выкладок можно показать, что число графов с п помеченными вершинами, состоящих из k непересекающихся деревьев, дается выражением

В процессе этих выкладок можно определить число деревьев полного графа с п помеченными вершинами. Кэли впервые доказал, что зто число равно пп-2. При­ведем интересное доказательство этого факта по индук­ции.

Теорема 5.4. Число деревьев полного графа с п по­меченными вершинами равно пп-2.

Доказательство. Для того чтобы избежать лиш­них выкладок, укажем сразу следующее известное в анализе тождество:

Теорема, очевидно, справедлива для одновершинного графа, так как

11-2=1. Предположим, что теорема справедлива для полного графа с числом вершин, мень­шим п, и докажем, что она справедлива для

n-вершинного полного графа. Обозначим через Тп число деревьев полного графа с п вершинами. Разделим п вершин на два множества, одно из i элементов и второе из п—i элементов, где i может быть любым из чисел 1, 2, ... .... п—1. По индуктивному предположению, число де­ревьев первого подграфа равно ii-2, а второго — n—1)п-i-2. Исследуем все способы связи дерева первого подграфа с деревом второго подграфа, при которых образуется дерево полного графа. Так как такая связь может быть образована между любой из i вершин пер­вого подграфа и любой из (п—i) вершин второго под­графа, то общее число возможных связей i(n—i). Та­ким образом, число деревьев в полном графе, получае­мое при данном выборе i, равно

Однако i вершин можно выбрать среди п вершин

способами, и следовательно, если мы умножим получен­ное выше число деревьев для одного разбиения на чис­ло всевозможных разбиений при данном i и просумми­руем по i, то получим

Остается рассмотреть вопрос дублирования. Некото­рые деревья исходного графа могут входить в послед­нюю сумму более одного раза. Действительно, так как существует (п—1) способ выбора подграфа с i верши­нами, то по мере увеличения i и приближения i к (n—1) величина (п—i) уменьшается до 1. Таким образом, ро­ли подграфов с i и (п—i) вершинами взаимно меняют­ся. В результате оказывается, что существует (n—1) пар подграфов с (1, п—1), (2, п—2)..... (i, п—i), ...