学术交流
位置: 首页 > 学术交流 > 正文

吕长虹: A bridge between the double resolving problem of graphs and the coin-weighing problem

时间:2024-04-11来源:数学学院

报告时间:2024年4月13日(星期六)15:00

报告地点:翡翠湖校区科教楼B1710室

:吕长虹 教授

工作单位:华东师范大学

举办单位:数学学院

报告简介

图G的顶点子集S称为图G的2-分辨集(Double resolving set), 如果G中任意两个顶点u, v都能在S中找到两个顶点x, y满足:x到u的距离与x到v的距离之差不等于y到u的距离与y到v的距离之差。2-分辨集的概念最初仅仅是Caceres 等人为了研究分辨集问题(resolving set problem)作为研究工具提出的一个新概念。硬币称重问题(Coin-weighing problems)是个古老的组合优化问题,其中一个经典形式为:给定n个硬币,假定真硬币的重量和假硬币的重量均已知,用弹簧称对硬币进行称重,用最少的称重次数将所有的假币找出来。硬币称重问题已经得到很多学者广泛地研究。

我们证明了超方体的2-分辨集问题与硬币称重问题的等价关系,我们利用硬币称重问题上著名的Lindström算法给出超方体2-分辨集问题的一些新结果,包括解决公开问题;超方体的2-分辨集问题的图论结果反过来也提供了硬币称重问题的一些新进展。

报告人简介

吕长虹,华东师范大学数学科学学院教授,院长,国家高层次人才计划入选者,主要从事图论和离散优化方面理论和应用研究。 2020年获得上海市科技进步特等奖和萧树铁应用数学奖,2021年获CSIAM首届数学落地成果奖和华为优秀技术成果奖。现为中国数学会常务理事、中国工业与应用数学常务理事、上海市工业与应用数学学会副理事长等。


关闭

Baidu
sogou