| 词条 | Edge cycle cover |
| 释义 |
In mathematics, an edge cycle cover (sometimes called simply cycle cover[1]) of a graph is a family of cycles which are subgraphs of G and contain all edges of G. If the cycles of the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover. In this case the set of the cycles constitutes a spanning subgraph of G. If the cycles of the cover have no edges in common, the cover is called edge-disjoint or simply disjoint cycle cover. Properties and applicationsMinimum-Weight Cycle CoverFor a weighted graph, the Minimum-Weight Cycle Cover Problem (MWCCP) is the problem to find a cycle cover with minimal sum of weights of edges in all cycles of the cover. For bridgeless planar graphs the MWCCP can be solved in polynomial time. [2] Cycle k-coverA cycle k-cover of a graph is a family of cycles which cover every edge of G exactly k times. It has been proven that every bridgeless graph has cycle k-cover for any integer even integer k≥4. For k=2, it is the well-known cycle double cover conjecture is an open problem in graph theory. The cycle double cover conjecture states that in every bridgeless graph there exists a set of cycles that together cover every edge of the graph twice.[3] See also
References1. ^Cun-Quan Zhang, Integer flows and cycle covers of graphs, Marcel Dekker,1997. 2. ^"Handbook in Graph Theory" (2004) {{isbn|1-58488-090-2}}, [https://books.google.com/books?id=mKkIGIea_BkC&pg=PA225&lpg=PA225&dq=%22minimum+weight+cycle+cover%22&source=web&ots=VV2JRTVXzz&sig=RPtrYtXXqDFPfXv0OrX0gqLs8GE&hl=en&sa=X&oi=book_result&resnum=8&ct=result#PPA225,M1 p. 225] 3. ^"The Cycle Double Cover Conjecture" 2 : Graph theory objects|Combinatorial optimization |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。