• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      七點(diǎn)七邊圖的圖分解

      2021-08-19 06:13:04袁蘭黨楊立保谷麗彥白占立
      關(guān)鍵詞:區(qū)組河北師范大學(xué)同構(gòu)

      袁蘭黨,楊立保,谷麗彥,白占立

      (1.河北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,河北省數(shù)學(xué)研究中心,河北 石家莊 050024;2.邢臺學(xué)院 數(shù)學(xué)科學(xué)技術(shù)學(xué)院,河北 邢臺 054001;3.河北師范大學(xué) 學(xué)報(bào)編輯部,河北 石家莊 050024)

      1 概念和主要結(jié)構(gòu)

      組合設(shè)計(jì)是組合數(shù)學(xué)中的一個(gè)重要分支,主要研究滿足不同條件的構(gòu)造的存在性,廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、編碼密碼中.圖分解是傳統(tǒng)的區(qū)組設(shè)計(jì)的推廣,是將區(qū)組設(shè)計(jì)中完全圖推廣到有限簡單圖,其內(nèi)容更加豐富,應(yīng)用范圍也更廣泛.關(guān)于圖分解的研究有幾十年了,代表性文章參見文獻(xiàn)[1-6],其中分別給出了星圖K1,k、圈圖Cn和六點(diǎn)八邊圖的圖分解存在譜.本文旨在研究2個(gè)七點(diǎn)七邊圖的圖分解,是將多重完全圖分解為若干個(gè)兩兩不相交且同構(gòu)的七點(diǎn)七邊圖的并,確定圖分解的存在譜.先介紹相關(guān)的基本概念[5]和主要結(jié)構(gòu).

      設(shè)λKv是頂點(diǎn)集為X的v階λ重完全圖.有限簡單圖G=(V,E)的圖分解是圖λKv的邊分解B(稱為區(qū)組集),其中B中的元素是Kv的子圖且與G同構(gòu).該圖分解記為G-GDλ(v)=(X,B).顯然,G-GDλ(v)存在的必要條件為

      v≥|V(G)|,λv(v-1)≡0(mod2|E|),λ(v-1)≡0(modd),

      (1)

      其中,d是V中各頂點(diǎn)的度的最大公因數(shù).

      有限簡單圖G的帶洞圖分解是圖λKn,n,…,n的邊分解A(稱為區(qū)組集),其中A中的元素稱為區(qū)組是Kn,n,…,n的子圖且與G同構(gòu).該帶洞圖分解記為G-HD(nt)=(X,H,A),其中H={Xi|i=1,2,…,t}為洞集合.特殊地,若λ重完全(v+1)部圖λK1,1,…,1,w亦可拆分為與G同構(gòu)的圖,則稱其為洞長為w的不完全G-分解,記為G-IDλ(v+w,w).易見,G-GDλ(v+1)為G-IDλ(v+1,1).當(dāng)λ=1時(shí),以上記號中的下標(biāo)λ通常省略.

      本文研究2個(gè)含C5的七點(diǎn)七邊圖Di(1≤i≤2)的圖分解(圖1,圖2),這些圖的頂點(diǎn)標(biāo)記為(a,b,c,d,e,f,g).

      圖1 七點(diǎn)七邊圖D1Fig.1 Graph with seven vertices and seven edges D1

      圖2 七點(diǎn)七邊圖D2Fig 2.Graph with seven vertices and seven edges D2

      由式(1),對于1≤i≤2,Di-GDλ(v)存在的必要條件為λv(v-1)≡0(mod 14),v≥7,即當(dāng)λ≡1,2,3,4,5,6(mod 7)時(shí),v≡0,1(mod 7);當(dāng)λ≡0(mod 7)時(shí),v≥7.

      將證明圖分解Di-GDλ(v)(1≤i≤2)存在的必要條件也是充分的,從而給出圖分解的存在譜.易見,對任意λ,μ∈Z+,若G-GDλ(v)存在,則G-GDλμ(v)存在.因此,只需分別討論λ=1,7的情形.

      引理1[5]設(shè)G是有限簡單圖,h、t、λ是正整數(shù),w≥0.若存在G-HDλ(ht),G-IDλ(h+w,w)和G-GDλ(h+w),則存在G-GDλ(th+w).

      2 HDs、IDs和GDs的構(gòu)造

      圖分解是經(jīng)典的區(qū)組設(shè)計(jì)的推廣,區(qū)組設(shè)計(jì)中常用的差方法可以推廣應(yīng)用于圖分解的構(gòu)造.

      設(shè)X是v階可交換群,G=(S,E)為有限簡單圖,點(diǎn)集S是集合X的子集合,λ為給定的正整數(shù),若X中任意一個(gè)非零元g,都有λ個(gè)序?qū),y∈S,{x,y}∈E,使得g=x-y,則稱G為Abel群X的一個(gè)(v,G,λ)-差圖.特別地,當(dāng)X是循環(huán)群時(shí),則稱G為群X的一個(gè)(v,G,λ)-循環(huán)差圖.進(jìn)一步,對a∈X,定義G的一個(gè)平移G+a={x+a|x∈S},又令DevG={G+a|a∈X},則(X,DevG)為圖分解G-GDλ(v).

      設(shè)X是v階可交換群,G為有限簡單圖,設(shè)s是正整數(shù).再設(shè)S是由s個(gè)與圖G同構(gòu)的圖G1,G2,…,Gs組成的圖族,這里,Gi=(Si,Ei),Si?X,i=1,2,…,s,若X中任意非零元g都恰有λ次表成如下形式的差:g=bij-bil,1≤i≤s,bij,bil∈Si,{bij,bil}∈Ei,i=1,2,…,s,則稱S為群X的一個(gè)(v,G,λ)-差圖族.特別地,當(dāng)X是循環(huán)群時(shí),則稱S為群X的一個(gè)(v,G,λ)-循環(huán)差圖族.進(jìn)一步,對a∈X,定義G的一個(gè)平移Gi+a={x+a|x∈Si},進(jìn)而令DevS={Gi+a|i=1,2,…,s,a∈X},則(X,DevS)為圖分解G-GDλ(v).

      類似地,差圖或差圖族亦可用來構(gòu)造帶洞圖分解和不完全圖分解.

      在本文中,構(gòu)作各類圖分解時(shí)用到的集合Zv通常為v階循環(huán)群,并記DevS:=Smodv.

      例:對于圖D1來說,B:(0,4,9,3,1,7,8)mod 15即為集合Z15上D1-GD(15)的區(qū)組集.

      引理2對于1≤i≤2,存在Di-HD(7t),t≥3.

      因此,只需構(gòu)作Di-HD(7k),k∈{3,4,5,6,8},便可得到Di-HD(7t),t≥3.

      k=3:X=Z21,H={{3j+i:j∈Z7}|i∈Z3},mod 21.

      D1:(20,1,17,4,0,8,10);D2:(17,1,20,0,4,13,10).

      k=4:X=Z7×(Z3∪{∞}),H={Z7×{x}|x∈Z3∪{∞}},mod(7,3).

      D1:(00,42,01,12,1∞,2∞,20),(40,41,62,50,1∞,22,61);

      D2:(01,42,00,1∞,12,5∞,20),(41,62,50,1∞,40,31,61).

      k=5:X=Z35,H={{5j+i:j∈Z7}|i∈Z5},mod 35.

      D1:(1,27,16,12,0,20,3),(16,30,8,2,0,13,27);

      D2:(16,27,1,0,12,8,3),(30,8,2,0,16,19,27).

      k=6:X=Z7×(Z5∪{∞}),H={Z7×{x}|x∈Z5∪{∞}},mod(7,5).

      D1:(01,22,44,62,00,6∞,43),(63,00,52,01,1∞,41,10),(24,63,60,54,1∞,02,30);

      D2:(62,00,01,22,44,33,6∞),(52,00,63,1∞,01,22,10),(60,63,24,1∞,54,10,30).

      k=8:X=Z7×(Z7∪{∞}),H={Z7×{x}|x∈Z7∪{∞}},mod(7,7).

      D1:(00,63,12,54,1∞,42,65),(12,34,45,1∞,10,05,53),(12,11,35,1∞,20,34,53),
      (56,44,31,22,53,62,21);

      D2:(12,54,1∞,00,63,65,21),(45,34,12,10,1∞,41,53),(1∞,20,12,11,35,45,34),
      (44,56,53,22,31,21,04).

      引理3對于i=1,2,存在Di-GD(v),v=7,8,14,15.

      證明:v=7,X=(Z3×Z2)∪{∞},mod(3,-),

      D1:(∞,00,01,10,21,20,11);D2:(∞,20,21,00,11,01,10).

      v=8,X=Z8,

      D1:(0,1,2,3,4,5,6),(0,2,4,1,6,5,7),(1,3,0,5,7,6,4),(3,5,6,2,7,4,0);

      D2:(0,1,2,3,4,5,6),(0,2,4,1,6,7,5),(3,0,5,7,1,6,2),(5,3,7,6,4,0,2)

      v=14,X=Z13∪{∞},mod 13,

      D1:(0,4,9,3,1,7,∞);D2:(0,4,9,3,1,6,∞).

      v=15,X=Z15,mod 15,

      D1:(0,4,9,3,1,7,8);D2:(0,4,9,3,1,6,10).

      引理4對于1≤i≤2,存在Di-GD7(v),v=7k+w,k=1,2,2≤w≤6.

      證明:v=9,X=Z9,mod 9,

      D1:(0,1,3,6,4,2,7)×3,(4,8,7,3,0,6,5);D2:(0,1,3,7,6,5,4)×3,(7,8,4,0,3,6,5).

      v=10,X=Z9∪{∞},mod 9,

      D1:(∞,0,4,3,1,6,5)×3,(0,1,3,5,2,∞,8),(0,1,2,5,3,6,4);

      D2:(∞,0,4,3,1,7,8)×3,(2,0,1,3,5,∞,6),(0,1,2,5,3,6,4).

      v=11,X=Z11,mod 11,

      D1:(0,1,3,6,2,4,7)×3,(0,1,5,4,9,8,10),(0,4,8,3,10,7,5);

      D2:(0,1,3,6,2,8,9)×3,(1,5,4,9,0,3,2),(0,4,8,3,10,5,9).

      v=12,X=Z11∪{∞},mod 11,

      D1:(∞,0,4,2,1,3,6)×3,(0,1,3,6,7,∞,2),(0,2,5,1,6,7,3),(0,1,5,3,4,10,7);

      D2:(∞,0,4,2,1,7,8)×3,(0,1,3,6,7,8,∞),(0,2,5,1,6,8,7),(0,1,5,3,4,7,6).

      v=13,X=Z13,mod 13,

      D1:(0,1,3,6,7,5,2)×3,(0,2,5,1,6,4,3),(0,4,9,3,6,8,1),(0,2,1,3,6,7,10);

      D2:(0,1,3,6,7,8,2)×3,(0,2,5,1,6,3,4),(0,4,9,3,6,5,8),(0,2,1,3,6,5,8).

      v=16,X=Z15∪{∞},mod 15,

      D1:(0,1,3,10,4,6,7)×4,(∞,0,4,2,1,7,6)×2,(∞,0,3,9,1,6,4),(0,1,3,6,10,∞,4);

      D2:(0,1,3,10,4,8,7)×4,(∞,0,4,2,1,11,7)×2,(∞,10,3,9,12,6,0),(0,1,3,6,10,9,∞).

      v=17,X=Z17,mod 17,

      D1:(0,1,3,10,4,6,7)×6,(0,8,1,9,3,16,11),(0,8,3,11,2,4,1);

      D2:(0,1,3,10,4,8,7)×6,(0,8,1,9,3,10,5),(0,8,3,11,2,12,10).

      v=18,X=Z17∪{∞},mod 17,

      D1:(0,1,3,6,10,∞,2)×5,(∞,0,5,7,1,6,13),(0,5,10,12,6,11,1),
      (0,1,4,12,5,7,9)×2;

      D2:(0,1,3,6,10,11,∞)×5,(∞,0,5,7,1,11,12),(0,5,10,12,6,4,7),
      (0,1,4,12,5,10,8)×2.

      v=19,X=Z19,mod 19,

      D1:(0,1,3,6,10,7,5)×6,(0,7,14,16,8,15,1),(0,7,14,6,13,15,5),(0,1,4,13,5,8,9);

      D2:(0,1,3,6,10,9,11)×6,(0,7,14,16,8,6,9),(0,7,14,6,13,3,17),(0,1,4,13,5,11,9).

      v=20,X=Z19∪{∞},mod 19,

      D1:(∞,0,5,11,1,6,8),(0,1,3,6,10,∞,2)×5,(0,5,11,4,12,1,9)×2,
      (0,5,10,4,9,6,3),(0,2,9,8,6,7,13);

      D2:(∞,0,5,11,1,12,17),(0,1,3,6,10,∞,14)×5,(0,5,11,4,12,7,1)×2,
      (0,5,10,4,9,11,17),(0,2,9,8,6,4,1).

      引理5對于1≤i≤2,存在Di-ID(7+w,w),2≤w≤6.

      證明:取X=Z7+w,洞為{7+i|i∈Zw},2≤w≤6.

      w=2:

      D1:(0,1,2,3,4,5,6),(0,2,4,1,3,5,6),(0,5,3,7,6,8,1),(0,7,2,6,8,4,3),(4,5,7,1,8,6,2);

      D2:(0,1,2,3,4,5,6),(0,2,4,1,3,5,6),(0,5,1,7,6,8,2),(3,5,8,4,7,2,6),(7,0,8,6,5,3,2).

      w=3:

      D1:(0,1,2,3,4,5,6),(0,2,4,1,3,5,6),(0,5,3,7,6,8,1),(0,8,4,5,9,2,1),
      (4,7,5,6,9,0,3),(6,2,7,1,8,9,3);

      D2:(0,1,2,3,4,5,6),(0,2,4,1,3,5,6),(0,5,1,7,6,8,2),(2,6,8,0,9,4,7),
      (3,5,9,4,7,1,6),(9,3,8,5,6,2,7).

      w=4:

      D1:(0,8,3,2,7,5,1),(5,9,4,1,10,3,0),(4,6,7,3,10,8,2),(0,1,2,4,3,6,5),
      (1,5,0,2,9,4,6),(2,6,3,1,8,10,4),(6,0,4,7,5,9,2);

      D2:(6,1,7,2,8,0,9),(5,0,10,3,9,1,8),(1,4,10,6,9,2,7),(0,1,2,3,4,5,6),
      (0,2,6,5,8,4,10),(1,5,7,4,8,3,2),(4,5,3,0,9,1,6).

      w=5:

      D1:(0,8,4,1,7,3,2),(5,10,4,2,9,3,0),(3,7,5,6,11,4,0),(1,9,4,0,10,3,2),
      (0,1,2,3,6,5,7),(0,2,11,4,5,8,3),(2,5,11,1,6,8,9),(4,3,1,8,6,0,10);

      D2:(6,0,7,2,8,1,9),(0,5,10,3,11,4,9),(0,4,11,6,10,2,9),(5,1,8,0,9,3,2),
      (0,1,2,4,3,5,7),(1,6,7,5,11,3,8),(9,1,3,5,4,2,6),(10,1,4,6,2,8,3).

      w=6:

      D1:(6,7,3,1,8,2,0),(5,9,12,10,0,4),(2,11,3,4,12,0,6),(4,7,5,6,9,1,2),
      (5,8,4,1,12,3,0),(0,1,5,2,3,11,9),(4,010,1,6,2,3),(6,0,5,4,2,7,8),
      (5,3,10,6,11,12,4);

      D2:(0,3,7,2,8,1,9),(4,5,10,2,11,3,12),(8,1,9,5,6,3,11),(5,0,12,3,8,6,11),
      (1,6,7,0,10,4,11),(0,1,2,4,6,3,8),(6,2,5,1,11,7,3),(6,9,0,4,10,2,12),
      (12,1,4,3,5,9,6).

      3 結(jié)論

      至此,已構(gòu)造出引理1中所需的各類圖分解,這樣,就得到了以下結(jié)論,即所討論的圖分解的存在譜:

      定理1對于1≤i≤2,Di-GDλ(v)存在的充分必要條件為λv(v-1)≡0(mod 14),v≥7.

      猜你喜歡
      區(qū)組河北師范大學(xué)同構(gòu)
      變化區(qū)組隨機(jī)化及其SAS宏實(shí)現(xiàn)
      賀河北師范大學(xué)百廿校慶
      巧用同構(gòu)法解決壓軸題
      如何正確運(yùn)用方差分析
      ——平衡不完全區(qū)組設(shè)計(jì)定量資料一元方差分析
      河北師范大學(xué)美術(shù)與設(shè)計(jì)學(xué)院油畫作品選登
      指對同構(gòu)法巧妙處理導(dǎo)數(shù)題
      同構(gòu)式——解決ex、ln x混合型試題最高效的工具
      高等代數(shù)教學(xué)中關(guān)于同構(gòu)的注記
      中醫(yī)臨床研究中區(qū)組設(shè)計(jì)應(yīng)用現(xiàn)狀的計(jì)量學(xué)分析*
      高等學(xué)校書法創(chuàng)作教學(xué)摭談——以河北師范大學(xué)為例
      宿迁市| 赤水市| 天台县| 若羌县| 青河县| 黎川县| 军事| 阿鲁科尔沁旗| 弥渡县| 宁波市| 红河县| 阿拉善盟| 东方市| 北海市| 安泽县| 定陶县| 禄丰县| 防城港市| 江城| 沙田区| 卓资县| 富民县| 贵南县| 武安市| 景德镇市| 吴川市| 紫金县| 九龙县| 通化县| 莲花县| 应城市| 三门县| 新沂市| 本溪市| 手机| 龙井市| 宁城县| 大城县| 容城县| 合水县| 耒阳市|