АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОПРЕДЕЛЕНИЕ. Последовательность W = a1,

Последовательность W = a ₁,..., a_n - вершин графа G образует путь в G, если " i = 1,..., n - 1 ((a_i, a_{i+ 1}) Î U).

Прохождение пути в графе - это последовательное перемещение по вершинам графа, по ребрам, соединяющим такие вершины. О таких ребрах говорят, что они принадлежат пути и что путь проходит через эти ребра. Если W это путь в графе G, то запись E(W) используется для обозначения множества ребер, принадлежащих пути.

Частный случай пути - это пустой путь W = a, который состоит из единственной вершины a. Такой путь начинается и заканчивается в этой вершине.

Вершины a ₁ и a_n называются началом и концом пути. При этом говорят, что W ведет из a ₁ в a_n. Длиной пути W называется число ребер, проходимых при движении по W из a ₁ в a_n. То есть, если W содержит m вершин, то длина W равна
m - 1.

Путь W называется элементарным, если все вершины в нем разные. Путь W называется простым, если все ребра
из E (W) являются разными.

Путь W называется циклом, если его начало и конец совпадают.

Цикл называется элементарным (простым) циклом, если в нем все вершины за исключением первой и последней (все ребра) разные.

Если некоторый путь W в графе G не является элементарным, то он может быть преобразован в элементарный путь с теми же началом и концом.

Для этого необходимо последовательно выбирать пары одинаковых вершин, одна из которых - это внутренняя вершина пути.

Для каждой такой пары вершин a_i и a_j из W удаляется часть, состоящая из вершин a_i+1,..., a_j, т.е. путь W = a ₁,..., a_i,..., a_j,..., a_n преобразуется в путь W ₁ = a ₁,..., a_i, a_{j+ 1},..., a_n.

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

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

Аналогично можно преобразовывать произвольные циклы в элементарные циклы с теми же начальной или заключительной вершинами.

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

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

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

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

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

А - проектирование принципиальной схемы изделия;

В - определение изготовителей комплектующих;

C - разработка внешнего вида изделия;

D - заключение договоров на производство комплектующих;

E - разработка технологического процесса;

F - изучение рынка сбыта и определение объема производства;

G - реклама изделия;

H - заключение договоров на поставку изделий;

I - переналадка производственных линий;

J - выпуск пробной партии;

K - доводка технологических процессов;

L - запуск продукции в массовое производство.

Каждый из перечисленных этапов A - L требует определенного времени для своего осуществления, которое можно предварительно оценить.

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

Представим процесс реализации проекта с помощью специальногографа. Вершины этого графа соответствуют этапам реализации проекта, а ориентированные ребра - очередности выполнения этапов.

Предположим, что для рассматриваемого примера такой граф изображен на рис. 5.13:

A (2)

B (3)

C (2) G (5)

F (8) D (4) H (2)

E (6)

I (3)

J (4) K (6) L (2)

Рис. 5.13

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

Как видим, время, требуемое для реализации всего проекта, определяется самой длинной по общей продолжительности цепочкой этапов, заканчивающейся в L. В нашем случае это: F, E, I, J, K, L. Эта цепочка носит название критического пути.

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

Важной характеристикой семейства всех путей в произвольном графе является связность.

Дата добавления: 2015-09-27 | Просмотры: 452 | Нарушение авторских прав