ЗАДАЧИ ИЗУЧЕНИЯ ЧЕЛОВЕКА И ОБЩЕСТВА

6.25. Графы и кибернетика

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

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

изменение — переходом. Переход может быть представлен в виде

Множество переходов, выполняемых одним оператором на множестве операндов, будем называть преобразованием. Схематически преобразование может быть представлено в виде

Преобразование замкнуто, если множество результатов преобразований не содержит элементов, которые не принадлежат множеству операндов. Так, преобразование

замкнуто.

Преобразование является однозначным, если оно переводит один операнд точно в один результат преобразования (множество результатов преобразования может содержать одинаковые элементы). Так,

является однозначным преобразованием. С другой стороны,

не является однозначным.

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

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

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

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

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

Рис. 6.58.

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

взаимно однозначным. В терминах теории графов получим следующую теорему.

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

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

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

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

Рис. 6.59.

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

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

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

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

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

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

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

Рис. 6.60.

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