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

Теперь задача состоит в том, чтобы восстановить ре­шение по найденным матрицам. Рассмотрим элемент (v1, v7) последней матрицы (VV')2·V. Этот элемент яв­ляется единичным. Найдем возможные ненулевые эле­менты первой строки матрицы (VV′)2, которые при умно­жении на седьмой столбец v давали бы единичное значе­ние рассматриваемого элемента. Одним из таких эле­ментов является (1, 4), элемент в первой строке и четвертом столбце матрицы (VV′)2, так как элемент (4, 7) матрицы V также является единичным. Другим эле­ментом V с таким же свойством является (5,7). Выберем первый из названных элементов. Таким образом, полу­чаем, что последний переход есть v4→ v7. Далее смот­рим, каким способом мог получиться единичный элемент (1, 4) матрицы (VV′)2. Проверив первую строку (VV")×V и четвертый столбец V′, получаем, что рассматривае­мый единичный элемент есть результат наличия ненуле­вого элемента (6, 4) в матрице V′ (так как соответству­ющий элемент матрицы (VV')·V также отличен от нуля). Таким образом, предпоследний переход есть v6 → v4. Снова проверяем причину наличия ненулевого элемента (6, 1) матрицы (VV')-V. Находим, что он об­разован единичными элементами (2, 1) в матрице W и (2, 6) в матрице V. Таким образом, третий от конца переход есть v2→v6. Аналогично находим, что четвер­тый и пятый от конца переходы v3→v2 и v1→v3 соот­ветственно. Вся результирующая совокупность перехо­дов есть v1→v3, v3→v2, v2-→v6, v6→v4, v4→v7 или в более простом виде: v1, v3, v2, v6, v4 и v7. В принципе можно было бы найти другие допустимые переходы.

Дадим словесную интерпретацию полученного реше­ния. Так как v3 есть (2, 0), оба людоеда должны пере­правиться одновременно, причем один из них должен вернуться (из-за v2). Затем вернувшийся людоед дол­жен высадиться, а два миссионера должны занять ме­сто в лодке. После причаливания к правому берегу один из миссионеров должен высадиться (чтобы получить v6), а другой вернуться обратно, чтобы получить v4. Наконец, последний миссионер и людоед переправляют­ся вместе на правый берег. При этом достигается ко­нечное состояние v7.

Упражнение 15. Состояния системы в задаче о трех миссионе­рах и трех людоедах, когда умеют грести все три миссионера и толь­ко один людоед, можно представить тройкой (т, r, с), где 0≤т≤3, 0≤r≤l и 0≤с≤2, причем т соответствует миссионерам, r — умею­щему грести людоеду и с — двум остальным людоедам. В этом слу­чае существует 16 возможных состояний системы. Запишите матрицу переходов системы.

Чтобы определить существование решения без ис­пользования всех процедур, необходимых для его факти­ческого получения, воспользуемся следующим методом.

Заметим, что решение должно иметь вид (VV')m×V. Пусть начальное состояние системы соответствует вершине v1, а конечное — вершине vk. Тогда, если реше­ние существует, то можно найти т такое, что элемент (1, k) матрицы (VV')m·V оказывается ненулевым. Как было показано выше, чтобы этот элемент был равен единице, необходимо существование, по крайней мере, одного ненулевого элемента в первой строке матрицы (VV')m, соответствующего ненулевому элементу в k-м столбце матрицы V. Таким образом, задача сводится к определению ненулевых элементов первой строки матрицы (VV')m для любой степени т. Это уже существен­но более простая задача даже при очень больших мат­рицах. Пусть множество {va, vb, ..., vc} состоит из вер­шин, соответствующих единичным элементам первой строки матрицы (VV'). В эти вершины можно попасть из вершины f[ за один круговой проход. Добавим к это­му множеству все вершины, которым соответствуют еди­ничные элементы в а-й, b-й, ..., с-й строке матрицы VV′. Новое расширенное множество содержит вершины, в которые можно попасть из v1 за два круговых прохо­да. Будем повторять такой процесс расширения для всех новых вершин множества до тех пор, пока не пере­берем всех вершин множества. Множество, полученное в результате такого процесса, состоит из всех вершин, в ко­торые можно попасть из v1 за произвольное число кру­говых проходов. Если это множество содержит верши­ны, которым соответствуют ненулевые элементы в k-м столбце матрицы V, то исходная задача имеет решение. В противном случае решение не существует.

Рассмотрим в качестве примера задачу с четырьмя миссионерами и четырьмя людоедами. Пусть вершины графа (число миссионеров, число людоедов)

Задача состоит в том, чтобы перейти из v1 в v13:

В 13-м столбце элементы v8, v11 и v12 не равны нулю. Следовательно, если задача имеет решение, то элемен­ты v8, v11 и v12 первой строки матрицы (VV')m также должы быть ненулевыми:

Множество вершин, в которые можно попасть из v1 состоит из { v1 v2}. Из v2 можно попасть в v1, v2 и v3. Поэтому добавим v3 к первоначальному множеству и получим расширенное множество

{v1, v2, v3}. Из v3 мож­но попасть в v2, v3, v4 и v6. Вводя новые вершины, полу­чим множество {v1, v2, v3, v4, v6}. Из v4 можно перейти в v3 и v4. Оба эти перехода не изменяют множества. На этом все возможности исчерпаны. Следовательно, из v1 можно попасть только в v1, v2, v3, v4 и v6 и нельзя по­пасть в v5, v7, v8, v9, v10, v11, v12, v13 ни при каком числе круговых проходов. Но в 13-м столбце матрицы V не­нулевыми являются только элементы v8, v11 и v12. Так как ни один из этих элементов не вошел в окончатель­ное множество, можно сделать вывод, что исходная за­дача не имеет решения.

Замечание. Матрица переходов (булева) может использоваться также для представления ориентирован­ного графа, соответствующего постулатам на множестве состояний Е1, Е2, ..., Еп, которые задают соотношения типа Ei→Ej. Заметим, что постулат Ei→Ei всегда вы­полняется. Возведя исходную матрицу в квадрат, мы получим новую матрицу, каждый единичный элемент которой указывает либо постулат, либо утверждение, доказываемое за 2 шага, например,

Е6→Е7, Е7→Е10 вместе означают E6→Ei0. Единичные элементы матри­цы, являющейся третьей степенью исходной, указывают постулаты или утверждения, которые могут быть дока­заны за 2 или за 3 шага. Наконец, (п—1)-я степень показывает все утверждения. Возникает за­дача нахождения наименьшего числа постулатов, из ко­торых можно вывести заданное множество утвержде­ний. Заметим, что существует, по крайней мере, 2n мно­жеств эквивалентных постулатов, позволяющих полу­чить п теорем.

Упражнение 16. Показать, что общее число матриц размером n×n, элементы которых принимают значения 0 или 1, а все диаго­нальные элементы единичные, равно .

5.11. Задача деления треугольника

Допустим, что мы разделили треугольник ABC на не­сколько треугольников меньшего размера, проводя п линий, параллельных его сторонам (рис. 5.25, где n= 2).

Рис. 5.25.

Расставим буквы А, В и С в точках пересечения ли­ний со сторонами следующим образом: точки на стороне ВС могут помечаться только бук­вами В, С (но не А), точки на сторонах АС и АВ помечают­ся по аналогичному правилу. Точки, находящиеся внутри большого треугольника, могут помечаться любой из трех букв. Требуется показать, что число маленьких треугольников, вершины которых по­мечены разными буквами, нечетно.

Для доказательства припишем символ нуль всем от­резкам с одинаково помеченными граничными точками и символ 1 — отрезкам с разными пометками. Сумма символов ребер для любого треугольника ABC равна 3. Для всех других треугольников эта сумма равна 0 или 2. Легко проверить, что сумма символов, соответствую­щих отрезкам каждой стороны большого треугольника, должна быть нечетной. Сумма символов по всем сторонам всех маленьких треугольников должна быть не­четной, так как все внутренние отрезки считаются дваж­ды. Следовательно, число треугольников (маленьких) с суммой символов сторон 3 оказывается нечетным.