Метасистемный подход в управлении: Монография. Миронов С.В - 287 стр.

    Таблица Г.12 - Число G-структур в & n + и & n , С-структур и их
классов i-эквивалентности и классов l-эквивалентности для n ≤ 7
         n    1   2   3      4       5        6             7
           +
       |Gn | 1    4 18 166 7,579 7,828,352 2,414,682,040,996
        |Gn|  1   2   9    114 6,894 7,785,062 2,414,627,396,434
        |&n|  1   2   8     64    1,024    32,768      2,097,152
          +
      |Gn /i| 1   3   8     28     208
      |Gn/i | 1   2   5     20     180
      |&n/i | 1   2   4     П       34      156          1,044
          +
      |Gn /l| 1   3   7     15      31       63           127
      |Gn/l | 1   2   5     12      27       58           121
      |&n/l | 1   2   4      7      11       16            22


где показатель п(п — 1)/2 — общее число возможных ребер в графе, опреде-
ленном на Nn. Ясно также, что |Gп/1|=п(п—1)/2+1. Вычисление |R n /i | для
заданного более сложно, но эта задача уже решена в теории графов (смотри
раздел Г.11). Приведенные в таблице Г.12 значения | G + n |, | G + n /i | , | G + n / l |,
| G п |, | G n /i | и | G n /l | известны только для п≤7.
        Введем упоминавшиеся уже структуры еще одного типа. Это такие
структуры, для которых при работе с вероятностными системами для опре-
деления несмещенной реконструкции не нужна итеративная процедура со-
единения. Обычно их называют ациклическими структурами.
        Для решения задачи реконструкции наибольший интерес представля-
ют ациклические структуры особого типа, которые можно было бы назвать
строго ациклическими структурами или L-структурами. G-структура
G i ∈ G n является L -структурой тогда и только тогда, когда не существует
такой пары ( а , b ) ∈ N 2 n , что она входит в некий элемент Gi и связана через
несколько соединенных элементов. Будем множество L-структур для не-
коего п обозначать L n .
       Определим множество L п формально. Пусть дана G-структура
G i ∈ & n . Для любой пары ( a , b) ∈ N 2 n пусть
                                       X a,b ={x | x ∈ G i , { а , b ⊂ х}.
Тогда Gi является L-структурой (Gi ∈ Ln) тогда и только тогда, когда не суще-
ствует пары (a, b)∈ N2n, являющейся элементом транзитивного замыкания rn(Gi
- Ха,b ).
       Очевидно, например, что все структуры из множества G 3 (рисунок
Г.16), за исключением структуры G 2 ={{1, 2}, {2, 3}, (3, 1}}, явля-
ются L-структурами. В множестве G4 только три структуры не являются
L-структурами. Они принадлежат к одному и тому же классу i-эквива-
лентности, который можно, например, представить С-структурой
С={{1, 2}, {2, 3}, {3, 4}, {4, 1}}. В самом деле, транзитивное замыка-
ние r4(С - X1,2)- это N4, и, следовательно, пара (1, 2) является ее элемен-
том.

287