чение г будет тогда верхней границей кликового числа. Показать, что описанный выше алгоритм является корректным, и применить его к графу G - дополнению графа G, приведенного на рис. .3.7. Результат сравнить со значением а IG], найденным в задаче 2.

6. Для передачи информации используется п символов (букв) из множества X = {xi, . . ., х„}. Рассмотрим граф G = {X, А), в котором (xi, Xj) 6 А тогда и только тогда, когда символ может быть спутан с символом xj на приемном конце канала связи. Символы используются в блоках - /с-буквенных словах . Показать, что число, равное наибольшему числу слов, которые можно использовать для безошибочной передачи информации, совпадает с числом независимости а графа G = G X G X . . . X G (к раз), где произведение G X G двух графов G = (X, А') и G = (Х , А ) есть граф Н = {Y, В), у которого

Y = {xiXj\xiX,xjeX }

и

в = {{XiXj, XftX,) I Xj = Xft и {xj, X,) e A ,

или Xj=xi и {Xi, xit)A ,

или {xi,xit)A и {xj, xi)A }

(cm. [61]).

7. Показать, что для любых двух графов G и G справедливо неравенство

a[G xG ]>a[G]-a[G ].

8. (i) Пусть G - неориентированный граф. Обосновать неравенство а [G] р [G], показав, что каждое максимальное независимое множество есть доминирующее множество.

(ii) Приведите пример, показывающий, что наименьшее доминирующее множество может не быть независимым.

9. Показать, что на шахматной доске кх к при 2 к 4 невозможно расставить к ферзей так, чтобы они не атаковали друг друга. Найти решение для к = 5.

10. Мун и Мозер [46] доказали, что наибольшее число клик (обозначим его / (п)), которые могут встретиться в графе с п вершинами, дается соотношениями:

3 /% если n = 0(mod3),

4,3(п-4)/з^ если n=l(mod3),

2.з(п-2,/з^ если n = 2(mod3). Показать, что оценка / (п) достигается только для следующих графов G:

а) Если ге = О (mod 3), то граф G состоит из ге/3 компопепт н каждая компопепта является треугольником.

б) Если ге = 1 (mod 3), то либо граф G имеет (ге - 4)/3--1 компонент, причем одна из них - цикл С^, а другие - треугольники, либо в графе G два отдельных ребра и (ге - 4)/3 отдельных треугольников.

в) Если ге = 2 (mod 3), то граф G состоит из одного отдельного ребра и (ге - 2)/3 отдельных треугольников.

Проверить приведенное выше утверждение для ге = 3, 4, 5.

И. Используя упрош;ения, о которых шла речь в разд. 4.2, исключить максимально возможное число строк и столбцов из задачи о покрытии, у которой матрицы [cj] и Uij] имеют следуюш;ий вид:

(Замечание. Упрош;ение 4 применять только для случая cf = 1.)

12. Используя метод из разд. 4, решить ЗНП, полученную И8 задачи И после осуш;ествления всех необходимых упрош;ений.

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

1. АгаЬеуге J. Р., Fearnley J., Steiger F. С, Teather W. (1969), The airline crew scheduling problem: A survey. Tramp. Sci., 3, p. 140.

2. Augustson J. G., Minker J. (1970), An analysis of some graph-theoretical cluster techniques, /. of ACM, 17, p. 571.

3. Balas B. (1970), Project scheduling with resource constraints. Applications of mathematical programming techniques, Beale, Ed., English Universities Press, London.

4. Balas E., Padberg M. W. (1972a), On the set covering problem. Ops. Res., 20, p. 1152.

5. Balas E., Padberg M. W. (1972), On the set covering problem. II: An algorithm. Management Sciences Research Report No 295, Carnegie-Mellon University.

6. Balinski M. (1965), Integer programming: methods, uses, computation, Man. Sci., 12, p. 253.

7. Balinski М. L., Quandt В. Б. (1964), On an integer program for a delivery problem, Ops. Res., 12, p. 300.

8. Bellmore M., Greenberg H., Jarvis J. (1970). Multi-commodity disconnecting sets, Man. Sci., 16, p. 427.

9. Bellmore M., Ratliff H. D. (1971), Set covering and involuntary bases, Man. Sci., 18, p. 194.

10. Bellmore M., Ratliff H. D. (1971), Optimal defense of multi-commodity networks, Man. Sci., 18, p. 174.

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

12. Bonner R. Б. (1964), On some clustering techniques, IBM J. Res. and Dev., 8, p. 22.

13. Bosak J., Rosa A., Znam S. (1966), On decompositions of complete graphs into factors with given diameters. Int. Symp. on theory of graphs, Dunod, Paris, p. 37.

14. Bron C, Kerbosch J. (1973), Algorithm 457 - Finding all cliques of an undirected graph. Comm. of ACM, 16, p. 575.

15. Burstall R. M. (1967), Tree searching methods with an application to a network design problem. Machine Intelligence, Colin and Michie, Бds., Vol. 1, Oliver and Boyd, London.

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

17. Chamberlin D. D. (1971), The single assignment approach to parallel processing, Proc. of AFIPS Conf., 39, p. 263.

18. Christofides N. (1971), Zero-one programming using non-binary tree search, The Computer J., 14, p. 418.

19. Christofides N., Korman S. (in press), A computational survey of methods for the set covering problem, Man. Sci.

20. Crowston W. B. (1968), Decision network planning models. Ph. D. Thesis, Carnegie - Mellon University.

21. Day R. H. (1965), On optimal extracting from a multiple file data storage system: An application of integer programming. Ops. Res., 13, p. 482.

22. Dealer J. F. (1969), Degree constrained subgraphs, covers, codes and k-graphs. Ph. D. Thesis, Northwestern University, Evasion, Illinois.

23. Edmonds J. (1962), Covers and packings in a family of sets. Bulletin of American Mathematical Soc, 68, p. 494.

24. Eilon S., Watson-Gandy C. D. Т., Christofides N. (1971), Distribution management: Mathematical models and practical analysis. Griffin, London.

25. Freeman D. R., Jucker J. V. (1967), The line balancing problem, /. of Industrial Engineering, 18, p. 361.

26. Garfinkel R. S. (1970), Set covering; a survey, presented at XVII TIMS Conf., London.

27. Garfinkel R. S., Nemhauser G. L. (1969), The set partitioning problem: set covering with equality constraints. Ops. Res., 17, p. 848.

28. Garfinkel R. S., Nemhauser G. L. (1972), Integer Programming, Wiley, New York.

29. Garfinkel R. S. (1968), Optimal political districting. Ph. D. Thesis, The John Hopkins University.

30. Gimpel J. F. (1965), A reduction technique for prime implicant tables, IEEE Trans., EC-14, p. 535.

31. Glover F. (1971), A note on extreme point solutions and a paper by Lemke, Salkin and Spielberg, Ops. Res., 19, p. 1023.

32. Gomory R. (1963), An algorithm for integer solutions to linear programs. Recent Advances in Mathematical Programming, Graves and Wolfe, Eds., McGraw-Hill, New York.

33. Hakimi S. L., Frank H. (1969), Maximum internally stable sets of a graph, /. of Math. Anal, and Appl., 25, p. 296.

34. Hakimi S. L. (1971), Steiners problem in graphs and its implications. Networks, 1, p. 112.