一个最小可行图的判定条件

A Criterion for a Minimum Feasible Graph

设有n个集合X_1,…,X_n,一个以X=U_(i=1)~nX_i为顶点集的图G称为是一个关于(X_1,…,X_n)的可行图,如果对每一个X_i(i=1,…,n),导出子图G_i=G[Xi]是连通的。关于集合序列(X_1,…,X_n),含最少边数的可行图称为是最小可行图。本文证明,关于(X_1,X_2,X_3)的可行图G=G_1∪G_2∪G_3是最小可行图的充分必要条件是:当X_i∩X_j∩X_k≠φ(i,j,k)=1,2,3)时,G_i∩G_j∩G_k是树。它发展了由D.-Z.Du(堵丁柱)在1986年得到的一个结果。

Given n set X_1,…,X_n, a graph G with the vertex set X=U_i^n=_1X_i Called feasible graph for (X_1,…,X_n)if, for each X_i (i=1,…,n), the induced subgrapl G_i=G[X_i] of G with the vertex set X_i is connected. A minimum feasible graph G for a set sequence (X_1,…,X_n,) is a feasible graph for (X_1,…,X_n) with minimal number of edges. In the paper we prove that a feasible graph G=G_1∪G_2∪G_3 for (X_1, X_2, X_3) is minimum if and only if G_i ∩G_j∩G_k are all trees for X_i∩X_j∩X_k≠ φ(i, j, k=1, 2, 3). It has extended a result proposed by D. -Z. Du(1986)[2].