寻找欧拉生成子图最大边数的一个方法

A method to find maximum number of edges in a spanning Eulerian subgraph

设G是超欧拉图,X是G的子图.在G中,把X的点收缩为一个点vX,去掉X的边,得到G关于子图X的收缩,记为G/X.引入a—子图的概念,得到了若干a—子图,并表明如何利用a—子图来寻找欧拉生成子图的最大边数.

Suppose G is Eulerian graph,X is the subgraph of C,v,in G,the point of X is contracted to a point Uxv, if the edges of X are removed, the contraction of subgraph X of G is arrived at and is noted as G/X. The concept of α - subgraph is introduced, a lot of a - subgraphs are obtained accordingly. How to use α - subgraph to find maximum number of edges of spanning Eulerian subgraphs is demonstrated.