關(guān)于無重復(fù)分解產(chǎn)生樹的定理
ON THE THEOREMS OF GENERATION OF TREES BY DECOMPOSITION WITHOUT DUPLICATIONS
-
摘要: 本文定義了一種二分圖,稱之為互補(bǔ)劃分圖。利用此圖容易證明有關(guān)互補(bǔ)劃分的定理,并可得到一個(gè)判別是否是本性互補(bǔ)劃分的較弱的條件。
-
關(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. -
W. K. Chen, IEEE Trans. on CT, CT-16(1969), 518.[3]W. K. Chen, Applied Graph Theory, 2nd ed., North-Holland, Amsterdam,. 1976.[4]F. Haray著,李慰萱譯,圖論,上海科學(xué)技術(shù)出版社,1980年. -
計(jì)量
- 文章訪問數(shù): 1589
- HTML全文瀏覽量: 134
- PDF下載量: 348
- 被引次數(shù): 0