8. Список литературы

1. Beale Е. М. L. (1959), An algorithm for solving the transportation problem when the shipping cost over each route is convex, Nav. Res. Log. Quart., 6, p. 43.

2. Bennington G. E. (1972), An efficient minimal cost flow algorithm. Report № 75, Department of Industrical Engineering, North Carolina State University at Raleigh.

3. Boldyreff A. W. (1955), Determination of the maximal steady flow of traffic through a railroad network, Ops. Res., 3, p. 443.

4. Bray J. A., Wizgall C. (1968), Algorithm 336 NETFLOW, Comm. of ACM, 11, p. 631.

5. Басакер P., Саати Т., Конечные графы и сети, М., Наука, 1974.

6. Busacker R. G., Gowen P. J. (1961), A procedure for determining a family of minimal-cost network flow patterns. Operations Research Office, Technical paper 15.

7. Clasen R. J. (1967), RS-0KF3, SHARE IBM Users group SDA 3536.

8. Dantzig G. В., Fulkerson D. R. (1956), On the max-flow min-cut theorem of networks. Linear inequalities and related systems, Ann. Math. Studies, 38, p. 215.

9. Edmonds J., Karp R. M. (1972), Theoretical improvements in algorithmic efficiency for network flow problems, /. of ACM, 19, p. 248.

10. Elias P., Feinstein A., Shannon C. E. (1956), A note on the maximum flow through a network, IRE Trans., IT-2, p. 117.

11. Ford L. R., Fulkerson D. R. (1956), Maximal flow through a network. Can. J. of Math., 18, 399.

12. Ford L. R., Fulkerson D. R.(1962), Flows in networks, Princeton University Press, Princeton.

13. Frank H., Frisch I. T. (1971), Communication, transmission and transportation networks, Addison Wesley, Reading, Massachusetts.

14. Gomory R. E., Hu T. C. (1964), Synthesis of a communication network, /. of SIAM {Appl. Math), 12, p. 348.

15. Grigoriadis M. D., White W. W. (1972), A partitioning algorithm for the multicommodity network flow problem. Math. Progr., 3, p. 157.

16. Hu T. C. (1969), Integer programming and network flows, Addison Wesley, Reading, Massachusetts.

17. Hu T. C. (1966), Minimum cost flow in convex cost networks, Nav. Res. Log. Quart., 13, p. 1.

18. Jewell W. S. (1968), Multicommodity network solutions, Theorie de graphes, Dunod, Paris, p. 183.

19. Johnson E. (1966), Networks and basic solutions. Ops. Res., 14, p. 619.

20. Klein M. (1967), A primal method for minimal cost flows with applications to the assignment and transportation problems, Man. Sci., 14, p. 205.

21. Maurras J. F. (1972), Optimization of the flow through networks with gains. Math. Prog., 3, p. 135.

22. Onaga K. (1967), Optimum flows in general communication networks, /. of the Franklin Institute, 283, p. 308.

23. Potts R. В., Oliver R. M. (1972), Flows in transportation networks. Academic Press, New York.

24. Sakarovitch M. (1966), The multicommodity maximum flow problem. Report ORC-66-25, Operations Research Centre, Univ. of California, Berkeley.

25. Siagal R. (1967), Multicommodity flows in directed networks. Report ORC-67-38, Operations Research Centre, Univ. of California, Berkeley.

26. Tomlin J. A. (1966), Minimum cost multicommodity network flows. Ops. Res., 14, p. 45.

27. Wollmer R. D. (1970), Multicommodity supply and transportation networks with resource constraints. The Rand Corporation, Report R. M.-6134-PR.

Глава 12

ПАРОСОЧЕТАНИЯ, ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ

1. Введение

Рассмотрим следующую задачу построения остовного подграфа Gp общего неориентированного графа G, степени вершин которого по отношению к подграфу Gp заданы.

Задача об остовном подграфе с предписанными степенями. Пусть G = (X, А) - неориентированный граф, ребрам uj А которого приписаны веса cj. Пусть, далее, заданы неотрицательные целые числа бг, i = 1, . . ., п. Требуется найти в G такой остовный подграф G*, что степени вершин Xi по отношению к Gp

являются заданными числами б^ (т. е. dfv = б;) и сумма весов ребер графа G максимальна (или минимальна).

Сформулированную выше задачу мы будем называть в настоящей главе общей задачей. Очевидно, что если дан граф G и числа б(, то вполне возможно, что в G не существует никакого остовного подграфа Gp, имеющего эти предписанные степени. Два необходимых (но не достаточных, см. разд. 5) условия, которым должны удовлетворять числа 6j, чтобы существовал некоторый допустимый остовный подграф, таковы:

6i<df, Vi=l, .... п (12.1)

У, bi - четна, =1

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

Паросочетанием общего неориентированного графа G = {X, А) называется подмножество М множества А ребер графа G, выбранное так, что никакие два ребра из М не являются смежными (т. е. не имеют общей вершины). Следующая задача будет называться задачей о максимальном паросочетании (ЗМП).

ЗМП: найти паросочетание М* максимального веса. Вес паро-сочетания определяется как

См= Zi

1. ВВЕДЕНИЕ 369

М* будет называться максимальным паросочетанием графа G. ЗМП можно выразить в терминах линейного программирования:

максимизировать z=Cjlj (12.2)

при условии S ijjl Vi = l, п, (12.3)

1 = 0 или 1, (12.4)

где [bij] - матрица инциденций графа G и = 1 или О в зависимости от того, входит ли ребро а] в паросочетание.

Совершенно очевидно, что ЗМП для графа G является частным случаем общей задачи. Если число вершин G четно, то требуется только добавлять kG ребра веса -оо до тех пор, пока не получится (новый) полный граф G. ЗМП становится тогда общей задачей для графа G, где все б; положены равными 1. Решением ЗМП будет решение общей задачи для (остовного) подграфа GJ, если пренебречь теми ребрами в Gp, которые имеют вес -оо. Если число вершин графа G нечетно, то к G добавляют одну изолированную вершину, после чего строится граф G, как это было описано выше.

В терминологии гл. 3 паросочетание может быть названо независимым множеством ребер , так как никакие два ребра паросочетания не являются смежными. Доминирующее множество ребер в смысле гл. 3 (т. е. множество ребер, доминирующее над всеми вершинами из G) следовало бы тогда определить как подмножество Е ребер из G, выбранное так, что каждая вершина инцидентна по крайней мере одному ребру из Е. Такое множество в литературе обычно называется покрытием, и в настоящей главе мы будем использовать этот термин. Весом покрытия Е графа G называется Cj. Теперь ЗМП соответствует задача

О минимальном покрытии (ЗПО). ЗПО: найти покрытие Е* минимального веса для графа G.

Е* будет называться минимальным покрытием графа G. Формулировка ЗПО в терминах линейного программирования такова:

минимизировать z= Cjlj (12.5)

при условии S Vi = l, п, (12.6)

IjO или 1, (12.7)

где 5j = 1 или О в зависимости от того, входит ли ребро aj в покрытие.