The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. ...The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.展开更多
This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, usin...This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.展开更多
将图论及一种新的数学分析工具——矩阵的半张量积(semi-tensor product of matrices,STP),作为研究工具,通过研究图的k内稳定集的充分必要条件,研究了k轨道任务分配问题的可解性条件.定义了图的顶点子集的特征向量,利用STP方法得到图的...将图论及一种新的数学分析工具——矩阵的半张量积(semi-tensor product of matrices,STP),作为研究工具,通过研究图的k内稳定集的充分必要条件,研究了k轨道任务分配问题的可解性条件.定义了图的顶点子集的特征向量,利用STP方法得到图的k内稳定集新的若干充分必要条件.基于这些新的充分必要条件,建立了能够搜索出图的所有k内稳定集的两种算法.进而将上述结果应用到k轨道任务分配问题,得到了该问题可解性的两个充分必要条件.此外,通过这些充分必要条件,也发现了一些有趣的现象.例如,完全最优方案(completely optimal schedules)的存在.展开更多
Let R be a commutative ring with unity,M be a unitary R-module and F be a simple connected graph.We examine different equivalence relations on subsets A_(f)(M)\{0},A_(s)(M)\{0}and A_(t)(M)/{0}of M,where A_(f)(M)is the...Let R be a commutative ring with unity,M be a unitary R-module and F be a simple connected graph.We examine different equivalence relations on subsets A_(f)(M)\{0},A_(s)(M)\{0}and A_(t)(M)/{0}of M,where A_(f)(M)is the set of full-annihilators,A_(s)(M)is the set of semi-annihilators and A_(t)(M)is the set of star-annihilators in M.We prove that elements x,y∈M are neighborhood similar in the annihilating graph ann_(f)(Г(M))if and only if the submodules ann(x)M and ann(y)M of M are equal.We study the isomorphism of annihilating graphs arising from M and the tensor product M⊗_(R)T^(-1)R,where T=R/C(M),C(M)={r∈R|rm=O for some O≠m∈M}.展开更多
文摘The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.
基金This work was supported by the National Natural Science Foundation of China （Nos. G61374065, G61034007, G61374002） the Fund for the Taishan Scholar Project of Shandong Province, the Natural Science Foundation of Shandong Province （No. ZR2010FM013） the Scientific Research and Development Project of Shandong Provincial Education Department （No. J11LA01 ）
文摘This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.
基金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)+1 种基金National Natural Science Foundation of China(61573199)Sub-project of National Key Research and Development Program(2016YFD0700103–2)
文摘将图论及一种新的数学分析工具——矩阵的半张量积(semi-tensor product of matrices,STP),作为研究工具,通过研究图的k内稳定集的充分必要条件,研究了k轨道任务分配问题的可解性条件.定义了图的顶点子集的特征向量,利用STP方法得到图的k内稳定集新的若干充分必要条件.基于这些新的充分必要条件,建立了能够搜索出图的所有k内稳定集的两种算法.进而将上述结果应用到k轨道任务分配问题,得到了该问题可解性的两个充分必要条件.此外,通过这些充分必要条件,也发现了一些有趣的现象.例如,完全最优方案(completely optimal schedules)的存在.
文摘Let R be a commutative ring with unity,M be a unitary R-module and F be a simple connected graph.We examine different equivalence relations on subsets A_(f)(M)\{0},A_(s)(M)\{0}and A_(t)(M)/{0}of M,where A_(f)(M)is the set of full-annihilators,A_(s)(M)is the set of semi-annihilators and A_(t)(M)is the set of star-annihilators in M.We prove that elements x,y∈M are neighborhood similar in the annihilating graph ann_(f)(Г(M))if and only if the submodules ann(x)M and ann(y)M of M are equal.We study the isomorphism of annihilating graphs arising from M and the tensor product M⊗_(R)T^(-1)R,where T=R/C(M),C(M)={r∈R|rm=O for some O≠m∈M}.
