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

报告时间：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首届数学落地成果奖和华为优秀技术成果奖。现为中国数学会常务理事、中国工业与应用数学常务理事、上海市工业与应用数学学会副理事长等。