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

Определение 4.7. Будем называть ЛО с ограничениями третьего рода для квадратной М × М-матрицы выражения вида

(4.38)

(4.39)

т. е. дизъюнкцию (конъюнкцию) БЛ всех сумм элементов А, содержащих каждая точно по одному элементу из каждого столбца и каждой строки А. Как и для ЛО первого и второго рода, здесь достаточно ограничиться изу­чением дизъюнктивного ЛО Сравнив (4.38), (4.39) с (4.24), (4.25), устанавливаем, что ЛО третьего рода — частные случаи ЛО второго рода при М = Р и вырожденных ограничениях (4.23):

(4.40)

Этим определяются все свойства ЛО третьего рода.

Теорема 4.6. ЛО вида (4.38), (4.39) всегда существуют.

Доказательство. Достаточно проверить выполнение условия (4.26), определяющего существование более общих ЛО вида (4.24), (4.25). В данном случае и (4.26) принимает вид что всегда выполняется. Поэтому ЛО (4.38), (4.39) всегда существуют.

ЛО третьего рода обладают свойствами ЛО первого рода, сформулиро­ванными в леммах 4.1 — 4.9, что доказывается точно так же. Кроме того, они обладают некоторыми специальными свойствами, вытекающими из равноправия их строк и столбцов. Так, справедлива

Лемма 4.18. Перестановка местами строк и столбцов с одинаковыми номерами (транспонирование) не меняет величины ЛО.

Доказательство. При указанной перестановке множество сумм остается прежним, и, согласно определениям (4.38), (4.39), ЛО не меняет величины.

4.8. Разложение логических определителей третьего рода

Разложение ЛО с ограничениями третьего рода на меньшие ЛО пресле­дуют ту же цель, что и выше ( § 4.3,4.6).

Определение 4.8. Пусть — произвольный М × М-ЛО (4.38) ЛО, полу­ченный из вычеркиванием i-й строки j-ro столбца, на пересечении кото­рых стоит элемент называется логическим дополнением этого элемен­та в ЛО и обозначается

Теорема 4.7. Произвольный ЛО (4.38) можно разложить:

1) по любо­му j-му столбцу, представив его в виде дизъюнкции БЛ сумм всех элемен­тов этого столбца и их логических дополнений

(4.41)

2) по любой i-й строке, представив его в виде дизъюнкции БЛ сумм всех элементов этой строки и их логических дополнений

(4.42)

Доказательство. Так как ЛО — частный случай ЛО по

теореме 4.4

где - логическое дополнение элемента в ЛО понимаемое в смыс­ле определения 4.5. Но область значений параметра pi в есть (1,1) и ее сдвиг влево на 1 дает область (0,0), что равносильно исключению i-й строки Поэтому здесь определение 4.5 совпадает с определением 4.8, т. е. и выписанное равенство переходит в (4.41). Доказательство разложения (4.42) получается, если воспользоваться леммой 4.18 и пере­ставить местами строки и столбцы ЛО с одинаковыми номерами, а полу­ченный ЛО разложить согласно (4.41).

Интересно заметить, что полученные разложения по столбцу (4.41) и по строке (4.42) совершенно аналогичны; это объясняется равноправ­ностью строк и столбцов ЛО в смысле наложенных на них ограничений.

В то же время ЛО введенные в § 4.2 — 4.6, этого равноправия не имеют, так что их предполагаемые разложения по строке должны были бы отличаться от полученных выше их разложений по столбцу.

Разложения по столбцу (4.41) и по строке (4.42) обобщаются так.

Определение 4.9. Пусть - произвольный М × М-ЛО (4.38). ЛО, полу­ченный из выделением всех элементов, стоящих на пересечении множест­ва строк с множеством столбцов где назовем минором r-го порядка и обозначим ЛО, полученный из вычеркиванием множества-строк Dr и множества столб­цов Вr, назовем логическим дополнением минора в ЛОи обозначим

Теорема 4.8. Произвольный ЛО (4.38) можно разложить:

1) по любой совокупности столбцов Вr, представив его в виде дизъюнкции БЛ сумм всех миноров с данным Вr и их логических дополнений

(4.43)

2) по любой совокупности строк Dr, представив его в виде дизъюнкции БЛ сумм всех миноров с данным Dr и их логических дополнений

(4.44)

Доказательство можно получить с помощью теоремы 4.5, ибо ЛО -частный случай ЛО (см. выше подобное доказательство теоремы 4.7).

Но есть и прямое доказательство. Действительно, минор — это максимальная сумма элементов, содержащая точно по одному элементу из каждой строкии из каждого столбца матрицы А. Логическое дополнение - это максимальная сумма элементов, содержащая точно по одному элементу из каждой строки и из каждого столбца Поэтому сумма — это максимальная условная сумма элементов, содержащая ровно по одному элементу из каждой строки и из каждого столбца всей матрицы А и взятая при условии, что для любого элемента суммы из следуети обратно. Для получения максимальной безусловной суммы, т. е. ЛО остается взять еще максимум по Dr или по Вr ; первое дает формулу (4.43), второе - (4.44).

В частном случае при формулы (4.43), (4.44) пере-

ходят соответственно в (4.41), (4.42). Разложения (4.41) - (4.44), как и (4.30), (4.34) нужно применять повторно, пока не получится выражение, содержащее небольшие, легко выражаемые ЛО. Эти разложения, подобно предыдущим, можно рассматривать как некоторые принципы оптималь­ности.

Оценим сложность (число N(M) элементарных операций представления М × М-ЛО, получаемого последовательным разложением по строке или столбцу. Как видно из разложений (4.41), (4.42), N(М) удовлет­воряет разностному уравнению

где N(1) = Q. (4.45)

Решая уравнение (4.45) индукцией по М, находим

при (4.46)

Оценим также сложность Nr(M) представления М × M-ЛО, полученного последовательным разложением по совокупности r строк или r столбцов. При фиксированной совокупности Dr из r строк (совокупности Вr из r столбцов) имеется СrM различных миноров размера r × r и столько же соответствующих им логических дополнений размера в разложении (4.44) (разложении (4.43)). Таким образом, Nr (M) удовлет­воряет разностному уравнению