Полином гамильтонового цикла

В математике полином гамильтонова цикла n × n -матрицы представляет собой многочлен в ее элементах, определяемый как

$\operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}$

где $H_{n}$ представляет собой множество n - перестановок, имеющих ровно один цикл.

Это алгебраический вариант, полезный в ряде случаев для определения существования гамильтонова цикла в ориентированном графе .

Это обобщение количества гамильтоновых циклов орграфа как суммы произведений весов дуг его гамильтоновых циклов (все из которых равны единице) для взвешенных орграфов с весами дуг, взятыми из данного коммутативного кольца. В то же время для неориентированного взвешенного графа сумма произведений весов ребер его гамильтоновых циклов, содержащих любое фиксированное ребро ( i , j ), может быть выражена как произведение веса ( i , j ) и гамильтонова цикла полином матрицы, полученной из ее взвешенной матрицы смежности путем подвергания ее строк и столбцов любому перестановочному отображению i в 1 и j в 2 , а затем удаления ее 1 -й строки и 2 -го столбца.

В ( Кнежевич и Коэн (2017) ) было показано, что

$\operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(-A_{J})\operatorname {per} (A_{\bar {J}})$

где $A_{J}$ является подматрицей $A$ индуцированные строками и столбцами $A$ индексируется $J$, и ${\bar {J}}$ является дополнением $J$ в $\{1,\dots ,n\}$, а определитель пустой подматрицы равен 1.

Благодаря этому и тождествам Борхардта для неособой n × n матрицы Коши размера $C(x,y)$ $\operatorname {ham} (C(x,y))={\det }(-D_{1}^{2}C^{*2}(x,y)D_{2}^{2}+I_{/1})\operatorname {det} (C(x,y))$ где $D_{1},D_{2}$ являются диагональными матрицами, которые составляют $D_{1}C(x,y)D_{2}$ унитарный (в вещественном поле или поле конечной характеристики, или ортогональный в поле комплексных чисел), $C^{*2}(x,y)$ является квадратом Адамара (по входу) $C(x,y)$, и $I_{/1}$ — единичная n × n -матрица с заменой элементов индексов 1,1 на 0.

В поле характеристики 2 справедливо равенство $\operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(-A_{J})\operatorname {per} (A_{\bar {J}})$ превращается в $\operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\det(A_{\bar {J}})$ что, следовательно, дает возможность за полиномиальное время вычислить полином гамильтонова цикла любой унитарной матрицы $U$ (т.е. такой, что $U^{T}U=I$ где $I$ — единичная n × n -матрица), поскольку в таком поле каждый минор унитарной матрицы совпадает со своим алгебраическим дополнением: $\operatorname {ham} (U)={\det }^{2}(U+I_{/1})$ где $I_{/1}$ представляет собой тождественную n × n -матрицу с заменой индексов 1,1 на 0. Следовательно, если возможно за полиномиальное время присвоить веса из поля характеристики 2 дугам орграфа, которые делают его взвешенную матрицу смежности унитарной и имеющей ненулевой полином гамильтонова цикла, то орграф является гамильтоновым. Следовательно, задача гамильтонова цикла вычислима на таких графах за полиномиальное время.

В характеристике 2 полином гамильтонова цикла матрицы размера n × n равен нулю, если n > 2k, где k - ее ранг, или если он инволютивен и n > 2.

Кроме того, в произвольном кольце $R$ характеристика которого не является четным натуральным числом, для любой кососимметричной n × n -матрицы $A$ существует степенной ряд по формальной переменной $\varepsilon$ $U(\varepsilon )=\sum _{n=0}^{\infty }U_{n}\varepsilon ^{n}$ такая, что это унитарная матрица размера n × n над $R\left(\varepsilon \right)$ и $U_{0}=I$, $U_{1}=A$, в то время как для любого $U(\varepsilon )$ удовлетворяющие этим условиям $\operatorname {ham} (A)$ равен коэффициенту при $n$-я степень $\varepsilon$ в степенном ряду $\operatorname {ham} (U(\varepsilon ))$. И для любого кольца $R$ четной характеристики то же самое верно, когда диагональ $AA^{T}$ кратно 2. Это означает, что вычисления с точностью до $n$-я степень $\varepsilon$, гамильтонов цикловый полином унитарной n × n -матрицы над бесконечным расширением любого кольца характеристики q (не обязательно простого) с помощью формальной переменной $\varepsilon$ это # $_{q}$P-полная задача, если $q$ не равно 2 и вычисляем гамильтонов полином цикла $k$-полуунитарная матрица (т.е. n × n -матрица $V$ такой, что $\operatorname {rank} (V^{T}V-I\,)=k$) над таким расширением любого кольца характеристики 2 является # $_{2}$P-полная задача для любого $k$ > 0 (поскольку любой $k$-полуунитарную матрицу можно получить из унитарной матрицы удалением $k$ ряды и $k$ столбцы). Для $k=1$ последнее утверждение можно переформулировать как # $_{2}$P-полнота вычислений для заданной унитарной n × n -матрицы $U$ над полем характеристики 2 n × n -матрица $H(U)$ чья i , j -я запись является полиномом гамильтонова цикла матрицы, полученной из $U$ подвергая его строки и столбцы любому перестановочному отображению j в 1 и i в 2 , а затем удаляя его 1 -ю строку и 2 -й столбец (т. е. сумму произведений весов дуг соответствующих гамильтоновых путей взвешенного орграфа из вершины i в вершину j ) для i ≠ j и ноль для i знак равно j . Эта матрица удовлетворяет матричному уравнению $U(H(U))^{T}=H(U)U^{T}$, пока $\operatorname {ham} \left({\begin{matrix}U&{Ua}\\a^{T}&1\end{matrix}}\right)=(a_{1}^{2}+...+a_{n}^{2})\operatorname {ham} (U)$ где $a$ — произвольный n-вектор (что можно интерпретировать как полиномиальную вычислимость гамильтонова циклового многочлена любой 1-полуунитарной m × m -матрицы $A$ такой, что $AA^{T}=I+bb^{T}$ где $b$ это $m$-й столбец $A$ с его $m$-я запись заменена на 0 и $I$ — тождественная m × m -матрица).

Кроме того, стоило бы отметить, что в характеристике 2 гамильтонов цикловый полином обладает своими инвариантными матричными сжатиями (частично аналогичными инвариантной для определителя гауссовой модификации), учитывая тот факт, что $\operatorname {ham} (X)=0$ для любой t × t -матрицы $X$ имеющий три равных ряда или, если $t$ > 2 — пара индексов i,j такая, что ее i-я и j-я строки совпадают, а также i-й и j-й столбцы.

Следовательно, если матрица имеет две равные строки с индексами i и j, то добавление одной из них к любой третьей не меняет этот полином в характеристике 2, что позволяет по принципу Гаусса исключить все элементы ее i -го столбца, кроме i-го столбца. , i -й и j , i -ый (в случае, если они не равны нулю) и удаляем его i -й столбец и j -ю строку (описанным выше способом) – тогда гамильтонов циклический полином исходной матрицы равен этому полиному нового, умноженному на начальный j , i -й элемент.

Также в характеристике 2 и для матриц с более чем двумя строками полином гамильтонова цикла не изменяется добавлением i -го столбца к j -му столбцу в матрице, где i -я и j -я строки идентичны, что, в частности, дает тождество

$\det(D+D^{-1})\operatorname {ham} \left({\begin{matrix}V&A\\B&U\end{matrix}}\right)=\operatorname {ham} \left({\begin{matrix}V&V+D&A\\V+D^{-1}&V+D^{-1}+D&A\\B&B&U\end{matrix}}\right)$

для n × n -матрицы $U$, m × m -матрицы $V$ и диагональ $D$, m × n -матрица $A$ и n × m -матрица $B$.

Ограничение этого тождества на случай, когда $U$ является унитарным, $VD+DV^{T}+AA^{T}=I+D^{2}$ и $BD=UA^{T}$, где $I$ является единичной m × m -матрицей, делает (2 m + n ) × (2 m + n )-матрицу в правой части равенства унитарной, а ее гамильтонов цикл полиномиально вычислимым, следовательно, за полиномиальное время, что, следовательно, обобщает вышеизложенное: данная формула для гамильтонова циклического полинома унитарной матрицы. Кроме того, в характеристике 2 для квадратных матриц X, Y $\operatorname {ham} \left({\begin{matrix}X&Y\\Y&X\end{matrix}}\right)$ — это квадрат суммы по всем парам неравных индексов i,j i,j-го элемента Y, умноженной на гамильтонов цикловый полином матрицы, полученной от X+Y удалением ее i -го элемента строку и j -й столбец (описанным выше способом). Следовательно, подставив приведенные выше равенства A = B и U = V, мы получим еще одно расширение класса унитарных матриц, в которых гамильтонов цикловый полином вычислим за полиномиальное время.

Помимо упомянутых выше преобразований сжатия, в характеристике 2 справедливо также следующее соотношение для гамильтоновых цикловых полиномов матрицы и ее частичной обратной (при $A_{11}$ и $A_{22}$ будучи квадратным, $A_{11}$ обратимый ) :

$\operatorname {ham} \left({\begin{matrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{matrix}}\right)={\det }^{2}\left(A_{11}\right)\operatorname {ham} \left({\begin{matrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}+A_{21}A_{11}^{-1}A_{12}\end{matrix}}\right)$

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

Следовательно, существует множество операторов матричного сжатия, выполняемых за полиномиальное время и сохраняющих полином гамильтонова цикла в характеристике 2, последовательное применение которых вместе с транспонирующим преобразованием (используемым каждый раз, когда операторы оставляют матрицу нетронутой), имеет для каждой матрицы определенный предел, который можно определить как оператор сжатия-закрытия. Таким образом, при применении к классам матриц этот оператор отображает один класс в другой. Как было доказано в ( Knezevic & Cohen (2017) ), если сжатие-замыкание класса унитарных матриц содержит подмножество, где вычисление этого полинома равно # $_{2}$P-полный , то полином гамильтонова цикла вычислим за полиномиальное время над любым полем этой характеристики, что влечет за собой равенство RP = NP .

Ссылки

• Кнежевич, Анна; Коэн, Грег (2017), Некоторые факты о перманентах в конечных характеристиках , arXiv : 1710.01783 , Бибкод : 2017arXiv171001783K .

• Коган, Григорий (1996). «Вычисление перманентов по полям характеристики 3: где и почему это становится трудным». Материалы 37-й конференции по основам информатики . стр. 108–114. дои : 10.1109/SFCS.1996.548469 . ISBN  0-8186-7594-2 . S2CID   39024286 . {{cite book}}: CS1 maint: дата и год ( ссылка )

• Коэн, Грег (2010), Новый алгебраический метод вычисления за полиномиальное время числа по модулю 2 гамильтоновых разложений и подобных разделов набора ребер графа , arXiv : 1005.2281 , Bibcode : 2010arXiv1005.2281C