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

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

作　　者：李登信[1] 

机构地区：[1]重庆工商大学理学院,重庆400067

出　　处：《重庆工商大学学报（自然科学版）》2007年第3期215-217,共3页Journal of Chongqing Technology and Business University:Natural Science Edition

基　　金：重庆市自然科学基金项目(CSTC.2007BA2024)

摘　　要：设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.

关 键 词：欧拉生成子图 收缩 边数 

分 类 号：O157.5[理学—数学]