关于路立方图的一个充要条件

A necessary and sufficient condition on the cube of path

在有向图中,哈密尔顿图一定是强连通图,但强连通图不一定是哈密尔顿图,本文证明了一类具有偶数阶的路立方图的任何定向,通过推点运算,可推成哈密尔顿有向图,当且仅当可推成强连通有向图.

It is generally known that,Hamiltonian digraph must be strong connected digraph,on the contrary,it doesn′t work.This paper will prove that an orientation of the cube of a path with even order can be made strong using the push vertex operation,if and only if it can be made Hamiltonian using the push operation.