Мультиграф и задача о лягушках.

[loldop]

Пусть дан ориентированный мультиграф $\mathbb{G}$
Пусть дана матрица смежности $A \in R^{n \times n}$.
Матрица смежности такова, что:
элемент $a_{ij}$ есть количество ребер, исходящих из $i \rightarrow j$

Теперь сама задача:
Есть болото.
В нем на кочках сидят лягушки. Между некоторыми кочками расстояние таково, что лягушки могут его преодолеть, но в два прыжка. Т.е. можно сказать, что существуют "промежуточные" кочки. Однако ни на основные, ни на промежуточные кочки не могут вставать одновременно две лягушки.
Вопрос:
Смогут ли лягушки из состояния "A" переместиться в состояние "Б"?

Хотелось бы услышать возможные догадки, рекомендации и что-нибудь полезное для прочтения.

Возможное решение:
Зададим начальное и конечное положение лягушек через код:
Пусть имеется $n$ вершин и $m$ лягушек. ( $m \leq n$ ).
Тогда, начальное положение можно закодировать так:
$b_1, b_2, \cdots b_m$, где $b_i \in \{1..n\}$.

Т.е. лягушка $i$ располагалась на месте(кочке) $b_i$.
Аналогично и с конечным расположением:
$c_1, c_2, \cdots c_m$, где $c_i \in \{1..n\}$

Теперь будем исследовать матрицу смежности на возможность перехода из начального в конечное состояние.
Интуитивно понятно, что:
1) Если у вершины исходящая или входящая степень равны нулю, а на ней сидела какая-то лягушка, то эта лягушка либо может только покинуть эту кочку, либо не поменяться вовсе. (Соответствующая строка или столбец - нулевые).
2) Если определитель матрицы $| A | = 1$, то, если количество лягушек совпадает с количеством кочек, то возможен только циклический сдвиг их местоположения.

Далее, более интересные выкладки.

Соответствующий минор $A^{ij}$, состоящий из элементов, стоящих на $i-j$ строке и в $i-j$ столбце, полностью описывает переход вершин $i и j$ друг в друга.
Соответствующий минор $A^{k_i,..,k_m}$ описывает переходы вершин (лягушек) между этими вершинами ${k_i,..,k_m}$.

Если воспользоваться такой формулой:
\mathbb{I}_{a_i \neq 0} - индикатор ненулевой строки $a_i$.
\overline{\mathbb{I}} = \sum\limits_{i=1}^n \mathbb{I}_{a_i \neq 0}
$E = diag\{1\} \in R^{n \times n}$

$ Fm = \frac{\sum\limits_{i=1}^{n}E\cdot a_i}{\overline{\mathbb{I}}} $

$Fm > 1$, то возможен циклические сдвиги и перестановки лягушек .
$Fm = 1$, то возможны только циклические сдвиги лягушек.
$Fm < 1$, то невозможны циклические сдвиги лягушек.

Жду критики:) Желательно конструктивно и с обилием литературы recommened for solution :)

[loldop]

Была допущена ошибка:

$Fm = \frac{\sum\limits_{i=1}^n 1 \cdot E \cdot a_i}{\overline{\mathbb{I}}}$

Где $1 \in R^{1 \times n} $ - вектор единиц.

[mag1K_]

С формулой все понятно мы можем определить какие переходы у нас возможны и достижимость вершин.
Но что делать дальше когда мы получили что Fm > 1 и нужные нам вершины доступны. Значит ли это что ответ задачи будет "да, переход лягушек возможен" или нужны еще проверки? и количество лягушек нам не важно?нельзя ли использовать различные алгоритмы обходов графа?

-- 26.03.2012, 14:12 --

индикатор ненулевной строки это 0 в случае нулевой и 1 в противном?) тогда разве Fm может получится <1 ?