摘要:
本文定義了一種二分圖,稱之為互補劃分圖。利用此圖容易證明有關(guān)互補劃分的定理,并可得到一個判別是否是本性互補劃分的較弱的條件。
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.