Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 14»

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 14 Сборник переводов Под редакцией О. Б. ЛУПАНОВА ИЗДАТЕЛЬСТВО «МИР* МОСКВА 1977 УДК 519. 95 Научный совет по кибернетике Академии наук СССР Продолжение новой серии кибернетических сборников, пуб- публикация которых была начата издательством «Мир» в 1965 г. В данном выпуске содержатся обзорные статьи и оригинальные работы известных зарубежных ученых по наиболее актуальным проблемам теоретической кибернетики. Большой интерес предста- представляют работа Ю. Куликовского по распознаванию образов, ра- работа Д. Гриса и Р. Констейбла о классах схем программ, а так- также статья У. Татта по теории графов. Книга предназначена для научных работников, инженеров-ис- инженеров-исследователей, аспирантов и студентов, занимающихся и интере- интересующихся теоретической кибернетикой и ее приложениями. М. Райт 1. ВВЕДЕНИЕ В работе рассматриваются графы простейшего вида, т. е. (я, q) -графы, которые состоят из п вершин и q неупорядоченных пар вершин, называемых ребрами. Петли или кратные ребра не допускаются. Число различных (п, q) -графов на помеченных вершинах обозначается через F = F{n,q), если же вершины не помечены, то через T=T(n,q). Существует самое большее N = п(п—1)/2 возможных ребер, и поэтому F = B(N, q), где В (Л, k) = h\j{k\ (h — k)!} — обычный биномиальный коэффици- коэффициент. Наша задача заключается в нахождении асимптотики Т для больших значений п и q. Из обозначений N = n(n— l)/2 ясно, что наибольшее значение q равно N. В дальнейшем под символами Л, С и ц будут подразуме- подразумеваться числа, но не всегда одни и те же. Числа Л и С положи- положительны и не зависят от п и q. Символ А используется для обо- обозначения любого положительного числа, которое можно выбрать, в то время как С — подходящее положительное число, которое может зависеть от данного или полученного значения Л, при- присутствующего в изучаемом выражении или подразумевающе- подразумевающегося. Из чего, если не оговорено обратное, во всех наших ут- утверждениях предполагается, что п и q — достаточно большие, т. е. что q>C и п>С. Обозначение О( ) приводится для мажорирования величин, зависящих от п и q при стремлении к бесконечности, а под мажорирующей константой понимается величина С. Величина ц—произвольное число, равное O(q~c) для некоторого С. Ясно, что F(n,q)= F(n, N — q) и аналогично T(n,q) = = Т(п, N — q). Следовательно, далее можно считать, что 4) Wright E. M. , Graphs on unlabelled nodes with a large number o! ed- edges, Proc. London Math. Soc. C), 28 A974), 577—594. Это исследование ча- частично финансировалось правительством США. §1974, Oxford University Press Перевод на русский язык, «Мир», 1977 E. M. Райт Обозначим Л„ = Л(р, д) = в{±р{р-1), q}/p\, |х = Bq/n) - log n, J = / (о) = {1 A + log t»)/t» }'/a, = i(l +Erfjc).