%0 Journal Article
%T k轨道任务分配问题的可解性条件: 图论方法<br>Solvability of k--track assignment problem: a graph approach
%A 岳菊梅
%A 陈增强
%A 闫永义
%A 金鑫
%J 控制理论与应用
%D 2017
%R 10.7641/CTA.2017.16033
%X 将图论及一种新的数学分析工具–—矩阵的半张量积(semi-tensor product of matrices, STP), 作为研究工具,通过研究图的k内稳定集的充分必要条件, 研究了k轨道任务分配问题的可解性条件. 定义了图的顶点子集的特征向量, 利用STP方法得到图的k内稳定集新的若干充分必要条件. 基于这些新的充分必要条件, 建立了能够搜索出图的所有k内稳定集的两种算法. 进而将上述结果应用到k轨道任务分配问题, 得到了该问题可解性的两个充分必要条件. 此外, 通过这些充分必要条件, 也发现了一些有趣的现象. 例如, 完全最优方案(completely optimal schedules)的存在.<br>The theory of graph and a new mathematical analysis tool, semi-tensor product (STP) of matrices are applied to consider the solvability conditions of k--track assignment problem by investigating the necessary and sufficient conditions of k--internally stable sets of graphs (k--ISS). By defining characteristic vectors for vertex subsets of graphs and using the STP, several new necessary and sufficient conditions of k--ISS are obtained, based on which two algorithms able to find all the k--ISSs of a graph are established. The results obtained are further applied to the k--track assignment problem, and two necessary and sufficient conditions of the solvability of the problem are proposed; also some interesting phenomena such as completely optimal schedules are discovered by the new method.
%K k轨道任务分配 k内稳定集 可解性 图论方法 矩阵的半张量积&lt
%K br&gt
%K k--track assignment k--internally stable set solvability graph method semi-tensor product of matrices
%U http://jcta.alljournals.ac.cn/cta_cn/ch/reader/view_abstract.aspx?file_no=20170406&flag=1