Книги по разным темам Pages:     | 1 |   ...   | 35 | 36 | 37 | 38 | 39 |   ...   | 41 |

&п, в которое входят те G-структуры Gi из множества &п, которые состоят из максимально сочетаемых классов, соответствующих графу rn(Gi) или, но в другой терминологии, основанных на кликах этого графа. Подобные структуры называются также полными покрытиями rn(Gi). Будем обозначать структуры Ci из Gn и называть С-структурами. Примерами С-структур являются структуры G1 и G2, изображенные на рисунке Г.15.

Pn, в которое входят те G-структуры из &n, элементы которых состоят из пар, связанных на графе rn(Gi) узлов (обозначаемых целыми числами), или являются отдельными изолированными узлами. Будем структуры из множества &n называть Р-структурами и обозначать через Pk. Примером Р-структуры является структура G4 на рисунке Г.15.

Из этих определений и из того факта, что множество всех максимально сочетаемых классов для любого неориентированного графа единственно, следует, что любой класс эквивалентности из &п/rп содержит в точности одну С-структуру из &п и одну Р-структуру из Pп. Таким образом, С- и Рструктуры могут рассматриваться как два канонических представления классов r-эквивалентности G-структур. Каждый класс r-эквивалентности, представленный графом, описывается двумя каноническими структурами - наименее уточненной С-структурой и наиболее уточненной Р-структурой. Взаимно однозначное соответствие между Rп и Gп (или Pп) индуцирует булеву решетку на Gп (или на Pn), изоморфную естественной булевой решетке, определенной на Pn.

Например, на рисунке Г.16 показаны решетка (&3,) и взаимно изоморфные булевы решетки, определенные на R3, G3, P3 и &3/r3.

Рисунок Г.16 - Решетка (&3,) и булевы решетки, определенные на R3, G3, P3, &3/rДля описания больших решеток полезно определить отношение эквива- i лентности n на множествах & следующим образом:

&3/i &G1=CGGG2=PGGGC2 GPGGGGCGPGGG5 GCGGPа) б) Рисунок Г.17 - Решетка (&3, ) и гомоморфное отображение &3&3/i i Gi тогда и только тогда, когда Gi, Gj&n и Gi, Gj изоморфны (то Gj есть когда одна структура может быть получена из другой только перестановкой целых чисел из Nn, напоминаем, что каждое целое число соответствует i узлу). Будем n называть i - эквивалентностью и обозначать через & /i множество классов эквивалентности изоморфных структур (или перестановочных классов эквивалентности), определенных на &п.

Пример, демонстрирующий смысл i-эквивалентности, приведен на рисунке Г.17, где обозначенные полужирным шрифтом Gk (kN5) показывают классы эквивалентности в &3/i. На рисунке Г.17,а показана решетка (&3/i, ). Это та же самая решетка, что и на рисунке Г.16, но упрощенная, так как на ней не различаются изоморфные структуры. Сделано это за счет удаления меток входов в блоки на схеме и включения только одной схемы для каждого перестановочно эквивалентного класса. Структуры в каждом классе легко определяются перестановкой целых 1, 2, 3 для входов в блоки. Упрощенная решетка на рисунке Г.17,в является гомоморфным образом решетки, изображенной на рисунке Г.16. Гомоморфное отображение, являющееся основой данного упрощения, показано на рисунке Г.17д На рисунке Г.18 показана более сложная решетка (&4/i, ). Перестановочные классы эквивалентности G-структур снова выделены жирным шрифтом, равно как С-структуры и Р-структуры, сгруппированные по классам rэквивалентности. Каждому такому классу соответствует граф k и две канонические структуры Ck и Pk (kN11). Для того чтобы более ярко продемонстрировать общие свойства этой решетки, на рисунке Г.19 перестановочные классы С-структур обозначены только их идентификаторами и выделены классы r-эквивалентности Рисунок Г.18. Решетка с указанием классов r-эквивалентности и канонических G- и Р-структур Рисунок Г.19 - Упрощенная схема ре- Рисунок Г.20 - Решетка (&4/i, ) шетки (&4/i, ), полностью показан- ной на рисунке Г.На рисунке Г.20 изображена решетка (&4/i, ), являющаяся подрешеткой (G4/i, ). Число около каждой схемы указывает на число различных Сструктур, входящих в перестановочный класс эквивалентности, показанный на этой схеме; числа, помещенные около дуг, указывают на число непосредственных уточнений С-структуры из данного перестановочного класса эквивалентности в другой класс. Как уже объяснялось выше, эта решетка изоморфна решеткам, определенным на R4/i, P4/i и (&4/i).

В то время как полные решетки (&n, ) представляют основу для локального уровня вычислений в задаче реконструкции, решетки (&n, ) и их изоморфизмы являются основой для глобальных вычислений. Для работы на глобальном уровне вычислений необходима процедура, порождающая для любой заданной С-структуры Ck&n (nN) все непосредственные уточнения в решетке (&n, ). Ниже приводится одна такая процедура, использующая представление С-структур в виде графов.

Уточняющая процедура для С-структур (или КС-процедура). Дана Сструктура Ск&п и соответствующий граф rn(Ck). Нужно определить все непосредственные уточнения на множестве.

1) исключить одно ребро из графа rn(Ck), скажем ребро (a, b);

2) разделить каждый элемент х из Сk, который содержит а и b на два элемента ха = х - {b} и xb = x - {а} и заменить х из Ck на xа и xb;

3) исключить все избыточные ха и xb, полученные на шаге 2 и записать полученный результат в качестве непосредственного уточнения Ck в решетке (&п,);

4) выполнить шаги 1Ч3 для всех ребер графа rn(Ck) и остановиться.

Данная процедура имеет следующие обоснования: 1) имеется взаимно однозначное соответствие между множествами Rп и &п и, следовательно, любое изменение графа приводит к изменению соответствующей С-структуры; 2) чем меньше число ребер графа, тем более уточненной является соответствующая С-структура; 3) поскольку никакой из циклов в вершинах нельзя исключить без нарушения.условия покрытия соответствующей С-структуры, то наименьшим допустимым сокращением графа является исключение одного из ребер. Таким образом, число ребер в графе определяет число непосредственных уточнений соответствующей С-структуры.

Пример Г.18. Рассмотрим граф 1 и соответствующую С-структуру Ci (рисунок Г.21,а). Этот граф имеет шесть ребер и, следовательно, шесть непосредственных уточнений этой С-структуры. Они изображены на рисунке Г.21,б. Например, уточнение получается с помощью RС-процедуры следующим образом: 1) из графа 1 исключается ребро (Г,5) и получается граф 7 ;

2) элемент (2, 4, 5} из C1 (единственный элемент С1 содержащий и 4 и 5) разбивается на элементы (2, 5} и {2, 4}; 3) поскольку элемент {2, 4} является единственным избыточным элементом ({2, 4} {2, 3, 4}), он исключается, а полученный результат С7={{1, 2}, {2, 5}, (2, 3, 4}} записывается как непосредственное уточнение С1.

Так как элементы Р-структур представляют собой просто ребра соответствующих графов, то процедура уточнения Р-структур (или RРпроцедура) совершенно тривиальна. Она состоит в исключении отдельных ребер из заданного графа [смотри шаг 1 RС-процедуры] и интерпретации результатов как Р-структур.

Полезны также процедуры, с помощью которых получаются все непосредственные укрупнения для множеств G-, С- и Р-структур. Они нужны для определения полного структурного соседства заданной структуры. Формулирование этих процедур мы предоставляем читателю в качестве упражнения (смотри также рисунок Г.10). Примеры такого соседства для трех этих типов структур приведены на рисунках Г.22 - Г.2Г. В этих примерах структуры обозначены соответственно как G, С и Р. Их непосредственные уточнения помечены нижними индексами, а непосредственные укрупнения - верхними.

На рисунке Г.22 показано, что в структурное соседство данной G-структуры могут входить G-структуры, входящие в другой класс r-эквивалентности (на рисунке Г.22 это структура G3). Чтобы непосредственные уточнения принадлежали тому же классу r-эквивалентности, можно слегка модифицировать RG-npoцедуру, заменив условие |kS| 2 на шаге 3 условием | kS |>2.

При СCCCРисунок Г.21. Пояснение к RС-процедуре: а Ч заданный граф и соответствующая С-структура; б Ч непосредственные уточнения CРисунок Г.22. Структурное соседство G-структуры G этом запрещается изменять элементы, содержащие только две вершины, и, следовательно, граф данной r-структуры остается неизменным.

Представление о непосредственных уточнениях (или укрупнениях) структур различных типов можно использовать для разбиения соответствующего множества структур на блоки структур, эквивалентных в смысле уровня уточнения, т. е. таких структур, которые достигаются от универсальной верхней границы {Nn} соответствующей решетки уточнения за одинаковое число шагов уточнения. Будем называть эту эквивалентность эквивалентноi стью уровня уточнения и обозначать. Так, например, структуры G, G2, G3 на рисунке Г.22 - l-эквивалентные G-структуры из множества &4; структуры, показанные на рисунке Г.21,б, - l-эквивалентные С-структуры из множества G5; структуры Р1.P2, Р3, P4 на рисунке Г.24 являются l-эквивалентными Р-структурами из множества &Г.

Для того чтобы можно было составить представление о скорости роста числа структур этих трех типов с ростом п, а также числа их классов i- и lэквивалентности, в таблице Г.12 приведены соответствующие данные для п 7. Понятно, что | &n |=| Pn |=| Rn |,| Rn |= 2n( n-1 ) / 2, Рисуноу Г.23 - Структурное соседство С-структуры С Рисунок Г.24 - Структурное соседство Р-структуры Р Таблица Г.12 - Число G-структур в &n+ и &n, С-структур и их классов i-эквивалентности и классов l-эквивалентности для n n 1 2 3 4 5 6 |Gn+| 1 4 18 166 7,579 7,828,352 2,414,682,040,|Gn| 1 2 9 114 6,894 7,785,062 2,414,627,396,|&n| 1 2 8 64 1,024 32,768 2,097,|Gn+/i| 1 3 8 28 |Gn/i | 1 2 5 20 |&n/i | 1 2 4 П 34 156 1,|Gn+/l| 1 3 7 15 31 63 |Gn/l | 1 2 5 12 27 58 |&n/l | 1 2 4 7 11 16 где показатель п(п Ч 1)/2 Ч общее число возможных ребер в графе, определенном на Nn. Ясно также, что |Gп/1|=п(пЧ1)/2+1. Вычисление |Rn/i| для заданного более сложно, но эта задача уже решена в теории графов (смотри раздел Г.11). Приведенные в таблице Г.12 значения |G+n|, |G+n/i|, |G+n/l|, |Gп|, |Gn/i| и |Gn/l| известны только для п7.

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

Для решения задачи реконструкции наибольший интерес представляют ациклические структуры особого типа, которые можно было бы назвать строго ациклическими структурами или L-структурами. G-структура GiGn является L-структурой тогда и только тогда, когда не существует такой пары (а, b)N2n, что она входит в некий элемент Gi и связана через несколько соединенных элементов. Будем множество L-структур для некоего п обозначать Ln.

Определим множество Lп формально. Пусть дана G-структура Gi&n. Для любой пары (a, b)N2n пусть Xa,b={x|xGi, {а, b х}.

Тогда Gi является L-структурой (GiLn) тогда и только тогда, когда не существует пары (a, b)N2n, являющейся элементом транзитивного замыкания rn(Gi - Ха,b ).

Очевидно, например, что все структуры из множества G3 (рисунок Г.16), за исключением структуры G2={{1, 2}, {2, 3}, (3, 1}}, являются L-структурами. В множестве G4 только три структуры не являются L-структурами. Они принадлежат к одному и тому же классу i-эквивалентности, который можно, например, представить С-структурой С={{1, 2}, {2, 3}, {3, 4}, {4, 1}}. В самом деле, транзитивное замыкание r4(С - X1,2)- это N4, и, следовательно, пара (1, 2) является ее элементом.

L-структуры отличаются тем, что для них не нужно использовать итеративную процедуру соединения независимо от порядка, в котором объединяются элементы рассматриваемой L-структуры. Ациклические структуры, не являющиеся L-структурами, этим замечательным свойством не обладают. Для таких структур, чтобы избежать применения итеративной процедуры соединения, нужно применять базовую процедуру соединения к элементам, расположенным в определенном порядке. Определение таких порядков требует сложных вычислений и проверок, так что методологическое значение таких структур существенно уступает значению L-структур.

С помощью различных понятий, введенных в этом разделе, можно более конкретно сформулировать задачу реконструкции. Дана обобщенная система и множество заданных пользователем реконструктивных гипотез (базирующихся на множестве Gп, &п, Pп или L - cтpyктyp). Решение задачи реконструкции сводится к выбору подмножества данного множества в соответствии с некоторыми требованиями. Обычно требуется, чтобы: 1) расстояния, соответствующие выбранным гипотезам, были как можно меньше и 2) сами гипотезы были, возможно, более уточненными. Оба эти требования предполагают упорядочение множества реконструктивных гипотез. Упорядочение в соответствии с требованием 2 фиксировано - это частичное упорядочение по структурному уточнению с решеткой, свойства которой описаны выше. Упорядочение согласно требованию 1 - его можно назвать упорядочением по расстоянию Ч не фиксировано. Оно зависит от данной обобщенной системы и выбранного типа расстояния и определяется только вычислением несмещенных реконструкций и расстояний отдельных реконструктивных гипотез.

Если используется расстояние, определяемое по формуле (Г.40) для вероятностных систем [или по формуле (Г.42) для возможностных систем], которое является мерой количества информации, потерянной при замене обобщенной системы реконструктивной гипотезой, то существует определенное предупорядочение по расстоянию: информационное расстояние монотонно не убывает с увеличением уточнения реконструктивных гипотез.

Кроме того, оба варианта информационного расстояния аддитивны для любого пути на используемой решетке уточнения. Это значит, что D (f x, f z) =D (f x, f y) + D (f y, f z) (Г.43) для любых трех реконструктивных гипотез х, у, z одной обобщенной системы, таких, что x y z. Свойства предупорядоченности и аддитивности очень полезны при решении задачи реконструкции и придают особую важность информационному расстоянию. В дальнейшем при обсуждении задачи реконструкции всегда будет предполагаться, что используется соответствующая версия информационного расстояния (то есть вероятностная или возможностная, базовая или порождающая).

Pages:     | 1 |   ...   | 35 | 36 | 37 | 38 | 39 |   ...   | 41 |    Книги по разным темам