Ориентированные графы. Построение минимального остовного дерева сети

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

Ребро графа G(X, Т) называется ориентированным, или дугой, если одну вершину считают началом, а другую концом этого ребра

На рисунке дугу обозначают стрелкой. Дугу с началом в вершине x_i и концом в вершине x_j записывают (x_i, x_j).

Определение2.7. Граф, все ребра которого ориентированы, называется ориентированным графом.

Число дуг, исходящих из вершины ориентированного графа x_i, называется полустепенью исхода вершины x_i, число дуг, входящих в вершину x_i, − полустепенью захода вершины x_i.

Вершина x_i называется источником, если ее полустепень захода равна нулю, и стоком, если ее полустепень исхода равна нулю.

Рассмотрим ориентированный граф на рисунке 2.25. Полустепень исхода вершины х₁ равна 1, полустепень захода этой вершины – 2, степень вершины х₁ равна 3. Вершина х₃ является источником, вершина х₂ – стоком.

Рис. 2.25	Рис. 2.26

Определение 2.8. Последовательность дуг (x₁, x₂), (x₂, x₃), …, (x_k-1, x_k), в которой конец предыдущей дуги совпадает с началом следующей, называется маршрутом от x₁до x_k.

Маршрут, в котором первая и последняя вершины совпадают, называется замкнутым.

Пример 2.6. Рассмотрим ориентированный граф (рис. 2.26). Он имеет мно­жество маршрутов, например: (х₁, х₂), (х₂, х₆), (х₆, х₇), (х₇, х₃), (x₃, х₂), (х₂, x₆), (х₆, х₅), (х₅, х₁). Этот маршрут является замкнутым.

Маршрут, в котором все вершины различны, называется путем от x₁до x_k.

Если существует путь из вершины x_iв вершину x_j, то говорят, что x_j достижима из x_i.

Замкнутый путь называется контуром.

Рассмотрим ориентированный граф (рис. 2.27). Он имеет пути (х₄, х₁), (х₁, х₂), (х₂, х₃) и (x₁, х₂); (х₂, х₄), (х₄, х₃), а также один контур (х₄, x₁), (х₁, х₂), (х₂, х₄). Вершина х_з достижима из вершины х₁.

Полным ориентированным графом называется граф G(X, Т), в котором каждая пара вершин соединена в точности одной дугой.

Ориентированный граф, изображенный на рис.2.28, является полным.

Рис. 2.27	Рис. 2.28

Ориентированный граф G(X.T) можно задать с помощью матрицы инци­дентности. Пусть x₁, x₂,..., х_n — вершины графа, 1₁, 1₂, …, l_m — дуги графа.

Определение 2.9. Матрицей инцидентности ориентированного графа G(X, T) называется матрица В_{n х m}, у которой элемент b_ij равен 1, если дуга l_j исходит из вершины x_i, равен (−1), если дуга l_j входит в вершину x_i; равен 0, если дуга l_j и вершина x_i не инцидентны.

Пример 2.7. Для ориентированного графа, изображенного на рис. 2.29,
матрица инцидентности имеет следующий вид:

1 0 0 -1 0 -1 1 0 0 1 0 -1 -1 0 0 0 0 1 1 -1 4 5	x1 l1 x2
Рис. 2.29

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

Определение 2.10. Остовным деревом сети называется дерево, содержа­щее все узлы сети.

Пример 2.8. Рассмотрим сеть с пятью узлами (рис. 2.30, а). Для этой сети можно построить множество остовных деревьев. Некоторые примеры таких остовных деревьев изображены на рис. 2.30, б-е.

а	б
в	г
д	е

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

Рассмотрим процедуру построения минимального остовного дерева. Вве­дем обозначения:

X = { х₁, х_{2, …,} х_n} — множество узлов сети;

C_k— связное множество узлов сети, соединенных алгоритмом после выполнения k-ой итерации;

— множество узлов сети, не соединенное с узлами множества C_k после выполнения k-ой итерации;

Минимальное остовное дерево строят по следующему алгоритму:

1) выбирают произвольный узел сети х_i: С₁ = х_i, = X \ {х};

2) выбирают из оставшихся узлов узел Xj, ближайший к множеству узлов
С₁: С₂ = Xi,.x_j, = X \ {x_i, Xj};

3) выбирают из множества узел, ближайший к узлам множества С₂,
включают его в множество С₂ и исключают из множества .

За конечное число шагов будут обработаны все узлы сети и построено минимальное остовное дерево: С_n = X, = .

а	б
в	г
д	е
	ж
	Рис. 2.31

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

Проведем пошаговое построение минимального остовного дерева для данной сети. Со = , = { х₁, х₂, х₃, х₄, х₅, х₆}. Начнем с узла x₁.

Итерация 1 (рис. 2.31, б):

С₁ = {х₁}. = {х_2, х₃, х₄, х₅, х₆}, min(1,5,7,9) = 1.

ближайший узел к множеству С₁ — узел х₂. Добавляем его к остовному дереву с ребром длиной 1 км.

Итерация 2 (рис. 2.31, в):

С₂ = {х₁, х₂}. = {х₃, х₄, х₅, х₆}. min(3,4,5,6,7,9) = 3.

ближайший узел к множеству С₂ — узел х₅. Добавляем его к остовному дереву с ребром длиной 3 км.

Итерация 3 (рис. 2.31, г):

С₃ = {х₁, х₂, х₅}. = {х₃, х₄, х₆}. min(4,5,6,7,8) = 4.

ближайший узел к множеству Сз — узел х₄. Добавляем его к остовному дереву с ребром длиной 4 км.

Итерация 4 (рис. 2.31, д):

С₄ = {x₁, х₂, х₄, х₅}, = {х_3, х₆}, min(3,5,6) = 3.

ближайший узел к множеству С₄ — узел х₆. Добавляем его к остовному дереву с ребром длиной 3 км.

Итерация 5 (рис. 2.31, е):

С₅ = {x₁, х₂, х₄, х₅, х₆}, = {х₃}, min(5,6,10) = 5.

Ближайший узел к множеству С₅ — узел х_3.Добавляем его к остовному дереву с ребром длиной 5 км. При этом возможно два альтернативных соединения (х₁, х₃) и (х₄, х₃) длиной 5 км. Процесс построения минимального остовного дерева завершен (рис. 32, ж).

Итак, С₆ = X = { x₁, х₂, х₃, х₄, х₅, х₆}, = . Минимальная длина телевизионного кабеля составит 1 + 3 + 4 + 3 + 5 = 16 км.

Задача нахождения кратчайшего пути. Дерево решений

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

Введем следующие обозначения:

x₁ — исходный узел;

х_n — узел назначения;

d_ij — расстояние на сети между смежными узлами x_i и x_j;

U_j — кратчайшее расстояние от узла x_i до узла x_j, U₁ = 0.

Алгоритм нахождения кратчайшего пути состоит в последовательном на­хождении значений U_j для каждого узла: от исходного до узла назначения. Значение U_j для каждого узла рассчитывается по формуле

U_j = min _i {U_i + d_ij},

где U_i — кратчайшее расстояние до предыдущего узла x_i; d_ij — расстояние между текущим узлом x_j и предыдущим узлом х_i.

Процедура заканчивается, когда получено значение U_n для узла назначения.

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

U₁ = 0;

U₂ = U₁ + d₁₂ = 0 + 2 = 2;

U₃ = U₁ + d₁₃ = 0 + 4 = 4;

U₄ = min {U₁ + d₁₄, U₂ + d₂₄, U₃ + d₃₄} = min {0 + 10, 2 + 11, 4 + 3} = 7;

U₅ = min {U₂ + d₂₅, U₄ + d₄₅} = min {2 + 5, 7 + 8} = 7;

U₆ = min {U₃ + d₃₆, U₄ + d₄₆ } = min {4 + 1, 7 + 7} = 5;

U₆ = min {U₅ + d₅₇, U₆ + d₆₇ } = min {7 + 6, 5+ 9} = 13.

Рис.2.32

Для определения кратчайшего расстояния между узлами x₁и x₇ получена обратная последовательность узлов и дуг:

x₇ → d₅₇ → x₅ → d₂₅ → x₂ → d₁₂→ x₁.

Минимальное расстояние между узлами x₁ и x₇ равно 13, а соответствующий маршрут — {x₁, x₂, х₅, х₇}.

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

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

Рис. 2.33

Решение.

U₁ = 0

U₂ = U₁ + d₁₂ = 0 + 4 = 4;

U₃ = min {U₁ + d₁₃, U₂ + d₂₃} = min {0 + 5,4, 4 + 4,3} = 5,4;

U₄ = min {U₁ + d₁₄, U₂ + d₂₄, U₃ + d₃₄} = min {0 + 9,8, 4 + 6,2, 5,4 + 4,8} = 9,8;

U₅ = min {U₁ + d₁₅, U₂ + d₂₅, U₃ + d₃₅, U₄ + d₄₅} =

min {0 + 13,7, 4 + 8,1, 5,4 + 7,1, 9,8+4,9} = 12,1.

Таким образом, кратчайший путь 1 — 2 — 5, стоимость — 12,1 тыс. ден. ед. Это означает, что каждый автомобиль заменяется через два года, а через пять лет списывается.

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

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

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

Рассмотрим задачу с применением дерева решений.

Пример 2.11. Компания может принять решение о строительстве среднего и малого предприятий. Малое предприятие впоследствии можно расширить. Решение определяется будущим спросом на продукцию, которую предполага­ется выпускать на сооружаемом предприятии.

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

Анализ рыночной ситуации показывает, что вероятности высокого и низкого уровней спроса равны соответственно 0,7 и 0,3. Строительство среднего предприятия обойдется в 4 млн. руб., малого — в 1 млн руб. Затраты на расширение малого предприятия через два года оцениваются в 3,5 млн руб.

Ожидаемые ежегодные доходы для каждой из возможных альтернатив:

• среднее предприятие при высоком (низком) спросе дает 0,9 (0,2) млн руб.;

• малое предприятие при высоком (низком) спросе дает 0,2 (0,1) млн руб.;

• расширенное предприятие при высоком (низком) спросе дает 0,8 (0,1)
млн руб.

Определить оптимальную стратегию компании в отношении строительства предприятий.

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

Задача представлена в виде дерева решений (рис. 2.34). Предполагается, что спрос может оказаться высоким и низким. Дерево имеет два типа вершин: «решающие» вершины обозначены квадратами, а «случайные» — кругами.

В вершине 1, являющейся «решающей», необходимо выбрать размер пред­приятия. Вершины 2 и 3 являются «случайными». Компания будет рассматривать вопрос о расширении малого предприятия только в том случае, если спрос по истечении первых двух лет установится на высоком уровне. Поэтому в вер­шине 4 принимается решение о расширении или не расширении предприятия.
Вершины 5 и 6 «случайные».

2 года 8 лет

Рис.2.34

Проведем расчеты для каждой из альтернатив. Вычисления начнем со 2-го этапа. Для последних восьми лет альтернативы, относящиеся к вершине 4, оцениваются:

ДР = (0,8 · 0,7 + 0,1 · 0.3) ·8-3,5 = 1,22 (млн руб.);

ДБР = (0,2 · 0,7 + 0.1 · 0,3) · 8 = 1,36 (млн руб.),

где ДР—доход в случае расширения предприятия; ДБР—доход без расширения предприятия.

Таким образом, в вершине 4 выгоднее не проводить расширение, тогда доход составит 1,36 млн руб.

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

Для вершины 1:

ДС = (0,9 · 0,7 + 0,2 · 0,3) · 10 - 4,0 = 2,9 (млн руб.);

ДМ = 1,36 + 0,2 · 0,7 · 2 + 0,1 · 0,3 · 10 - 1,0 = 0,94 (млн руб.),

где ДС — доход среднего предприятия; ДМ — доход малого предприятия.

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

Оценим степень риска каждого решения по величине среднеквадратического отклонения:

σ₁= = 2,23 (млн руб.);

σ₂ = = 0,77 (млн руб.).

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