圖的確定一致性猜想.pdf

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

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

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