【摘要】：具有高度對稱性和很大圍長的圖在極圖理論、糾錯編碼理論、密碼學、網絡通信以及量子計算等各種不同的領域內具有重要應用。對于素數冪q和整數k≥2,1995年Lazebnik和Ustimenko利用李群的根系在[16]中提出了一個q-正則的代數二部圖D(k,q),它是邊傳遞的并且圍長不小于k+4.自提出以來,這個二部圖得到了廣泛的關注和研究,不但為一系列的極圖問題提供了最佳的上界或下界估計,也為具有優(yōu)異糾錯性能的LDPC碼提供了一種很好的構造方法,還可以用來設計快速的對稱密碼算法和公鑰密碼算法。本學位論文進一步研究二部圖D(k,q)的性質,給出了其中的路徑的顯式表達公式,證明了關于其圍長的一個猜想在幾種新的情形下的正確性,提出了D(k,q)的一個新的推廣Γ(Ω,q),深入討論了推廣的二部圖Γ[Ω,q)的連通分支數、路徑及其表示、白同構、對稱性和圍長。我們首先給出了二部圖D(k,q)的一個等價構造Λki,q研究了F∞上的三個線性變換σ、τ和δ的一些性質,討論了它們在Fq上的多項式的唯一表示問題。然后我們利用這些線性變換改寫了二部圖Λk,q。的鄰接關系,得到了Λk,q中的路徑上的頂點之間的一個遞推關系。進一步我們還利用齊次多項式ρs(w1,w2,…,wn),給出了Λk,中始于全零向量的路徑上的各頂點用所經過的頂點的顏色(第一個坐標)表示的顯式表達公式。特別,當這樣的路徑上的屬于同一頂點集合的相鄰頂點的顏色之差取定值時,我們計算了路徑上各項點的所有坐標,并由此證明了關于D(k,q)的圍長的猜想A：對所有的奇數k≥3和素數冪q≥4,D(k,q)的圍長等于k+5.在(k+5)／2為有限域Fq的特征的冪時是成立的。為了進一步研究猜想A,我們又給出了二項式系數在有限域Fq中的一個推廣其中b為Fq*中的一個h階元素,s mod h表示使得h整除s-s mod h的最小非負整數。我們得到了關于推廣的二項式系數θb(k,s)的一系列恒等式。進一步,利用這些恒等式我們計算了當路徑上的屬于同一頂點集合的相鄰頂點的顏色差為等比數列時從全零向量出發(fā)可以到達的頂點的坐標,并由此證明了猜想A在(k+5)／2為有限域F。的特征的冪與q-1的因子的乘積時是成立的。這是當前關于猜想A的最好研究結果。通過將頂點向量除顏色以外的各分量以二元序列集合Ω中的元素來標記的方法,我們還提出了一類新的二部圖Γ[Ω,q)：頂點集L(Ω)和R(Ω)皆為Fq上的|Ω|+1長序列的集合,[l]∈L(Ω)和〈r〉∈R(Ω)在Γ[Ω,q)中鄰接當且僅當lα0+rα0=r*lα,若α0∈Ω: lβ1+rβ1=l*rβ,若β1∈Ω,這里*是一個不在Q中的一個特別的符號,l*和r*表示頂點的顏色,并且規(guī)定*0=*1=η為空序列。二部圖Γ[Ω,q)是二部圖D(k,q)的一種推廣。首先我們給出了二部圖Γ[Ω,q)的連通分支上的一些不變量：若α與其逆序序列α互異并且都包含于Ω,則存在一個在Γ[Ω,q)的連通分支上不變的量α(·.,α).并且這些不變量在不同的連通分支上是可以自由取值的。由此我們得到Γ[Ω,q)的連通分支數的一個下界。然后,我們給出了Γ[Ω,q)的一些自同構,得到了Γ[Ω,q)具有不同層次的對稱性所需滿足的一些充分條件。特別,我們給出了Γ[Ω,q)是邊傳遞的二部圖的,一個條件：如果對Ω中任何二元序列,刪除其第一個比特或最后一個比特或兩個連續(xù)的相同比特中的一個比特所得到的序列仍在Q中,則二部圖Γ[Ω,q)是邊傳遞的。我們還對Γ[Ω,q)的始于除顏色以外各坐標都等于零的頂點的路徑進行了研究,得到了這樣的路徑上的各頂點用所經過的頂點的顏色表示的顯式表達公式。進一步,我們利用這些表達式,證明了Γ[Ω,q)中的一些特殊環(huán)的不存在性。最后,我們得到了Γ[Ω,q)的圍長的一些下界估計。特別,除了連通分支數的準確值以外,關于Γ[Ω,q)中的這些研究結果都可推出有關D(k,q)的最佳結果。
[Abstract]:......
【學位授予單位】：揚州大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：O157.5

【相似文獻】

相關期刊論文 前10條

1 馮文麗,原軍;一類度極大的非哈密爾頓簡單平衡二部圖[J];華北工學院學報;2003年05期

2 王秀英,劉春峰;關于二部圖是可跡的一個注記[J];吉林師范大學學報(自然科學版);2005年03期

3 卞秋香;孫志人;;二部圖的四圈覆蓋[J];江蘇科技大學學報(自然科學版);2005年06期

4 劉春峰;佟紹成;;關于二部圖圈的一個結果[J];科學技術與工程;2007年08期

5 王洪偉;;二部圖匹配強迫數的譜[J];山東大學學報(理學版);2009年12期

6 閔安共;;二部圖的兩個判定方法及性質[J];廊坊師范學院學報(自然科學版);2010年01期

7 喬誠;王勤;;導出匹配可擴二部圖度和條件的改進[J];中國計量學院學報;2010年01期

8 張國志;王世英;;飽和二部圖[J];晉中學院學報;2010年03期

9 王文虎;楊雨;;二部圖的所有極大匹配[J];電腦開發(fā)與應用;2011年08期

10 宋曉奎;李秀平;;二部圖的匹配的簡單應用[J];邢臺學院學報;2012年04期

相關會議論文 前3條

1 常迎香;;一類無完美匹配的二部圖[A];中國運籌學會第七屆學術交流會論文集（中卷）[C];2004年

2 李小強;張寧;;基于鄰接矩陣的二部圖的判定方法[A];第五屆全國復雜網絡學術會議論文（摘要）匯集[C];2009年

3 吳宏林;劉紹明;;基于二部圖最大匹配的漢日詞對齊[A];內容計算的研究與應用前沿——第九屆全國計算語言學學術會議論文集[C];2007年

相關博士學位論文 前8條

1 成曉燕;關于一類代數二部圖的研究[D];揚州大學;2015年

2 孫靜;二部圖參數與圈型結構研究[D];華中師范大學;2014年

3 王洪偉;二部圖的匹配強迫數[D];蘭州大學;2008年

4 邊紅;圖中的若干極值問題[D];廈門大學;2008年

5 馬麗;素數冪與2倍素數冪階局部本原圖[D];云南大學;2012年

6 葉萌;圖張開及其在互極大圖與互極大理想圖中的應用[D];上海交通大學;2013年

7 劉賽華;若干圖類的κ-共振問題的研究[D];蘭州大學;2010年

8 呂華眾;圖的條件匹配排除問題的計算復雜性和平衡超立方圖的若干網絡性質[D];蘭州大學;2013年

相關碩士學位論文 前10條

1 王雅靜;基于二部圖網絡的協(xié)同過濾推薦算法研究[D];燕山大學;2015年

2 韓路;基于核心圖的標簽傳播社團劃分算法[D];南京信息工程大學;2015年

3 王玉玲;匹配的anti-Ramsey數的若干研究[D];浙江師范大學;2015年

4 李熠;引入信任的二部圖電子商務個性化推薦算法改進研究[D];電子科技大學;2015年

5 鄭連江;圖的關聯能量[D];上海大學;2015年

6 沈富強;無符號拉普拉斯特征值的界[D];上海理工大學;2013年

7 孫曉萌;基于社團劃分和加權二部圖網絡的個性化推薦算法研究[D];河北工業(yè)大學;2015年

8 陸瑋佳;關于一類具有較大圍長的代數二部圖的研究[D];揚州大學;2015年

9 楊立保;兩個二部圖設計到其子圖設計的變化[D];河北師范大學;2016年

10 鄭延春;二部圖的彩虹匹配問題[D];山東大學;2016年

，

本文編號：2332650