摘要:
本文定义了一种二分图,称之为互补划分图。利用此图容易证明有关互补划分的定理,并可得到一个判别是否是本性互补划分的较弱的条件。
Abstract:
A complementary partitive graph is a bipartite graph G(V , V; E) with disjoint vertex sets V , V, and an edge set E such that all edges are directed except only one edge, say j=[x, y], is undireeted, and the outgoing degrees are d+(x)=0, d+(y)=0 and d+(v)=1 for all vx, y. The following assertions can be easily proved: If G(v' , V; E) is a complementary partitive graph with undireeted edge j, then a pair of eomple mentary partitions P' (E) and P(E) with respect to j can be constructed by the edges incident with each vertex of V' and each vertex of V'' . Conversely, if Hk has a complementary partition with respect to j, then a complementary partitive graph can be constructed. by using the complementary partiive graph defined above. We can ease the proofs of theorems of complementary partitions established by W. K. chen (1969, 1976) and give a simple criterion to determine whether or not a complementary partition is essential as follows: Theorem A complementary partition is essential if and only if the corresponding complementary partitive graph is a connected graph.