Дискретно-непрерывная математика (стр. 100 )

(Б.54)

Этап 2 (второе правило)

(Б.55)

откуда получаем новую подматрицу

(Б.56)

(Б.57) (Б.58)

откуда получаем новую подматрицу

(Б.59)

' (Б.60)

Получаем новую подматрицу

(Б.61)

(Б.62)

откуда получаем новую подматрицу

(Б.63)

(Б 64)

Этап 3 (второе правило).

Выпишем новое покрытие

(Б.65)

(Отметим, что для частного случая симметричных булевых матриц алго­ритм можно упростить, но из дидактических соображений мы предпочли ис­пользовать первоначальный алгоритм.)

Этап 4 (первое правило).

(Б.66)

дает новую подматрицу

(Б. 67)

(Б.68)

дает новую подматрицу

(Б.69)

(Б.70)

Этап 5 (второе правило). Выпишем новое покрытие

(Б.71)

Мы исключили подматрицы [М2], [М3], [М4], [М5] как содержащие­ся в других подматрицах покрытия (Б.71).

Этап 6 (первое правило). Читатель может удостовериться в том, что новых матриц получить больше нельзя. Итак, покрытие С" (Б.71) состоит из следующих основных матриц:

(Б.72)

В этом покрытии содержатся три квадратные подматрицы [M1], [М10] и [М11]; они дают три непересекающихся подотношения. На рис. Б.3 представлены эти три подотношения, ни одно из которых не содержится в другом.

Заметим, что выявление матриц [М6] = [М8]' и [М7] = [М9]' небес­полезно, ими обеспечивается «стыковка» между подотношениями.

Другой метод. Алгоритм Пиша. Этот метод при­годен исключительно для симметрических квадратных матриц, кото­рые представляют для нас особый интерес,

Рис. Б. З

Рассмотрим верхнюю треугольную матрицу, такую, например, как на рис. Б.4.

Pис. Б.4.

Поочередно в каждой строке матрицы выделим нули. Рассматри­вая элементы матрицы как булевы переменные, свяжем булевым зна­ком суммированияиндекс строки и индексы столбцов, в которых

находятся нулевые элементы этой строки, и полученные суммы объе,-диним знаком булева произведения •, причем, если в строке нет нулей, будем считать, что сумма равна 1.

Упростим получившееся в результате произведение (используя для этого следующие правила упрощения булевых выраже­ний: x+x=x,

x•x=x, x+xy=x), приведя его к максимальной форме. Для каждого слагаемого в этой форме возьмем его дополнение. Таким образом получим максимальные подотношения, устанавливающие покрытие.

Рассмотрим пример на рис. Б.2, для которого верхнетреугольная матрица представлена на рис. Б.4.

Для строки

: ' (Б.73)

Теперь имеем

(Б.74)

Подсчитаем сумму S', в которой слагаемыми будут дополнения соответствующих слагаемых суммы S. Получим

(Б.75)

Это дает нам три подмножества

(Б.76)

которые определяют основные подматрицы, составляющие покрытие (см. [М11], [М10] и [M11] в (Б.72)).

Замечание. Если нас интересуют элементы, общие для попарно не содержащихся друг в друге отношений, то их можно получить непо­средственно, подсчитав пересечения

(Б.77)

Поиск максимальных подотношений подобия в нечетком предпорядке Любой из двух предыдущих алгоритмов можно использовать для определения этих подотношений. Достаточно рассмотреть соот­ветствующую булеву матрицу такую, что

(Б.78)

и

(Б.79)

Пример. Рассмотрим еще раз пример, приведенный на рис. 11.3, который мы повторили на рис. Б.5. Здесь выписаны булева матрица, соответствующая отношению , и полученная в соответствии с (Б.78) и (Б.79) матрица

Рис. Б. 5

Используем второй метод. Имеем

(Б 80), (Б.81)

Таким образом, в этом предпорядке имеется три максимальных подотношения подобия, определенных на обычных подмножествах-

(Б 82)

Эти подотношения приведены на рис. 11.3.

ЛИТЕРАТУРA

1. Теория графов, «Мир», М., 1973.

2. Конечные графы и сети, «Наука», М., 1974.

3. Теория графов и ее применение, ИЛ, М., 1962.

4. Теория графов, «Наука», М., 1968.

5. (Ore О.), The four-color problem, Academic Press, New

York, 1967.

6. Ли (Liu С L.), Introduction to combinatorial mathematics, McGraw-Hill, New York, 1968.

7. Мун (Moon J. W.), Counting labelled trees, Canadian Math. Cong­ress, Montreal, 1970.

8. Харрис (Harris B.) (ed.), Graph theory and its applications, Aca­demic Press, New York, 1970.

9. Харари (Harary F.) (edA Proof techniques in graph theory, Academic press, New York, 1969.

10. Мирскин (Mirsky L.), Transversal theory, Academic Press, New

York, 1971.

11. , , Потоки в сетях, «Мир», М., 1966.

12. Приключения Алисы в стране чудес, «Детская ли­тература», М., 1974.

13. Апостол (Apostol Т. М.), Mathematical analysis, Addison-Wes-ley, Reading. Mass. 1957.

14. Введение в теорию вероятностей и ее приложен я, т. 1,«Мир», М., 1967.

15. Уитни (Whitney H.),On the abstract properties of linear dependen­ce, Amer. J. Math., 57 (1935), 509—533.

16. Теорема о раскраске карт, «Мир» М. 1977

1.7 Floyd R. VV., A Note on Mathematical Induction on Phrase Structured Grammar. Inform. Control, 4: 353—358.

18. F 1 о у d R. W., On the Non-existence of a Phrase Structured Gram­mar for mun. Assoc. Somputing Machinery, 5: 483 (1962).

19. F 1 о у d R. W., Syntactic Analysis and Operator Precedence. J. Assoc: Computing Machinery, 10:3 (1963).

20. G о г n S., Detection of Generative Ambiguities in Contextfree Alechanical Languages. J. puting Machinery, 10:196—208 (1963).

21. Chomsky N., Syntactic Structures. Moutan, 1962.

22. Chomsky N., On Certain Formal Properties of Grammars. Inform. Control, 2 :137—167.

23. Luce Bush, Galanter (eds.), «Handbook of Mathematical Psychology». John Wiley & Sons, Inc., New York, 1964.

24. Proceedings of a Working Conference on Mechanical Language Structures, August, mun. puting Machinery. 7:2 (1964).

25. Nour P. (ed.), Revised Report on the Algorithmic Language mun. puting Alachinery, 6(1) :1—17 (1963).

26. Meeting on lR-Oriented Languages, October, mun, puting Machinery, 5: I (1962).

27. Berge С, Les Problems de Flot et de Tension. Cahiers Centre Etudes Rech. Oper., 3, :69-^93 (1961).

28. D a n t z i g G. В., Fulkerson D. R., Computation of Maxi-

mal Flows in Networks. The RAND Corp., p. 677, 1955.

29. F о г d L. R., Jr., Network Flow Theory. The RAND Corp., p. 923, 1956.

30. Ford L. R., Jr., Fulkerson D. R., Maximal Flow through a Network. Can. J. Math., 8: 399—404 (1956).

31. F о r d L. R., Jr., Fulkerson D. R., A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem. The RAND corp., RM-1604, 1955.

32. Ford L. R., Jr., F_ulkerson D. R., Constructing Maximal Dynamic Flows from'Static Flows. Operations Res., 6: 419—433 (1959).

33. Fulkerson D. R., An Out-of-kilter Method for Minimal-cost Flow Problems. J. Soc. Ind. Appl. Math., 9: 18—27 (1961).