最小連通傳感器覆蓋及其相關(guān)問題

覆蓋問題是在無線傳感網(wǎng)絡(luò)研究中的重要課題。在自2015年1月1日至2018年12月31日期間，在本項基金的支持下，我們對于傳感器覆蓋問題按照申請書的計劃做了系統(tǒng)的研究，同時我們對社交網(wǎng)絡(luò)的若干熱點展開了初步研究探討。在傳感器覆蓋上，我們研究了邊界覆蓋的質(zhì)量以及安全性，有向傳感器網(wǎng)絡(luò)中弱柵欄覆蓋構(gòu)建，全視角強柵欄覆蓋，基于迭代加權(quán)虛擬力算法的DSNs覆蓋，等等。在社交網(wǎng)絡(luò)上，我們研究了關(guān)于影響力最大化的Bharathi-Kempe-Salek猜想，謊言傳播的阻斷問題，社區(qū)劃分等核心問題。在這些研究中，我們獲得了許多成果。利用這些成果完成了總計41篇論文，其中34篇刊出在雜志，7篇發(fā)表在會議文集。特別是，有12篇發(fā)表在SCI/SCIE類雜志里，有4篇論文發(fā)表在CCF A類的雜志和會議文集里。

無線傳感器已廣泛應(yīng)用于交通管制、環(huán)境監(jiān)測、災(zāi)難預(yù)警、農(nóng)田管理、戰(zhàn)場指揮等經(jīng)濟活動及人類生活的各種領(lǐng)域。這些應(yīng)用都離不開目標(biāo)覆蓋問題（Coverage Problem）。給出一組目標(biāo)點或者一個目標(biāo)區(qū)域，找出一組傳感器使得它們的感知范圍覆蓋所有的目標(biāo)點或者整個目標(biāo)區(qū)域。這是關(guān)于無線傳感器的一個基本問題。本項目是對最小連通傳感器覆蓋等 NP 難度優(yōu)化問題的多項式時間近似算法的設(shè)計與分析。所選出的問題理論難度大，應(yīng)用背景強。因此，研究結(jié)果對算法理論與無線傳感器網(wǎng)絡(luò)技術(shù)的發(fā)展均有重要意義。

1954年，Tutte教授在研究四色問題時，引進(jìn)了整數(shù)流的概念。四色定理等價于任何平面圖有處處非零4流。后來人們發(fā)現(xiàn)整數(shù)流問題與圈覆蓋等圖論問題有緊密的關(guān)系。1992年, Jaeger教授將整數(shù)流的概念推廣為群連通度(group connectivity），群著色 (group coloring)作為群連通度的對偶提出來。群連通度本身在研究整數(shù)流時，有應(yīng)用價值。Thomassen在1986年提出任何4-邊連通的線圖是Hamilton的。任何超歐拉圖的線圖是Hamilton的。因此，超歐拉圖對研究Thomassen這個猜想有應(yīng)用價值。超歐拉圖、Hamilton圈的研究 本身就是子圖的存在性問題。本項目的主要內(nèi)容是：研究群連通度及相關(guān)問題， 包括群著色、3-流問題等；研究子圖的存在性, 包括線圖Hamilton性、超歐拉圖等；作為子圖存在性的應(yīng)用，研究算法的容錯性。

本項目主要研究圖論中整數(shù)流、群連通度問題、歐拉子圖的存在即網(wǎng)絡(luò)容錯性及相關(guān)問題，它包括圖的處處非零的3-流問題、群連通度（Group connectivity）、 群著色問題及相關(guān)問題。 著名數(shù)學(xué)家Tutte教授（1954）提出的3-流猜想(Bondy和Murty的《Graph with applications》中未解決問題48):任何4-邊連通圖有非零3-流: 法國數(shù)學(xué)家 Jeager教授(1992) 把整數(shù)流問題推廣到群連通度問題。而群著色問題作為群連通問題的對偶問題提出來的。 平面圖的染色是與平面上的整數(shù)流等價。因此， 整數(shù)流問題、群連通問題和染色問題是圖論研究的主流問題之一。 我們對對這些問題進(jìn)行深入、系統(tǒng)的研究，取的一批重要成果。我們刻畫了度條件與群連通性、 度系列與群連通性、禁用子圖與群連通性、平面圖的群著色。因為平面上整數(shù)流的問題和染色問題是等價的， 因此我們研究了平面圖的著色以及強邊著色等問題。我們還研究了線圖的Hamilton性、度條件與歐拉連通子圖的存在性, 因子的存在性和網(wǎng)絡(luò)的容錯性等問題。 2100433B