Cтраница 2
Одной нз наиболее знаменитых теорем в комбинаторной математике является теорема Брука - Райзера - Човла, дающая легко проверяемое необходимое условие существования симметричных блок-схем. [16]
Поскольку (16.4.25) также дает tn - k, то каждое а - / есть нуль или единица, и А является матрицей инцидентности симметричной блок-схемы. При четном k - К теорема неверна. При А, 1 существует много контрпримеров. [17]
Если А - матрица целых чисел, удовлетворяющая (16.4.1), и либо AJ kJ, либо JA kJ, то А есть матрица инцидентности симметричной блок-схемы. [18]
В этом разделе мы коснемся вопроса, существуют ли такие матрицы А, и если существуют, то при каких условиях А является матрицей инцидентности некоторой симметричной блок-схемы с параметрами v, k, К. Первая теорема проста, но не совсем тривиальна. [19]
Если мы назовем элементы S точками, а блоки - прямыми, то SP молшо рассматривать как конечную проективную плоскость на множестве точек S: свойства симметричных блок-схем обеспечивают, как нетрудно убедиться, выполнение аксиом 1) - 3) конечной проективной плоскости. [20]
Теорем а 10.4. Если s4 - - блок-схема с параметрами Ь пг п, v и2, г п 1, k тг, X 1, го существует симметричная блок-схема & с параметрами v п2 п 1, А ге 1, А, 1, для которой 4 - - остаточная схема. [21]
Теорема 9.3 показывает фактически, что если А - матрица инцидентности симметричной блок-схемы с параметрами v, k, Я, то и транспонированная матрица Ат - матрица инцидентности некоторой симметричной блок-схемы с теми же параметрами. Это подсказывает еще один способ получения новых блок-схем из уже известных. [22]
В силу теоремы 3 удовлетворяются все четыре равенства ( 14), ( 15), ( 16) и ( 17), и, следовательно, мы имеем симметричную блок-схему с параметрами v 4t - 1, k 2t - 1, Kt-1. Обратно, из такой блок-схемы легко построить нормализованную матрицу Адамара Н порядка 4t, поскольку блок-схема точно определяет позиции для 1 внутри каймы из 1 в 0 - й строке и 0 - м столбце. [23]
Следовательно, уравнение (9.9) не может иметь решения в целых числах, отличного от ( х, у, z) ( 0, 0, 0), и по теореме 9.4 симметричной блок-схемы с параметрами v 43, k 7, Я, 1 не существует. [24]
Выписать матрицу инцидентности симметричной блок-схемы, которую порождает это множество. [25]
Между параметрами уравновешенной неполной блок-схемы, кроме (5.2), (5.3), существуют также другие соотношения. Таким образом, в матрице инцидентности симметричной блок-схемы содержится не только в точности k единиц в каждой строке, но и k единиц в каждом столбце. [26]
Соотношения (9.1), (9.2) ( а для симметричных блок-схем - (9.4), (9.5)) дают по теореме 9.1 необходимое и достаточное условие существования блок-схемы с параметрами b, v, r, k, X. Однако это условие никак нельзя признать эффективным, так как решение подобных матричных уравнений при сколь-нибудь значительных размерах матриц лежит вне пределов возможностей современных вычислительных устройств. [27]
Здесь два блока 1, 6, 7, 9, 12, 13 и ( 1, 6, 8, 10, 12, 13 имеют четыре общих элемента. Следовательно, для этой схемы не существует производной схемы некоторой симметричной блок-схемы с параметрами v - b 25, r & 9, Я 3, в такой симметричной схеме любые два различных блока имеют ровно три общих элемента. [28]
Рассмотрим некоторые совокупности чисел Ь, у, г, k, К, для которых выполняются необходимые условия (5.2), (5.3) существования блок-схем ( в случае симметричных блок-схем они сводятся к одному K ( v - i) k ( k - 1)), так что блок-схемы с такими параметрами могут существовать. [29]
Теорема Брука - Райзера - Човла дает наиболее сильное условие существования блок-схем. До сих пор не найдено, как мы уже упоминали в начале параграфа, ни одного примера такого множества параметров v, fc, К, чтобы выполнялись условия h ( v - 1) k ( k - 1) и условия этой теоремы, а при этом было бы доказано, что симметричной блок-схемы с этими параметрами не существует. Для многих значений параметров существование блок-схем остается под сомнением. [30]