Маршруты, пути, деревья

Определение. Путь изv₁ в v_t+1 ворграфеD=(V,X) - последовательность вершин и дуг v₁,x₁,v₂,x₂,...,v_t,x_t,v_t+1 , где t>0, причем каждая вершина v_i Î V, а каждая дуга x_i Î X, и x_i всегда является дугой (v_i,v_i+1).

Определение. Цепьв неориентированном графеG=(V,E) - последовательность вершин и ребер v₁,e₁,v₂,e₂,...,v_t,e_t,v_t+1, где t>0, причем каждая вершина v_i Î V, а каждое ребро e_iÎE, и e_i всегда является ребром {v_i, v_i+1}.

Иногда, когда кратности дуг (рёбер) равны 1, то путь (цепь) записывают просто последовательностью вершин v₁, v₂, ..., v_t, v_t+1.

Возвратимся к рисункам 6.2-6.5 Маршрутом (путем) в графе, соединяющим вершины А и В, называется такая последовательность его ребер, в которой каждые два ребра имеют общую концевую точку, причем первое ребро выходит из вершины А, а последнее входит в вершину В (рис. 6.3). При этом маршрутами от точки А до точки В могут быть АDB или FCEDB и т.д.

Граф называется связанным, если для любых двух его вершин может быть указан маршрут, по которому из одной вершины можно попасть в другую. Графы на рис.6.2 и 6.3 – связанные, на рис.6.4 представлен несвязанный граф.

Цепью называется маршрут, не содержащий повторяющихся ребер. Вершины в цепи могут повторяться несколько раз. Например, маршрут ADCEDB на рис.6.5 является цепью, а маршрут ACDECDB цепью не является. Цепь, начальная и конечная вершины которой совпадают, называется циклом, например цепь ADECA на рис. 2.

Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если сходящееся в ней число ребер нечетно. На рис.4 вершина С - четна, вершина D – нечетна.

Степенью (порядком) вершины называется число сходящихся в ней ребер.

Конечнымграфом называется граф с конечным числом ребер.

Граф, все вершины которого четны, называется эйлеровым графом.

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

Метод определения эйлерова цикла рассмотрим на примере.

Пример 6.6. Определить эйлеров цикл для графа, представленного на рис.6.11. За начальную вершину принять вершину А.

Решение.

Прежде всего убедимся, что данный граф – эйлеров. В вершину А можно вернуться пройдя, например, по ребрам 1, 2, 3, 4, 5, 6. В построенный нами цикл входят не все ребра. Поэтому продолжим исследования. В полученном нами цикле обязательно есть вершина, из которой выходят еще не пройденные ребра. Этих ребер будет четное число. Пусть это вершина В. Построим вторую цепь из вершины В, привлекая только не пройденные ранее ребра.

Теперь, совместив первый и второй циклы, получим суммарный цикл.

Этот цикл можно пройти следующим образом. Из вершины А, проходя по ребрам 1, 2, 3, доходим до вершины В. Затем проходим по второму циклу 7, 8, 9 и возвращаемся в вершину В. Далее по ребрам 4, 5, 6 возвращаемся в вершину А.

Наконец, из вершины С строим третий цикл. Совместив его с двумя предыдущими, построим цикл 1, 2, 3, 7, 10, 11, 12, 8, 9, 4, 5, 6, в который входят все ребра графа (см. рис.6.11)

Рис.6.11

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

Если заданный граф допускает гамильтонов цикл, то он называется гамильтоновым графом.

Важный класс графов составляют так называемые деревья. Деревом называется связанный граф, который не имеет циклов (рис. 17).

Рис. 6.12

Число В вершин дерева и число Р его ребер различаются на единицу:

В=Р+1.

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

Применение дерева решений подразумевает понимание (хотя бы интуитивное) таких понятий, как "вероятность" и "ожидаемое значение (математическое ожидание) случайной величины".

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

1. Если он останавливает свой выбор на университете штата и бизнесе, то вероятность успеха (получение диплома) считается равной 0,60.

2. Если он останавливает свой выбор на университете штата и инжиниринге, то вероятность успеха считается равной 0,70.

3. Если он останавливает свой выбор на университете г. А и бизнесе, то вероятность успеха считается равной 0,90.

4. Если он останавливает свой выбор на университете г. А и инжиниринге, то вероятность успеха считается равной 0,95.

5. Средний доход за год в течение первых пяти лет у окончившего бизнес-школу университета штата при условии полной занятости равен 35 тыс. долл.

6. Средний доход за год в течение первых пяти лет у окончившего школу инжиниринга университета штата при условии полной занятости равен 30 тыс. долл.

7. Средний доход за год в течение первых пяти лет у окончившего бизнес-школу университета г. А при условии полной занятости равен 24 тыс. долл.

8. Средний доход за год в течение первых пяти лет у окончившего школу инжиниринга университета г. А при условии полной занятости равен 25 тыс. долл.

9. Если по каким-либо причинам выпускник не поступает ни в один из этих университетов, то его средний доход в течение этих пяти лет при условии полной занятости будет равен 18 тыс. долл.

Предположим, что единственным критерием при принятии выпускником окончательного решения является величина ожидаемого среднего дохода в первые пять лет его трудовой деятельности. Сделав это предположение, попробуем решить проблему выпускника, используя дерево решений (рис. 6.13).

Рис. 6.13

Поясним некоторые обозначения на рисунке:

S₁ - окончание бизнес-школы университета штата,

S₂ - либо неудача при поступлении в бизнес-школу университета штата, либо невозможность завершения обучения,

S₃ - окончание школы инжиниринга университета штата,

S₄ - либо неудача при поступлении в школу инжиниринга университета штата, либо невозможность завершения обучения,

S₅ - окончание бизнес-школы университета города А,

S₆ - либо неудача при поступлении в бизнес-школу университета города А, либо невозможность завершения обучения,

S₇ - окончание школы инжиниринга университета города А,

S₈ - либо неудача при поступлении в школу инжиниринга университета города А, либо невозможность завершения обучения,

d₁ - выбор университета штата,

d₂ - выбор университета города А,

d₃ - предпочтение отдано бизнесу,

d₄ - предпочтение отдано инжинирингу.

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

Эти два типа узлов рассчитываются по-разному.

При расчете узлов 4-7 определяются ожидаемые значения:

значение в узле 7

N₇ = (0,95 )(25000) + (0,05) (18000) = 24650 долл.,

значение в узле 6

N₆ = (0,90)(24000) + (0,10)(18000) = 23400 долл.,

значение в узле 5

N₅ = (0,70) (30000) + (0,30)(18000) = 26400 долл.,

значение в узле 4

N₄ = (0,60) (35000) + (0:40) (18000) = 28200 долл.

Значение N₃ в узле 3 определяется так:

вследствие того что N₇ > N₆, полагаем N₃ = N₇. И считаем, что выбор d₄ предпочтительнее d₃.

Тем самым, N₃ = 24650 долл.

Рис. 6.14

Значение N₂ в узле 2 определяется так:

вследствие того что N₄ > N₅, полагаем N₂ = N₄ и считаем, что выбор d₃ предпочтительнее выбора d₄.

Тем самым, N₂ = 28200 долл.

Значение N₁ в узле 1 определяется так:

вследствие того что N₂ > N₃, полагаем N₁ = N₂ и считаем, что выбор d₁ предпочтительнее выбора d₂.

Тем самым, N₁ = 28200 долл.

Наносим результаты расчетов на рис. 6.13 и принимаем окончательное решение (рис. 6.14).

В экономических приложениях граф обычно называется сетью или сетевым графом.

Глава 7. Элементы сетевого планирования и управления

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

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

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

Первый вариант этого метода был разработан в 1957 г. американскими учеными Дж. Е. Келли и М. Р. Уокером и был назван СРМ (от начальных букв выражения « Critical Path Method», означающего « Метод критического пути»). Примерно в то же время независимо от СРМ появилась система РЕRT («Program Evaluation and Review Technique», что означает «Техника обзора и оценки программ»). В результате дальнейшего развития эти системы превратились в совокупную методику построения графиков – сетевое планирование и управление.