学术报告通知
题目：
Digital Door Lock and De Bruijn graphs
报告人：
Sergey Kitaev (University of Strathclyde)
时间：
5月21日（周四） 下午3：00
地点：
博理楼B108
摘要：
This presentation introduces de Bruijn cycles and graphs through motivating applications and fundamental concepts from graph theory. After reviewing key notions such as directed paths, connectivity, balanced graphs, and Eulerian cycles, it explains how de Bruijn sequences arise as shortest strings containing all binary words of a fixed length exactly once. The core idea is to construct de Bruijn graphs, whose structure guarantees the existence of Eulerian cycles, thereby proving the existence of such sequences. The correspondence between paths in these graphs and words is highlighted, along with the extension to k-ary alphabets. The talk concludes with a practical application to digital door locks, demonstrating how de Bruijn cycles drastically reduce the number of required inputs, illustrating both theoretical elegance and real-world relevance.
简介：
Kitaev 教授的研究兴趣涉及组合数学和图论及其应用的各个方面，已在《Journal of Combinatorial Theory, Series A》等期刊发表140 余篇论文，并著有专著《Patterns in Permutations and Words》、《Words and Graphs》。现任《Journal of Combinatorial Theory, Series A》和《Proceedings of the Edinburgh Mathematical Society》 编委。
目的地搜索