分数Hamilton圈与分数树形图

FRACTIONAL HAMILTONIAN CYCLES AND FRACTIONAL ARBORESCENCES

定义有向图的分数有向Hamilton圈和分数支撑树形图 ,讨论分数Hamilton圈、分数旅行售货员问题和分数支撑树形图基于线性规划的等价定义及多项式时间算法 .

We give the definitions of fractional directed Hamiltonian cycles and fractional spanning arborescences of a directed graph,and investigate the equivalent definitions of fractional Hamiltonian cycles,travelling salesman problem and spanning arborescences based on LP and their polynomial algorithms.