k轨道任务分配问题的可解性条件:图论方法（英文）

发布时间：2018-02-08 23:28

本文关键词： k轨道任务分配 k内稳定集可解性图论方法矩阵的半张量积　出处：《控制理论与应用》2017年04期 　论文类型：期刊论文

【摘要】：将图论及一种新的数学分析工具——矩阵的半张量积(semi-tensor product of matrices,STP),作为研究工具,通过研究图的k内稳定集的充分必要条件,研究了k轨道任务分配问题的可解性条件.定义了图的顶点子集的特征向量,利用STP方法得到图的k内稳定集新的若干充分必要条件.基于这些新的充分必要条件,建立了能够搜索出图的所有k内稳定集的两种算法.进而将上述结果应用到k轨道任务分配问题,得到了该问题可解性的两个充分必要条件.此外,通过这些充分必要条件,也发现了一些有趣的现象.例如,完全最优方案(completely optimal schedules)的存在.
[Abstract]:The semi-tensor product of the matrix, a new mathematical analysis tool, is used as a tool to study the necessary and sufficient conditions for the k-inner-stable set of graphs. In this paper, the solvability conditions of k-orbit assignment problem are studied. The eigenvector of vertex subset of graph is defined. By using STP method, some sufficient and necessary conditions for the new set of k-internal stability of graph are obtained. Based on these new sufficient and necessary conditions, In this paper, two algorithms for finding all stable sets in k of graphs are established. Then, the above results are applied to k-orbit assignment problems, and two necessary and sufficient conditions for the solvability of the problem are obtained. In addition, through these sufficient and necessary conditions, we obtain two necessary and sufficient conditions for the solvability of the problem. Some interesting phenomena have also been found, such as the existence of complete optimal optimal scheduling.
【作者单位】：河南科技大学农业装备工程学院;南开大学计算机与控制工程学院;河南科技大学信息工程学院;
【基金】：Supported by Key Scientific Research Program of the Higher Education Institutions of Henan Educational Committee(15A416005) 2015 Science Foundation of Henan University of Science and Technology for Youths(2015QN016) National Natural Science Foundation of China(61573199) Sub-project of National Key Research and Development Program(2016YFD0700103 2)
【分类号】：O157.5

【相似文献】