Упражнения

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

S1. Положить для

S2. Положить

S3. Если то HALT, иначе выбрать такое и, что

S4. Для каждого такого с, что положить ),

Если при этом уменьшается величина то положить

S5. Положить и идти к шагу

15.2. Докажите корректность следующего алгоритма, предложенного Данцигом [15.107], для выделения кратчайших путей между всеми парами вершин во взвешенном графе, который не содержит ориентированных циклов отрицательной длины. -расстояние от где и ни одна вершина с номером, большим k, не используется в пути, вдоль которого определялось это расстояние. — длина ребра если такого ребра не существует. Кроме того, для всех .

S1. Положить

S2. Для выполнить

S3. Для выполнить

S4. Если иначе положить и идти к шагу Покажите также, как можно обнаружить циклы с отрицательной длиной при выполнении приведенного выше алгоритма.

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

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

15.5. Докажите, что если вектор длин путей удовлетворяет условию, налагаемому на характеристическую сумму, и если то вектор также удовлетворяет условию, налагаемому на характеристическую сумму,

и длины путей расположены в неубывающем порядке [d то же, что и в выражении (15.17)].

15.6. Используя результат упражнения 15.5, покажите, как построить -дерево, в котором порядок листьев слева направо совпадает с порядком величин в векторе длин путей.

15.7. Найдите минимальное дерево бинарного поиска для весов (1, 2, 3, 3, 4, 4).

15.8. Докажите, что замена шага в алгоритме 15.5 на шаг (Выбор ребра.) Выбрать ребро... Если такого ребра не существует, то идти к шагу не влияет на корректность алгоритма выделения максимального паросочетания [15.28].

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

15.10. Если — минимальные разрезы в транспортной сети N, то покажите, что также минимальные разрезы в

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

15.12. Рассмотрим транспортную сеть N, в которой каждой вершине сопоставлено неотрицательное целое число Покажите, как можно определить максимальный поток, в котором поток в каждую вершину не превышает с помощью применения помечивающего алгоритма к модифицированной сети. (Примените построение, используемое при доказательстве теоремы 15.14.)

15.13. Рассмотрим транспортную сеть N, в которой определена также и нижняя граница потока в каждом ребре.

а) Найдите необходимые достаточные условия существования потока в сети.

б) Модифицируйте помечивающий алгоритм для определения максимального потока в сети N [15.108].

15.14. Докажите, что поток в транспортной сети с нижними границами для потока в ребре существует тогда и только тогда, когда каждое ребро принадлежит ориентированному циклу или ориентированному пути из s в t или ориентированному пути из t в

15.15. Опишите метод определения местонахождения в транспортной сети N ребра, которое обладает тем свойством, что увеличение его пропускной способности приводит к увеличению максимального потока в сети

15.16. Оптимальное ветвление не обязательно является оптимальным ориентированным остовом. Покажите, как можно модифицировать алгоритм Эдмондса для выделения ориентированного остова.

15.17. а) Докажите корректность следующего алгоритма Прима [15.81] для определения минимального взвешенного остова в связном взвешенном графе . Выбрать произвольную вершину v в графе G. Среди всех ребер, входящих в v, выбрать ребро с минимальным весом. Стянем и пусть G — полученный граф. Повторить эти действия для G и продолжить до тех пор, пока не будет определено ребро Ребра образуют минимальный взвешенный остов графа

б) Сконструируйте О (-реализацию алгоритма Прима.

15.18. Докажите теорему Холла 8.13, используя теорему 15.9 о максимальном потоке и минимальном разрезе, и наоборот.

15.19. Пусть — двудольный граф, в котором существует полное паросочетание X в Y. Тогда известно, что существует такая вершина что для каждого ребра , инцидентного v, существует полное паросочетание, содержащее (упражнение 8.16). Непосредственный алгоритм определения такой вершины будет требовать для своего выполнения шагов. Попытайтесь сконструировать алгоритм с меньшей сложностью.