采用线性不定方程组的Hamiltonian存在判定条件

Necessary and Sufficient Conditions for Hamiltonian Based on Linear Diophantine Equations

本文基于{0，1}线性不定方程组和顶边关联矩阵．提出了一个基于无向Hamiltonian图的充要判定定理。并证明了满足该定理的不定方程组解向量对应给定圄的Hamiltonian回路中边的集合，本文还推导出两个可以基于矩阵秩的Hamiltonian回路存在的必要判据。

A necessary and sufficient condition is presented for the Hamiltonian cycle problem in simple undirected graph with linear Diophantine equation, which is based on the incidence matrix. It is proved that the solution set of the Diophantine equation with a {0, 1 } vector is with respect to the edges of Hamiltonian cycle in a given graph. Based on the given necessary and sufficient condition, two necessary conditions for a graph having a Hamiltonian cycle are given by determining the rank of the matrix.