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

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

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

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

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

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

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

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

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

9、.隨機向量序列X,[Ran,G](X),[Ran,G]2(X),[Ran,G]3(X),…構(gòu)成一個齊次的馬爾可夫鏈。 13.兩個狀態(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,π]中的排列π用一個[n]上的字ξ