运筹学方向讨论班
报告题目: Short cycle Structures of Graphs on Surfaces(1)—the Uniqueness Theory
报告人: 任韩 副教授;
单位: 华东师范大学数学系;
报告地点: 理科大楼A1510
时间: 3月15号（星期三）下午2:00-3:00
报告内容:
This is a talk about cycle space theory. Minimum cycle bases, or MCB in short, has been studied by many people and much work has been down. In theory, it is viewed as a source of matroid. As applications, cycle base theory has been used in electric circuit theory, structural analysis, chemical structure storage and biology field. Here, in this talk we shall present some basic combinatorial structures of cycles bases. After setting up a Hall type theorem for bases transformation, we give a sufficient and necessary condition for a collection of facial cycles to be contained in every MCB. We show that all MCB in a (weighted) graph have a unique structure, i.e., there is a 1-1 correspondence between any pair of MCB such that the corresponding elements have the same length(weight). This implies that if a MCB contains a k-cycle, then any other (possible ) MCB will also contains a k-cycle; further, any two MCB must have the same number of k-cycles for each integer k=3,4,…,n(=|VG)|). This extends P.F.Stadler’s and J.Leydold’s works on Halin graphs and outer-planar graphs, respectively. Since J.D.Horton proved that there is a polynomial time algorithm to find a MCB in a graph, this implies that the cycle structure in every
MCB can be determined in polynomial time.
欢迎大家光临！
