张新鸿，薛彩娟

（太原科技大学 应用科学学院，山西 太原 030024）

0 引言

1962年，Ore提出了图的控制集这一概念[1]，近年来，越来越多的学者们对控制集进行了研究，图的控制理论得到迅速的发展，并广泛应用于通信网络、信息学等多方面，相关结论可以参看文献[2-9]。

设D是一个具有n个顶点的有向图，常记为D=(V，A)，其中V和A分别表示有向图D的顶点集和弧集。有向图控制集的研究可参看文献[10-13]。有向图D的阶表示D中顶点的数目，记为|D|。如果uv是一条弧，那么称u控制v（或v被u控制），记为u→v。对于V(D)中不交的顶点子集X和Y，X→Y表示X中的每一个顶点控制Y中的每一个顶点。定义

即(Y，X)D表示尾在Y中，头在X中的弧集。X⇒Y表示(Y，X)D=∅。X↦Y表示X→Y和X⇒Y同时成立。给定有向图D=(V，A)，对于顶点集T⊆V(D)，如果对每个顶点v∈V(D)T，至少存在一个顶点t∈T，使得tv∈A(D)，那么称T是有向图D的一个控制集[14]，其中所含顶点个数最少的控制集称为D的最小控制集。

设v∈V(D)，定义集合，分别称集合和为顶点v的外邻集和内邻集。是以v为尾的所有弧的数目，称为顶点v的外度是以v为头的所有弧的数目，称为顶点v的内度。设V(H)⊆V(D)，A(H)⊆A(D)，如果两个端点都在V(H)中的每一条弧都属于A(H)，则称H是由X=V(H)导出的，记为，也称H为D的一个导出子图。如果对于D的每一对不同的顶点x和y，总存在一条(x，y)途径和(y，x)途径，那么称有向图D是强连通的。

无2圈的有向图称为定向图，任意两个顶点均相邻的定向图称为竞赛图。定向图以及竞赛图的相关研究参看文献[15-16]。每一对不同的顶点都相邻的简单图称为无向完全图[17]。无向完全图的双定向图称为半完全有向图。……