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

Рис. 5.55.

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

Для нахождения числа изомеров при k≤10 можно пред­ложить довольно сложный метод, который требует до­полнительных уточнений. Метод может быть обобщен на двухсвязные молекулы СkН2k и трехсвязные молекулы СkH2k+2. Существует метод определения числа структур­ных изомеров для значительно более сложных молекул.

5.23. Два примера из статистической механики

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

Начнем с задачи Изинга. Было замечено, что фер­ромагнитное вещество теряет свою намагниченность в зависимости от температуры. Таким образом, функция намагниченности является убывающей и резко падает при определенной температуре, называемой точкой Кюри. Задача состоит в разработке модели, которая объяс­няла бы явление резкого падения намагниченности. Эту задачу можно рассмотреть на некоторой решетке и по­пытаться записать функцию разбиения, которая для конечной решетки была бы аналитической функцией температуры и не учитывала бы наличия резкого паде­ния. Однако в некоторых пределах эта функция все же должна обладать интересующим нас свойством. Пусть задача рассматривается на трехмерной решетке и пред­полагается, что ферромагнетизм вызывается взаимодей­ствием между спинами определенных электронов в ато­мах, образующих кристалл. Эти взаимодействия можно описать следующей обобщенной задачей на языке тео­рии графов.

Требуется найти производящую функцию числа до­пустимых помеченных подграфов с k ребрами для поме­ченного графа, который представляет собой п-мерную решетку. Подграф является допустимым, если все его вершины имеют четную степень. До сих пор эта задача была решена только для п=1 (Изинг) и п=2 (Онзагер).

Пример графа Изинга приведен на рис. 5.56.

Рис. 5.56

Интересные работы по статистике решеток опубликованы Монтроллом. Работы сопровож­даются хорошей библиографией.

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

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

Более сложной математической задачей является задача раскладки, в которой требуется найти число спо­собов покрытия двухмерной решетки п квадратами. Причем квадраты могут быть двух типов: единичные и двойные. Считается, что п=п1+2п2, где п1 — число единичных квадратов, а п2 — число двойных квадратов.

5.24. Генетическая задача

Бенцер сформулировал следующую задачу о воз­можных соединениях, допустимых конфигурацией хими­ческих компонент генов. Если такими компонентами являются трехмерные молекулы, то они могут быть сое­динены вместе в соответствии с определенной структурой. Это объединение может быть представлено в трех­мерном пространстве, если каждой молекуле постав­лена в соответствие некоторая вершина и вершины сое­динены прямыми линиями при наличии связи между соответствующими молекулами. Возникает вопрос, мож­но ли расположить молекулы на одной и той же пря­мой линии так, чтобы они сохранили прежние связи? Каждая молекула представляется при этом отрезком прямой. Если пара молекул связана, то соответствую­щие им отрезки взаимно перекрываются. Таким образом, задача состоит в нахождении условий, при которых граф связей можно представить с помощью пересекаю­щихся определенным образом отрезков одной прямой линии, т. е. необходимо так сопоставить отрезки с вер­шинами, чтобы два отрезка пересекались тогда и только тогда, когда они соответствуют смежным вершинам. Граф, который может быть представлен таким образом, будет называться графом отрезков. Например, треуголь­ник можно представить на действительной оси перекры­вающимися отрезками

(0, 3), (1, 4) и (2, 5). С другой стороны, цикл, состоящий более чем из трех вершин, не может быть представлен рассматриваемым способом.

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

Рис. 5.57

Биологическая задача в ее общем виде связана с мутантными генами. Требуется проверить соответствие линейной модели гена заданной информации о пересечении (соединении) пар.

Фалкерсои и Гросс показали, что задача определе­ния графа отрезков является частным случаем следую­щей задачи, которую они решили: дана (0, 1) матрица А (т. е. матрица, элементы которой равны 0 или 1). Найти условия, при которых можно путем перестановки строк матрицы получить новую матрицу, в каждом столбце которой единичные элементы расположены не­посредственно друг за другом. Заметим, что сопостав­ление графа произвольной матрице А оказывается не­однозначным. Один из способов, например, состоит в

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

При решении сформулированной задачи вводится понятие графа «перекрытий» (отличается от «пересече­ний») и понятие графа компонент.

Применительно к графу отрезков матрица А должна рассматриваться как матрица инциденций доминирую­щих клик. (Множество вершин, каждая пара которых соединена ребром, называется кликой графа. Если семейство всех таких множеств вершин частично упорядо­чено по множеству включений, то максимальные эле­менты называются доминирующими кликами графа. Учитывая, что две вершины связаны ребром тогда и только тогда, когда они принадлежат некоторой доми­нирующей клике, можно считать, что матрица инциденций доминирующих клик полностью определяет граф.) В результате граф является графом отрезков тогда и только тогда, когда единичные элементы во всех столб­цах матрицы инциденций доминирующей клики распо­ложены последовательно друг за другом. Гилмор и Гоф­ман доказали, что граф G является графом отрез­ков тогда и только тогда, когда каждая квадратная решетка в G имеет диагональ и каждый цикл нечетной длины в дополнительном графе имеет треугольную хор­ду. Треугольная хорда цикла, проходящего через вер­шины v1,...,vk, есть любое ребро (vi, vi+2), l≤i≤k—2, (vk-1, v1) или (vk, v2).

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

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

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

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

Бледная кожа→темная кожа.

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

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

замкнуто.

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

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

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

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