应萃英学院和数学与统计学院邀请，奥地利维也纳技术大学Herbert Fleischner教授为萃英班学生作报告。 欢迎广大师生参加！

题 目：What is the Chinese postman doing in the mazes of the imperial gardens of Vienna/Paris/Beijing?

时 间：7月6日（星期五）下午3:30

地 点：齐云楼911多媒体报告厅

Abstract：One of the origins of graph theory is an 18th century problem of mathematical entertainment: The Seven Bridges of Konigsberg, where the problem was to walk across the bridges precisely once (within the City limits of course). Leonhard Euler showed that such a walk is not possible because of the way the bridges were placed! More than a hundred years later, Hierholzer, a young German mathematician, showed how to produce a closed covering walk in a connected graph with even degree vertices only (called eulerian graphs today), such that every edge is traversed precisely once. Such a walk is called an eulerian trail. These two problems are closely related. In this talk I discuss various types of closed covering walks such as double tracings, postman tours, but also traversals of mazes where one has only local information at every vertex without knowing the whole graph. Finding such walks always amounts to constructing eulerian trails in eulerian graphs obtained from the given graphs by doubling certain edges.

Herbert Fleischner教授简介：

国际著名的图论专家，欧拉图研究和双圈覆盖等方面的最重要专家之一。解决过Erdos提出的100美元奖金猜想， 有名的结果有2连通图的平方是哈密尔顿的等。到目前为止，已经发表SCI论文90余篇，其中有7篇发表在图论的重要杂志《 Journal of Combinatorial Theory, Series B》上。他的关于欧拉图方面的著作《Eulerian graphs and related topics》是图论的重要著作之一。

萃英学院

数学与统计学院

二〇一二年七月五日