35. Hause R., Nelson L., Rado T. (1965), Computer studies of a certain class of linear integer programs. Recent Advances in Optimization Techniques, Lavi and Vogel, Eds., Wiley, New York.

36. Jardine N., Sibson R. (1971), Mathematical taxonomy, Wiley, London.

37. Jensen P. A. (1971), Optimal networks partitioning. Ops. Res., 19, p. 916.

38. Капилина P. И., Шнейдер Б. Н. (1970), Задача о внутренней устойчивости и методы ее решения с помощью ЭВМ, в сб. Труды научной и технической конференции по итогам научных исследований за 1968 - 1969 гг., М., Издательство Московского Энергетического института.

39. Кагр R. М. (1972), Reducibility of combinatorial problems, Complexity of computer computations. Miller and Thatcher, Eds., Plenum Press, New York, p. 85. [Русский перевод см. Кибернетический сборник . Новая серия, 12, стр. 16-38.]

40. Lawler Е. L. (1966), Covering problems: Duality relations and a new method of solution, /. of SIAM {Appl. Math.), 14, p. 1115.

41. Lemke C. E., Salkin H. M., Spielberg K. (1971), Set covering by single branch enumeration with linear programming subproblems. Ops. Res., 19, p. 998.

42. Lovsaz L. (1966), On covering of graphs. Int. Symp. on theory of graphs, Dunod, Paris, p. 231.

43. Mayoh B. H., (1967), Simplification of logical expressions, /. of SIAM (Appl. Math.), 15, p. 898.

44. McCluskey E. J.Jr. (1956), Minimization of boolean functions. Bell. Syst. Tech. J., 35, 1417.

45. Michadu P. (1972), Exact implicit enumeration method for solving the set partitioning problem, IBM J. of Res. and Dev., 16, p. 573.

46. Moon J. W., Moser L. (1965), On cliques in graphs, Israel J. of Mathematics, p. 23.

47. Pierce J. F. (1967), On the truck dispatching problem - Part I, IBM Scientific Centre Technical Report 320-2018.

48. Pierce J. F. (1968), Application of combinatorial programming to a class of all-zero-one integer programming problems, Man. Sci., 15, p. 191.

49. Pierce J. F., Lasky J. S. (1973), Improved combinatorial programming algorithms for a class of all-zero-one integer programming problems, Man. Sci., 19, p. 528.

50. Pyne J. В., McCluskey E. J.Jr. (1961), An essay on prime implicant tables, /. of SIAM (Appl. Math.), 9, p. 604.

51. Quine W. V. (1952), The problem of simplifying truth functions, American Mathematical Monthly, 59, p. 521.

12. Roth R. (1969), Computer solutions to minimum-cover problems, Ops. Res., 17, p. 455.

53. Roy B. (1972), An algorithm for a general constrained set covering problem. Computing and Graph Theory, Read, Ed. Academic Press, New York.

54. Roy B. (1969, 1970), Algebre moderne et theorie des graphes, Vol. 1 and Vol. 2, Dunod, Paris.

55. Rubin J. (1971), A technique for the solution of massive set covering problems, with application to airline crew scheduling, IBM Philadelphia Scientific Center Technical Rept., No 320-3004.

56. Rutman R. A. (1964), An algorithm for placement of inter-connected elements based on minimum wire length, Proc. of A FTPS Conf., 20, p. 477.

57. Salkin H. M., Koncal R. (1970), A pseudo dual all-integer algorithm for the set covering problem. Dept. of 0. R. Technical Memo, No 204, Case Western Reserve University.

58. Salkin H. M., Koncal R. (1971), A dual algorithm for the set covering problem, Dept. of 0. R. Technical Memo, No 250, Case Western Reserve University.

59. Salveson М. Е. (1955), The assembly line balancing problem, /. of Industrial Engineering, 6, p. 18.

60. Selby G. (1970), The use of topological methods in computer-aided circuit layout. Ph. D. Thesis, University of London.

61. Shannon C. Б. (1956), The zero-error capacity of a noisy channel. Trans. Inst. Elect. Eng., 3, p. 3. [Русский перевод см. Шеннон К., Работы по теории информации и кибернетике, М.,ИЛ, 1963.]

62. Шнейдер Б. Н. (1970), Приложение алгебры множеств к решению задач из теории графов.

63. Starobinets S. М. (1973), On an algorithm for finding the greatest internally stable sets of a graph, Engineering Cibernetics 73, English Translation by Plenum Press, p. 873.

64. Steiger F. (1965), Optimization of Swiss Airs crew scheduling by an integer linear programming model, Swissair Report O.R.SDK 3.3.911.

65. Steiger F., Neiderer M. (1968), Scheduling air crews by integer programming, presented at IFIP Congress 68, Edinburgh.

66. Steinberg L. (1961), The background wiring problem; a placement algorithm, /. of SIAM (Review), 3, p. 37.

67. Thiriez H. (1971), The set covering problem - a group theoretic approach. Rev. Frangaise dInformatique et de Recherche Operationnelle, V-3, p. 83.

68. Wells M. В., Application of a finite set covering theorem to the simplification of boolean function expressions. Information Processing 62, Popple-well, Ed., North Holland, Amsterdam.

г лава 4 РАСКРАСКИ

1. Введение

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

Граф G называют г-хроматическим, если его вершины могут быть раскрашены с использованием г цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число г, такое, что граф G является г-хроматическим, называется хроматическим числом графа G и обозначается у (G). Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на г подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных верпшн.

Вообще говоря, хроматическое число графа (так же как числа независимости и доминирования, рассмотренные в предшествующей главе) нельзя найти, зная только числа вершин и ребер графа. Недостаточно также знать степень каждой вершины, чтобы вычислить хроматическое число графа. В этом можно убедиться, рассматривая графы, приведенные на рис. 4.1(a) и 4.1(6). Эти графы имеют по 71=12 вершин, те = 16 ребер и одинаковые распределения степеней вершин dj. Однако хроматические числа данных графов равны 4 и 2 соответственно. При известных величинах п (число вершин), т (число ребер) и d, . . ., dn (степени вершин графа) можно получить верхнюю и нижнюю оценки для хроматического числа графа. Этим оценкам посвящен следующий раздел.

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