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

есть взаимно однозначное преобразование, а

им не является.

Рассмотрим теперь пример применения последова­тельных однозначных преобразований к некоторому множеству операндов, который проиллюстрирует прин­цип «выбора» на множестве операндов:

(вторая строчка является частью предложения, взятого из произведения Марка Твена «Письма с Земли»). За­метим, что уже после четырех преобразований исходное множество из 26 элементов сводится к множеству из 5. Выполненные выше последовательные преобразования могут быть представлены ориентированным графом, ко­торый Эшби называет кинематическим (рис. 5.58).

Рис. 5.58.

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

Теорема 5.11. Кинематический граф состоит из не­скольких простых контуров, не имеющих общих вершин, тогда и только тогда, когда преобразование взаимно однозначно.

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

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

состоит из k = 3 петель (рис. 5.59).

Рис. 5.59

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

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

Преобразование можно представить матрицей вер­шин, например:

Задача определения элементов, которые будут выбирать­ся при

m-кратном повторении преобразования, эквивалентна задаче определения столбцов матрицы, которые содержат положительные элементы после возведения матрицы в m-ую степень.

Матрица взаимно однозначного преобразования яв­ляется единственной матрицей однозначного преобразова­ния, содержащей единичный элемент в каждой строке и каждом столбце. Следовательно, это единственная мат­рица, которая может быть примитивной. Таким образом,

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

Кроме понятия изоморфизма преобразований, кото­рое совпадает с понятием изоморфизма графов, Эшби определил понятие гомеоморфизма преобразований. Требования для гомеоморфизма менее жесткие, чем для изоморфизма. Два множества операндов гомеоморфны, если применение преобразования объединения к более сложному множеству может свести его к множеству,

которое изоморфно с более простым. В терминах гра­фов два графа будут гомеоморфными, если соответ­ствующее стягивание подграфов графа с большим чис­лом вершин в отдельные вершины дает граф, который изоморфен более простому графу. Два графа на рис. 5.60 гомеоморфны.

Рис. 5.60.

5.26. Применения в социологии

Ориентированный граф может быть использован для представления общественной иерархии или родства. Рассмотрим простой пример. Пусть имеется семей­ная группа, состоящая из Дэвида (D), его сына Джона (J) и дочери Грейс(G), жены Джона Сильвии (S) и двух сыновей Майкла (М), Ричарда (R), дочери Эмилии (Е) и сына Грейс Бена (В). Связи Р (означает чей-то сын) и Q (означает чей-то ребенок) иллюстрируют­ся ориентированными графами рис. 5.61.

Рис. 5.61.

Соответствую­щие матрицы для этих графов имеют вид

Взяв произведение матриц, получим матрицу отноше­ний PQ (сын ребенка, т. е. чей-то внук):

Рассмотрим еще один пример.

Ставился эксперимент по изучению эффективности схем связи. Каждому из пяти лиц, участвовавших в экс­перименте, выдавалось пять символов из шести следующих:

В каждом опыте все участники имели только один об­щий символ. Для каждого участника фиксировалось число сообщений и время, необходимое для опознава­ния общего символа.

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

Рис. 5.62.

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

Каждый участник давал свою оценку схем по степе­ни удовлетворенности пребыванием в различных вер­шинах.

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

Наибольшая удовлетворенность участников экспери­мента соответствовала схеме цикла, а наименьшая — схеме колеса. Во всех случаях наиболее выгодной было положение центрального участника С (конечно, там, где такое положение существенно).

В другом эксперименте три участника А, В и С долж­ны были восстановить общий список из 25 слов по имев­шемуся у каждого из них частичному списку. Спис­ки участников содержали последовательные пары слов такие, что, например, второе слово в паре А-го списка было первым словом пары В-гo или С-го списка. Идея построения списков иллюстрируется приводимой табли­цей 5.2.

Таблица 5.2

Далее участники должны были восстановить предло­жение из 25 слов (каждое слово имело не более трех слогов) по заданному частичному списку слов, приве­денных в той же последовательности, в которой они стоят в предложении. Одним из таких предложений было: «The picture we saw was painted by an old woman who had been tought how to mix the colours by one of the native artists» ( Картина, увиденная нами, была нарисована старой женщиной, которая училась смешивать краски у одного местного художника.), а один из частичных списков имел вид: picture was an who been to the colours of native.

Третий эксперимент состоял в составлении анаграм­мы трех буквенных слов, полученных из слов, имеющих девять букв по четыре гласные в каждом. Например, abolished courtesan.

Участники должны были максимизировать общее число очков группы. Если одно и то же слово повторялось во всех трех записках, оно считалось три раза. На рис. 5.63 показано пять использовавшихся схем связи.

Рис. 5.63.

Заметим, что в данном случае связь была направленной. Для раз­личных схем измерялось время, число сообщений и трудности исправления ошибок при передаче сообще­ний. Участники эксперимента находились в различных комнатах и могли общаться только по телефону. В ли­нии связи вводился белый шум, т. е. шум, спектр частот которого имеет одну и ту же интенсивность, чтобы за­глушать звуки, которые проходили через стены. Кроме того, каждое задание выполнялось при трех различных отношениях сигнал/шум: +6, —2 и —10 децибел. Соот­ветственно процент правильного приема был равен 85%, 66% и 24%. Было установлено, что первая схема является лучшей при выполнении первого задания, третья схема — при выполнении второго задания, нако­нец, все схемы одинаковы при выполнении третьего задания. Пятая схема была наихудшей для первого и второго заданий, и различные уровни шума только подчеркивали ее недостатки.

5.27. Математические модели разоружения

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