ГЛАВА 2
МАТЕМАТИЧЕСКИЕ СЕЙФЫ НА ГРАФАХ
(ЗАМКИ С ДВУМЯ СОСТОЯНИЯМИ)
2.1. Постановка задачи
Общая задача о математическом сейфе была сформулирована в [1].
Задача. Математическим сейфом называется система S(Z, b,), состоящая из множества замков Z = {z1, z2, . . . , zN}, вектора состояний сейфа b,где - состояние i - го замка, и множества , . В результате одного поворота ключом по часовой стрелке в замке zl все замки переходят из состояния в состояние . Сейф считается открытым, если он находится в состоянии . Необходимо найти для каждого замка такое количество поворотов ключем, чтобы открыть сейф.
Вектор будем называть решением задачи о сейфе. Множество называется множеством инцидентности. Его можно записать в виде матрицы инцидентности размером , где на главной диагонали стоят нули, а , если принадлежит множеству , и нулю в противном случае. Очевидно, что x поворотов ключом в замке zl по часовой стрелке равносильно kl - x поворотам против часовой стрелки. Матрице можно поставить в соответствие ориентированный граф , в котором из вершины в вершину входит дуга, если . В зависимости от сложности этой матрицы возникают различные задачи о математическом сейфе. Обозначим , где единичная матрица. В столбце этой матрицы, соответствующему j-у замку, стоят единицы против тех замков, которые влияют на состояние j-го замка. Учитывая количество всех поворотов в этих замках и число поворотов xj в данном замке, получим суммарное число поворотов, которое произошло в j-м замке. В сумме с начальным состоянием j-го замка это должно привести к 0(mod kj). Тогда общая задача о сейфе сводится к решению системы линейных сравнений:
(2.1)
где - i - й столбец матрицы А.
Предполагается, что начальное положение сейфа B известно, или, по крайней мере, его можно легко вычислить. Если для всех , то такие замки называются однотипными.
Из самой постановки задачи вытекает, что реализация решения задачи не зависит от порядка поворота ключом в замках. Поэтому, в зависимости от типа решаемой задачи, мы будем приводить примеры, в которых последовательности поворотов ключей будут различаться.
Рассмотрим решение задачи для простейших графов. Будем считать графы связными, иначе можно рассматривать каждую компоненту графа независимо. Введем обозначения. Пусть в ориентированном графе , который соответствует матрице , и обозначают число выходящих дуг из вершины z (соответственно число входящих в вершину z). Тогда степень вершины z будет . Если для всех вершин графа , что равносильно O, то все замки изолированы, и задача решается для каждого замка независимо от других. Поэтому будем считать, что всегда для всех . Случай представляет всевозможные паросочетания замков, решение для которых ввиду однозначности не представляет интереса.
2.2. Решение задачи для простейших ориентированных графов
Рассмотрим задачу с однотипными замками для самого простого случая K=2, то есть . Рассмотрим следующее ограничение .
В этом случае каждая компонента графа представляет собой либо цепь, либо цикл с произвольно ориентированными ребрами. Решение будем находить отдельно для каждой компоненты.
Пример 2.1. Пусть несколько вершин графа образуют цепь, в которой все ребра ориентированы в одном направлении, то есть цепь образует путь (рис.2.1).
Занумеруем его вершины от 1 до N, начиная с вершины, не имеющей входящей дуги. Номера вершин указаны в кружочках, а под ними указаны состояния замков (вершин).
Рис.2.1. Компонента - путь из N вершин
Положим i=1. Если , то переходим к вершине . Если , то делаем поворот в замке , переводя его состояние в 0, а переходит в состояние . Теперь переходим к вершине . В конце концов приходим к вершине N, состояние которой переводим в . В результате для всей компоненты получим состояния . Можно подсчитать количество операций (поворотов ключа), которое при этом выполнялось. Для этого выделим в векторе компоненты, состоящие из последовательных единиц. Совокупность компонент, содержащих единиц, обозначим . Аналогично обозначим совокупность компонент вектора , содержащих последовательных нулей. Тогда разобьётся на непересекающиеся множества
~ (2.2)
где и могут быть и пустыми. Пусть
(2.3)
Выделим в (2.2) те множества , для которых . Очевидно, что проделав операций, можно превратить эти состояния в нулевые.
Удалим из (2.2) все такие множества, а соседние нулевые множества объединим. У нас останутся множества, содержащие лишь нечетное число единиц . С помощью операций можно добиться, чтобы замков перешли в состояние 0. Удалим эти состояния из (2.2), а оставшиеся множества (обозначим их одной буквой), содержащие только одну единицу, перенумеруем.
(2.4)
где , или , или могут быть пустыми. Начиная с единицы и заканчивая единицей за операций переводим все состояния в 0. Затем то же самое делаем с множеством состояний, начиная с и заканчивая и т. д. Если , то процесс заканчивается на единице . Если , то начиная с до вершины N включительно переводим все состояния замков в положение 0. Это равносильно тому, что существует фиктивный замок , для которого
В любом случае общее число операций будет равно
.
Цепи, у которых рёбра ориентированы произвольно, представляют собой набор путей, у которых ориентация чередуется. Другими словами, каждые два соседних пути имеют общую вершину, в которой они либо сходятся, либо начинаются. Вершины, общие для двух путей, поочерёдно имеют степени , или . Начиная операции переключения с вершин, у которых , постепенно переводим вершины всей цепи в состояние 0.
Рассмотрим теперь циклы. Если ориентация рёбер в них не одностор