最小连通传感器覆盖及其相关问题

覆盖问题是在无线传感网络研究中的重要课题。在自2015年1月1日至2018年12月31日期间，在本项基金的支持下，我们对于传感器覆盖问题按照申请书的计划做了系统的研究，同时我们对社交网络的若干热点展开了初步研究探讨。在传感器覆盖上，我们研究了边界覆盖的质量以及安全性，有向传感器网络中弱栅栏覆盖构建，全视角强栅栏覆盖，基于迭代加权虚拟力算法的DSNs覆盖，等等。在社交网络上，我们研究了关于影响力最大化的Bharathi-Kempe-Salek猜想，谎言传播的阻断问题，社区划分等核心问题。在这些研究中，我们获得了许多成果。利用这些成果完成了总计41篇论文，其中34篇刊出在杂志，7篇发表在会议文集。特别是，有12篇发表在SCI/SCIE类杂志里，有4篇论文发表在CCF A类的杂志和会议文集里。

无线传感器已广泛应用于交通管制、环境监测、灾难预警、农田管理、战场指挥等经济活动及人类生活的各种领域。这些应用都离不开目标覆盖问题（Coverage Problem）。给出一组目标点或者一个目标区域，找出一组传感器使得它们的感知范围覆盖所有的目标点或者整个目标区域。这是关于无线传感器的一个基本问题。本项目是对最小连通传感器覆盖等 NP 难度优化问题的多项式时间近似算法的设计与分析。所选出的问题理论难度大，应用背景强。因此，研究结果对算法理论与无线传感器网络技术的发展均有重要意义。

1954年，Tutte教授在研究四色问题时，引进了整数流的概念。四色定理等价于任何平面图有处处非零4流。后来人们发现整数流问题与圈覆盖等图论问题有紧密的关系。1992年, Jaeger教授将整数流的概念推广为群连通度(group connectivity），群着色 (group coloring)作为群连通度的对偶提出来。群连通度本身在研究整数流时，有应用价值。Thomassen在1986年提出任何4-边连通的线图是Hamilton的。任何超欧拉图的线图是Hamilton的。因此，超欧拉图对研究Thomassen这个猜想有应用价值。超欧拉图、Hamilton圈的研究 本身就是子图的存在性问题。本项目的主要内容是：研究群连通度及相关问题， 包括群着色、3-流问题等；研究子图的存在性, 包括线图Hamilton性、超欧拉图等；作为子图存在性的应用，研究算法的容错性。

本项目主要研究图论中整数流、群连通度问题、欧拉子图的存在即网络容错性及相关问题，它包括图的处处非零的3-流问题、群连通度（Group connectivity）、 群着色问题及相关问题。 著名数学家Tutte教授（1954）提出的3-流猜想(Bondy和Murty的《Graph with applications》中未解决问题48):任何4-边连通图有非零3-流: 法国数学家 Jeager教授(1992) 把整数流问题推广到群连通度问题。而群着色问题作为群连通问题的对偶问题提出来的。 平面图的染色是与平面上的整数流等价。因此， 整数流问题、群连通问题和染色问题是图论研究的主流问题之一。 我们对对这些问题进行深入、系统的研究，取的一批重要成果。我们刻画了度条件与群连通性、 度系列与群连通性、禁用子图与群连通性、平面图的群着色。因为平面上整数流的问题和染色问题是等价的， 因此我们研究了平面图的着色以及强边着色等问题。我们还研究了线图的Hamilton性、度条件与欧拉连通子图的存在性, 因子的存在性和网络的容错性等问题。 2100433B