圖的確定一致性猜想.pdf

1、近30年以來圖論有了非常快速的發(fā)展，許多工程和應(yīng)用問題都可以適當(dāng)?shù)霓D(zhuǎn)換為圖論問題，并運用圖的理論及其算法對其進(jìn)行深入的討論和研究。在控制論領(lǐng)域，多智能體網(wǎng)絡(luò)中的節(jié)點與鄰節(jié)點間的信息互換通常用圖的理論來建模。多智能體網(wǎng)絡(luò)的一致性問題是近年來學(xué)者們研究的重點內(nèi)容之一，正是通過對多智能體網(wǎng)絡(luò)一致性問題的深入研究而提出了圖的確定一致性猜想。本文主要討論一些特殊的圖是否滿足確定一致性猜想。
　　首先研究了一些非常特殊的圖，如完全圖、樹等，確

2、定其滿足確定一致性猜想，然后討論了直徑與半徑滿足特定關(guān)系的圖，研究直徑與半徑在什么關(guān)系時該圖滿足確定一致性猜想。對于其它滿足確定一致性猜想的圖的研究難度相對較大，先討論了一些階數(shù)較低的圖，然后探討圖的一些運算對確定一致性猜想的影響。注意到所有的樹都滿足確定一致性猜想，我們以樹圖為基礎(chǔ)構(gòu)造了一類更廣泛的圖，并且證明了這類圖都滿足確定一致性猜想。
　　本文對圖的確定一致性猜想進(jìn)行的研究和探討，主要得到了以下結(jié)論：
　　首先，證明

3、了所有直徑等于兩倍半徑的圖都滿足確定一致性猜想；從階數(shù)較低的圖出發(fā)，證明了五個頂點及以下的所有連通圖都滿足確定一致性猜想。通過分別證明奇數(shù)和偶數(shù)多個頂點的路的情況，證明了所有的路都滿足確定一致性猜想。
　　其次，證明了如果圖G和H都滿足確定一致性猜想，那么G×H也滿足確定一致性猜想。證明了若H是圖G的連通生成子圖，且D(G)=D(H)，當(dāng)H滿足確定一致性猜想時，G也滿足確定一致性猜想。
　　最后，通過對于樹半徑的討論，證明了