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

1. Верж К (1962), Теория графов и ее применения, ИЛ, М.

2. Bendy J. А. (1969), Bounds for the chromatic number of a graph, /. of Combinatorial Theory, 7, p. 96.

3. Brooks R. L. (1941), On colouring the nodes of a network, Proc. Cambridge Philosophical Soc, 37, p. 194.

4. Brown J. R. (1972), Chromatic scheduling and the chromatic number problem, Man. Sci., 19, p. 456.

5. Christofides N. (1971), An algorithm for the chromatic number of a graph. The Computer J., 14, p. 38.

6. Eilon S., Christofides N. (1971), The loading problem, Man. 5ci. 17, p. 259.

7. Even S. (1973), Algorithmic combinatorics, Macmillan, New York.

8. Geller D. P. (1970), Problem 5713, American Mathematical Monthly, 77, p. 85.

9. Gillian R. J. (1970, The chromatic number of a graph, M. Sc. Thesis, Imperial College, London University.

10. Gilmore P. C, Gomory R. E. (1967), The theory and computation of knapsack functions, Ops. Res., 15, p. 1045.

11. Graver J. E., Yackel J. K. (1968), Some graph theoretic results associated with Ramseys theorem, /. of Combinatorial Theory, 4, p. 125.

12. Harary F. (1969), Graph Theory, Addison-Wessley, Reading, Massachusetts [Русский перевод: Харари Ф. (1973), Теория графов, М. Мир .]

13. Heawood Р. J. (1890), Map-colour theorems. Quart. J. of Mathematics, Oxford Series, 24, p. 322.

14. Lin C. L. (1968), Introduction to combinatorial mathematics, McGraw-Hill, New York.

15. Matula D. W. (1968), A min-max theorem for graphs with application to colouring, /. of SIAM (Review), 10, p. 481.

16. Matula D. W., Marble G., Isaacson J. D. (1972), Graph colouring algorithms. Graph Theory and Computing, Read, Ed., Academic Press, New York. p. 109.

17. Mitchem J. (to appear), On various algorithms for estimating to the chromatic number.

18. Myers B. R., Lin R. (1972), A lower bound on the chromatic number of a graph. Networks, 1, p. 273.

19. Nordhous E. A., Gaddum J. W. (1956), On complementary graphs, Л тгггсап Mathematical Monthly, 63, p. 175.

20. Ore 0. (1967), The four colour problem, Academic Press, New York.

21. Szekeres G., Wilf H. S. (1968), An inequality for the chromatic number of a graph, /. of Combinatorial Theory, 4, p. 1.

22. Tutte W. T. (B. Descartes) (1954), Solution of advanced problem № 452G, American Mathematical Monthly, 61, p. 352.

23. Welsh D. J. A., Powell M. B. (1967), An upper bound on the chromatic number of a graph and its application to timetabling problems. The Computer J., 10, p. 85.

24. Williams M. R. (1968), A graph theory model for the solution of timetables. Ph. D. Thesis, Iniversuty of Glasgow.

25. Wood D. C. (1969), A technique for colouring a graph applicable to large scale timetabling problems. The Computer J., 12, p. 317.

26. Зыков A. A. (1949), 0 некоторых свойствах линейных комплексов, Матем сб., 24(66), 163 - 188.

Глава 5 РАЗМЕЩЕНИЕ ЦЕНТРОВ

1. Введение

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

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

Целью этой главы является рассмотрение минимаксной задачи размещения для взвешенных графов с весами c,j-, соответствующими дугам (и представляющими длины) и другими весами Vj, связанными с вершинами (и представляющими, скажем, размеры или важность объектов). Приводятся алгоритмы определения оптимального размещения центров в таких графах и результаты вычислений для графов средних размеров.

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

2. Разделения

Для любой вершины Xi графа G = (X, Г) пусть Rl (xi) есть множество тех вершин Xj графа G, которые достижимы из вершины Xi с помощью путей со взвешенными длинами Vjd (Xi, xj), не превосходящими величины К. Через Rx (xi) будет обозначаться мно-

Рис. 5.1.

жество тех вершин Xj- графа G, из которых вершина Xi может быть достигнута с использованием путей, имеющих взвешенные длины Vjd (xj, Xi)K. Таким образом.

RliXi) {X, 1 Vjd (Xi, Xj) < К, Xj e X) Ri (Xi) = {xj 1 Vjd (xj, Xi) < K, Xj e X}.

(5.1)