• 
    

    
    

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

      2—連通三正則平面網(wǎng)絡的結(jié)構(gòu)

      2017-06-02 09:45:10林馨
      數(shù)字技術(shù)與應用 2017年4期
      關(guān)鍵詞:子圖平面圖正則

      林馨

      摘要:對任意簡單圖G的兩條邊ab,cd滿足ac,bdE(G),令,該變換稱為開關(guān)變換。若圖G經(jīng)過有限次開關(guān)變換后,變成圖G,則稱圖G和圖G在開關(guān)變換下是連通的。本文將2-連通三正則平面網(wǎng)絡抽象為2-連通三正則平面圖,討論此圖類的結(jié)構(gòu),并驗證此圖類在開關(guān)變換下是連通的。

      關(guān)鍵詞:三正則;2連通;平面;開關(guān)變換

      中圖分類號:O157.5 文獻標識碼:A 文章編號:1007-9416(2017)04-0095-01

      1 引言

      在組合網(wǎng)絡理論中,網(wǎng)絡拓撲結(jié)構(gòu)可抽象為圖。網(wǎng)絡中的節(jié)點看做圖中的頂點,網(wǎng)絡中的連線看做圖中的邊。下面討論2-連通三正則平面網(wǎng)絡(圖)的結(jié)構(gòu)。

      對任意簡單圖G的兩條獨立的邊ab,cd滿足ac,bdE(G),令,則該變換稱為開關(guān)變換。

      若圖G經(jīng)過有限次開關(guān)變換后,變成圖G,則我們稱圖G和圖G在開關(guān)變換下是連通的。

      2 主要結(jié)論

      以下涉及到的圖論中常用符號和概念參見[1]。

      對任意n階2-連通三正則平面網(wǎng)絡G,,G中必存在哈密爾頓圈C。將圈C上的頂點按次序編號為。我們給出圖G的一個平面嵌入,并記落在圈C內(nèi)的邊集記為,在圈C外的邊集記為。

      定義1:記Jn為n階2-連通三正則平面圖集合。

      類似地,時,也能使得中含情形1)中的子圖H。

      定義3: 標準2-連通三正則平面圖:其哈密頓圈C上的頂點依次為,

      。

      定理2: 若,則對G進行有限次開關(guān)變換之后可得到,且每次變換得到的圖仍屬于Jn。

      證: (1)容易驗證n=4和n=6時,結(jié)論成立。(2)則對可以對G實行定理1中的開關(guān)變換,使其含有子圖K,將K中的3圈收縮后,得到的圖。

      綜上,由歸納法可知,若,則對G進行有限次開關(guān)變換之后可得到,且每次變換得到的圖仍屬于Jn。

      3 結(jié)語

      本文驗證了在開關(guān)變換下,任意一個2-連通三正則平面圖通過有限次開關(guān)變換都可以轉(zhuǎn)化為標準圖G*,再由開關(guān)變換的可逆性知整個2-連通三正則平面圖類在開關(guān)變換下是連通的。此結(jié)論為進一步研究各類網(wǎng)絡結(jié)構(gòu)提供了基礎(chǔ)。

      參考文獻

      [1]J.A Bondy and U.S.R Murty,“graph theory with applications”, 1st Edition, The MacMillan Press,1976.

      猜你喜歡
      子圖平面圖正則
      《別墅平面圖》
      《別墅平面圖》
      《景觀平面圖》
      臨界完全圖Ramsey數(shù)
      剩余有限Minimax可解群的4階正則自同構(gòu)
      類似于VNL環(huán)的環(huán)
      平面圖的3-hued 染色
      基于頻繁子圖挖掘的數(shù)據(jù)服務Mashup推薦
      有限秩的可解群的正則自同構(gòu)
      不含2K1+K2和C4作為導出子圖的圖的色數(shù)
      兴义市| 永安市| 合山市| 永胜县| 微山县| 西安市| 全南县| 阜南县| 大渡口区| 石景山区| 雅江县| 孟连| 盐边县| 印江| 扬中市| 方城县| 北流市| 兰州市| 正蓝旗| 七台河市| 兴山县| 怀集县| 中山市| 慈利县| 瑞昌市| 潍坊市| 老河口市| 翁源县| 临海市| 桓台县| 奉新县| 长葛市| 灌云县| 德州市| 寿阳县| 乌什县| 合阳县| 那坡县| 阿拉善右旗| 正镶白旗| 买车|