計(jì)算機(jī)模擬與圖上的離散動(dòng)力系統(tǒng).pdf

1、本論文的主要研究對(duì)象是幾類無向圖上或有向圖上的離散動(dòng)力系統(tǒng)。首先我們介紹無向圖上的貫序動(dòng)力系統(tǒng)(SDS)的概念，它由以下幾個(gè)要素構(gòu)成：(1)一個(gè)有限的，用1,2,……,n頂點(diǎn)標(biāo)號(hào)的無向圖G，每個(gè)頂點(diǎn)都有一個(gè)狀態(tài)，設(shè)這些狀態(tài)屬于某個(gè)數(shù)域D；(2)對(duì)應(yīng)圖中的每一個(gè)頂點(diǎn)i,1≤i≤n,都有一個(gè)函數(shù)E,G：Dn→Dn；(3)n階置換群Sn中的一個(gè)排列π。函數(shù)Fi,G根據(jù)第i個(gè)頂點(diǎn)自身的狀態(tài)和它鄰點(diǎn)的狀態(tài)來決定i點(diǎn)被更新后的狀態(tài)，而并不改變其它頂

2、點(diǎn)的狀態(tài)。排列π表示圖中各點(diǎn)被更新的前后順序。把函數(shù)Fi,G按照π的順序復(fù)合起來，就得到了一個(gè)圖G上的貫序動(dòng)力系統(tǒng)(SDS)： [F,G,π]=Fπ1,GFπ2,G…Fπn,G：Dn→Dn。 對(duì)于其它幾類離散動(dòng)力系統(tǒng)：無向圖上的并序動(dòng)力系統(tǒng)(PDS)，有向圖上的貫序動(dòng)力系統(tǒng)(SDS)，有向圖上的線性貫序動(dòng)力系統(tǒng)(LSDS)，無向圖上的隨機(jī)并序動(dòng)力系統(tǒng)(RPDS)和無向圖上的字貫序動(dòng)力系統(tǒng)(SDSW)，其定義可以類似地給出

3、。 論文總共由五章構(gòu)成。 第一章為介紹部分，陳述了課題的背景并給出了一些定義、符號(hào)及已知的結(jié)果。 第二章研究了四種無向圖上的離散動(dòng)力系統(tǒng)：OR-PDS[OR,G]，OR-SDS[OR,G,π]，NOR-PDS[NOR,G]和NOR-SDS[NOR,G,π]。對(duì)每一個(gè)研究對(duì)象，都用一個(gè)等價(jià)的引理去表示它在狀態(tài)向量上的作用。這種等價(jià)性在于每個(gè)狀態(tài)向量都和一個(gè)圖的頂點(diǎn)子集一一對(duì)應(yīng)。事實(shí)表明，這種方法在研究動(dòng)力系統(tǒng)的性質(zhì)

4、方面是實(shí)用的和有效的。這章的主要目的是用圖的結(jié)構(gòu)性質(zhì)來刻畫動(dòng)力系統(tǒng)本身所具有的屬性。這章的主要結(jié)果有： 1.動(dòng)力系統(tǒng)PDS[OR,G]的寬度等于圖G的直徑。 2.動(dòng)力系統(tǒng)PDS[NOR,G]的寬度等于1。 3.動(dòng)力系統(tǒng)PDS[NOR,G]的每一個(gè)軌道(即有限圈)都是2長的。 4.在動(dòng)力系統(tǒng)PDS[NOR,G]的像圖中，狀態(tài)(0,0,…,0)具有極大的入度，且此入度值等于圖G的控制集個(gè)數(shù)。 5.對(duì)于

5、任意的排列π∈Sn，動(dòng)力系統(tǒng)SDS[OR,G,π]的寬度不超過圖G的直徑；而且，存在一個(gè)排列σ∈Sn使得SDS[OR,G,σ]的寬度等于圖G的直徑。 6.動(dòng)力系統(tǒng)SDS[NOR,G,π]的寬度等于1。 7.動(dòng)力系統(tǒng)SDS[NOR,G,π]的周期點(diǎn)和圖G的獨(dú)立集之間是一一對(duì)應(yīng)的。第三章主要研究有向圖上的線性貫序動(dòng)力系統(tǒng)(LSDS)。我們首先介紹了一種矩陣方法，它可以處理一般的線性貫序動(dòng)力系統(tǒng)，這里的“一般”是指頂點(diǎn)狀態(tài)屬于

6、一般的代數(shù)，局部函數(shù)是任意的線性函數(shù)。接著，我們研究布爾代數(shù)上的、以O(shè)R為局部函數(shù)的線性貫序動(dòng)力系統(tǒng)的性質(zhì)。這類動(dòng)力系統(tǒng)被稱為有向圖D上的OR-SDS，記作[OR,D,π]。布爾矩陣?yán)碚撛谟懻撝衅鸬搅朔浅ｊP(guān)鍵的作用。最后對(duì)另一種有向圖上的線性貫序動(dòng)力系統(tǒng)，PAR-SDS，也做了一些討論。這章的主要結(jié)果有： 8.下面四個(gè)結(jié)論互相等價(jià)：(a)D中不包含有向圈。(b)存在整數(shù)m≥1使得[OR,D,π]m(X)=(0,0,…,0)對(duì)任意

7、X∈Fn2都成立。(c)像圖Γ[OR,D,π]是連通的。(d)FIX[OR,D,π]=FIX[OR,D,π]∪PER[OR,D,π]={(0,0,…,0))。 9.下面五個(gè)結(jié)論互相等價(jià)：(a)動(dòng)力系統(tǒng)[OR,D,π]是可逆的。(b)動(dòng)力系統(tǒng)[OR,D,π]是恒等映射。(c)像圖Γ[OR,D,π]是頂點(diǎn)不交的有向圈的并。(d)像圖Γ[OR,D,π]是2n個(gè)環(huán)的并。(e)圖D是n個(gè)環(huán)的并。 10.對(duì)任意的X≠(0,0,…,0

8、)，存在整數(shù)m≥1使得[OR,D,π]m(X)=(1,1,…,1)當(dāng)且僅當(dāng)圖D是強(qiáng)連通的并且滿足條件(◇)。 11.動(dòng)力系統(tǒng)[PAR,D,π]是可逆的當(dāng)且僅當(dāng)圖D的每個(gè)頂點(diǎn)都有自環(huán)。在論文的第四章中，我們構(gòu)造了一種無向圖上的隨機(jī)并序動(dòng)力系統(tǒng)(RPDS)[Ran,G]。證明了由RPDS[Ran,G]誘導(dǎo)出的狀態(tài)序列是一個(gè)齊次的馬爾可夫鏈。同時(shí)還得到了兩個(gè)狀態(tài)向量在RPDS的作用下互達(dá)的充分必要條件。這章的主要結(jié)果有： 12

9、.隨機(jī)向量序列X,[Ran,G](X),[Ran,G]2(X),[Ran,G]3(X),…構(gòu)成一個(gè)齊次的馬爾可夫鏈。 13.兩個(gè)狀態(tài)向量I=(i1,i2,…,in)∈Fn2和J=(j1,j2,…,jn)∈Fn2在由RPDS[Ran,G]誘導(dǎo)出的馬爾可夫鏈中互達(dá)當(dāng)且僅當(dāng)存在整數(shù)k使得(I,J)和(J,I)在圖Gk中都是適應(yīng)的。 論文的最后一章討論了SDS的另一種推廣形式。把SDS[F.G,π]中的排列π用一個(gè)[n]上的字ξ