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

Найдите соответствующую матрицу Р для другого разделения.

33. Требуется 41 сравнение. L(15) и N(15) равны 41 и 45 соот­ветственно.

Раздел 6

1. Пусть φ1 — поток, заданный рис. 6.2, и φ2 состоит из единич­ных потоков в каждой дуге той же сети. Тогда выходные потоки в вершинах v1 и v8 относительно потока φ1+ φ2 равны 8, 5, 3, —3, —13 и 0 соответственно. Относительно φ1- φ2 получим выходные потоки 2, 7, —3, 3, —7 и —2 соответственно. Сравните полученные значения с выходными потоками в тех же вершинах, но отдельно относительно потоков φ1 и φ2.

2. Потоки не являются согласованными. В двух дугах (v 3, v2) и (v1, v 4) оба потока не равны нулю и направлены противоположно.

3. Численный результат будет полностью зависеть от выбора потоков в упражнении 2 и от выбора ψ. Для каждой дуги про­верьте, что ψ (а) +φ1 (а) лежит между ψ (а) и ψ (a)+φ1(a)+ ψ 2(a).

4. В унитарном графе существует, например, 3 дуги из v1 в v3; 10 дуг из v5 в w2; 2 дуги из v2 в v3; 0 дуг между v5 и v6 и т. д.

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

6 цепей w1 v2 v5 w2,

2 цепи w1 v1 v2 v5 w2,

2 цепи w1 v1 v2 v3 v 5 w2.

1 цепь w1 v1 v3 v6 w2,

1 цикл v1 v3 v*4 v1

1 цикл v1 v3 v*4 v1.

6. Существует 8 разделений, представляющих интерес. Напри­мер, при W={v1, v2, v5) выражение справа в теореме 3 имеет зна­чение (4+3+2) — (1+6).

9. Например, дуга (v1, v2), нижняя граница пропускной способ­ности которой равна 1, а верхняя —3, заменяется на 3 дуги: (v0, v2), (v, v0) и (v1, v2) с пропускными способностями 1, 1 и 2 соответствен­но. Нижняя граница потока для всех трех дуг равна нулю (как у всех дуг вспомогательной сети).

11. Величина максимального потока через N' равна только 7, в то время как для насыщающего потока требуется значение 19 (сум­ма нижних границ потоков для всех дуг в исходной сети).

12. Покажите, что если такой контур существует, то поток, рав­ный сумме φ и единичного потока в контуре, является допустимым и имеет ту же общую стоимость, что и φ. С другой стороны, покажите, что если существует второй поток φ' минимальной стоимости, то каждый единичный поток по контуру в декомпозиции φ′ — φ опреде­ляет контур данного типа в графе приращений.

13. Заметьте, например, что в графе приращений самый внеш­ний контур, ориентированный по часовой стрелке, имеет общую дли­ну 4+1—2—3—1 = — 1. Здесь имеется и другой контур, ориентиро­ванный по часовой стрелке, который включает в себя все вершины, за исключением источника, и имеет длину —2.

14. Пропустите две единицы потока по цепи v, х, w при единич­ной стоимости 5. Затем пропустите одну единицу по цепи v, х, r и при единичной стоимости 7. Наконец, пропустите 2 единицы по цепи v, у, r, w при единичной стоимости 9. Общая стоимость равна 35.

15. Одно решение показано потоками, распространяющимися слева направо в следующей сети:

Приложение А

Общая схема доказательств для операций, связанных с max и min

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

Пусть ∆ — операция взятия нижней границы, а — верхней границы двух элементов (Хi, Xj) решетки. В решетке выполняются четыре двойственных свойства этих операций, рассмотренные в (4.2)— (4.9):

(А.1)-(А.2) (А.3)-(А.4) (А.5)-(А.6) (А.7) -(А.8)

К тому же, если решетка дистрибутивная, то справедливо и свойство

(А.9)- (А.10)

Если решетка с дополнениями, то справед­ливо и свойство

(А.11) (А.12)

Рассмотрим несколько примеров систематического доказательства различных формул.

Случай L = [0, 1] охватывает все нечеткие подмножества в смыс­ле Заде.

Вполне упорядоченное множество [0, 1] представляет собой дис­трибутивную решетку, но без дополнений. Следовательно, все свойст­ва (А.1)—(А.10) удовлетворяются и ∆ можно обозначить через , а — через ; нижнюю границу можно называть минимумом, а верх­нюю границу — максимумом.

Пусть мы хотим доказать равенство

(А.13)

Для этого надо проверить, что для xi, xj, xk Е

(А.14)

А так как L - дистрибутивная решетка, то это равенство справедли­во.

Рассмотрим более сложный случай и докажем свойство дистрибу­тивности:

(А.15)

Это равенство справедливо, если для

и отношений

выполняется

(А. 16),

Распишем члены уравнения (А. 16):

(A.17) (А.18)

(А.1 9)

Для упрощения записи положим

(А.20)

Тогда отношения (А.17)—(А.19) можно записать в виде

(А.21) (А.22) (А.23) Теперь в силу ассоциативности операции имеем

(А.24)

Сравнивая соотношения (А.21) и (А.24) и используя свойство дис­трибутивности

(А.25) действительно имеем

(А. 26) что и доказывает справедливость равенства (А.13).

Докажем, что закон ° отно­сительно операции пересечения не дистрибутивен:

(А.27)

Воспользуемся теми же обозначениями, что и в (А. 13). Поскольку надо доказать, что для некоторых свойство дистрибутивности не выполняется, то мы ограничимся универсальным множеством, в ко­тором α, β, γ = 1, 2 в (А.27). Имеем

(А.28)

(А.29)

Надо показать, что (А.28) и (А.29) — это разные величины; для этого запишем

(А.31)

Теперь справедливость неравенства устанавливается в результате сокращений, так как

(А.32)

Приложение Б

Разложение на максимальные подотношения подобия

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